О пресловутом ГСЧ и честности покеррумов.

Мне вся дискуссия о сокращениях навевает воспоминания об Орруэлле

__________________
Cuius rei demonstrationem mirabilem sane setex hanc marginis exiguitas non caparet

Какая ошибка?
Запиши 100! в двоичном виде. Затем на каждую цифру кинь монетку. Решка - ноль, орёл - один. Получишь случайное число от 0 до 100! (точнее до ближайшей сверху степени двойки). Разве не так?

__________________
Моё мнение здесь для того, чтобы узнать, почему оно неправильное.

Да вроде так. Просто засомневался в распределении так как уже подзабыл немного, но взял до 7, те 000,001,010 итд. Те всего 8 цифр. Проверил - вроде все ок.Вероятность 0.5^3 = 0.125 для каждого числа. 8*0.125 = 1 вроде все сходится. Значит не ошибся - зря засомневался.

__________________
мой блог

К сожалению не так...В этом случае вероятность получить цифру 0 стремится к нулю. :(
Да и вообще глупо разбирать бессвязный поток слов...

__________________
bona fortuna

ну я же говорю иди учи тер-вер вероятность получить 0. Это 000. Три нуля подряд. 0.5^3 = 0.125

__________________
мой блог

Нука, "ГЕНЕРАТОР" ты наш "ученый" сгенерируй число 9!
Чтоб тебе проще было - в двоичной системе 1001...

__________________
bona fortuna

Короче! Разговаривать с тобой абсолютно бесполезно.
И давай убирай каракули которые ты мне в рейтинг понаставлял. :x

__________________
bona fortuna

k345 излагает крайне коряво, но если продраться сквозь форму и рассмотреть содержание, то оно будет верным.

__________________
Наша война - это работа, в первую очередь работа интеллекта, где эмоциям нет места, потому что они могут исказить решение задачи и оказаться в конечном счете гибельными.

Соглашусь. Просто лень много писать. Не люблю писать. Поэтому кидаю куски мысли - кому надо, тот поймет. А кто не поймет... объяснят те кто понял.

p -> 0. Могу только добавить если очень хочешь.

__________________
мой блог

Да не коряво он излагает, а ЧУШЬ городит!
Если число Х может быть описано 2мя разрядами,
а число Y(максимальное в массиве) - 999999ю разрядами,
то по автору "гениального"ГСЧ количество испытаний - 999999. Где же тут СЛУЧАЙНОСТЬ?
Человек не понимает понятия "СЛУЧАЙНОСТЬ" в принципе!


Дафай, дафай

__________________
bona fortuna

Очевидно не так.

И так у нас есть ГСПЧ с внешним источником энтропии. В данном случае это либо монетка либо например 64 гранный кубик. Как ЛЮБОЙ внешний источник энтропии данные источники не идеальны. Т.е. в монетке чаще выпадает определенная сторона, а в кубике n граней.

Для простоты расмотрим простейший ГСПЧ (без внтурених преобразований типа LFSR) - который просто преобразует результаты работы источника энтропии в бинарную последовательность. Т.е. бросок монетки будет добавлять к данной последовательности либо 0 либо 1, а бросок кубика последовательность от 000000 до 111111.

Далее. Все для проверки качества ГСПЧ его подвергают следующим тестам. *upd* как минимум

monobit test (equal numbers of ones and zeros in the sequence)
poker test (a special instance of the chi-squared test)
runs test (counts the frequency of runs of various lengths)
longruns test (checks whether there exists any run of length 34 or greater in 20 000 bits of the sequence)
autocorrelation test.

Очевидно что в случае с монеткой результат простейщего monobit теста будет как минимум не лучше, а чаще хуже чем с кубиком.

*Sic!* В утверждении выше я не прав. До утрировался. Вообщем смысл в том что чем меньше внутренних стостояний у источника энтропии сложнее из получившейся случайно последовательности получить "хорошо распределенную" последовательность. С монеткой и кубиком попробую подумать и расписать.

Проблема собственно в том том что ГСПЧ должен генерить не только наиболее случайную последовательность , он должен генерить так называемую well distributed sequences. И собственно все танцы с вокруг этого. В том числе и LFSR и прочее.

Это простещий вариант. В более сложном случае например монетка может быть идеальной - но солнце например будет светить то справа, то слева (тем самым создавая давление) - последовательность так же останеться случайной, но опять же будет не "well distributed". В случае кубика, за счет его формы, последовательность будет таки более "well".


Вот, попробовал на пальцах обхяснить как я понимаю.

P.S. ГСПЧ с внешним источником энтропии == ГСЧ, для утверждения терминологии.

Это не так. Существующие аппаратные ГСПЧ существенно уступают в скорости программным.

Ребята вы что смеетесь что ли? Фраза про монетку была в общем виде. Понятно что если у меня на столе лежит пыль, которая задувается из окна, то это пыль имеет четкое направление в виде бороздок, так как ветер дует из окна, и монетка, падая на стол, может попасть в бороздку, а так как насечки на грани монеты неравномерные, то....

__________________
мой блог

Речь о другом, речь о о разрядности ГПСЧ (учитывая что используються потоковые аппаратные ГПСЧ - то под данным термином можно понимать только "разрядность" внешнего источника энтропии).

Либо мы уже говорим не о аппаратных - ГПСЧ, а о неком программном алгоритме которые преобразует битовую последовательность выдаваемуе ГПСЧ в неколе логическое представление.

Совершенно верно.

__________________
мой блог

Из твоих рассуждений не видно, что "не так". Именно так и есть. Причем если взять идеальную (вымышленную) монету, имеющую абсолютно точное дискретное равномерное распределение, то и сгенерированное нами СЧ любой разрядности будет тоже иметь равномерное распределение.

Хотел бы я посмотреть на такой кубик!!!

А чего ты аббревиатуру ГПСЧ так исковеркал? И вообще, поясни для малограмотных, в честь чего АППАРАТНЫЙ ГСЧ будет выдавать ПСЧ? Нафига он тогда вообще нужен??? 8-)

Ты сам придумал эту проблему, тогда как CorwinXX говорил лишь о возможности генерации числа. Как это реализовано - это уже другой вопрос, который в данном разговоре вообще не затрагивался.

А.В. АРХАНГЕЛЬСКАЯ

Московский инженерно-физический институт (государственный университет)


ОБ ОДНОМ ПОДХОДЕ К ОПРЕДЕЛЕНИЮ ПОНЯТИЙ ГЕНЕРАТОРОВ СЛУЧАЙНЫХ И ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ


В работе проанализированы основные определения понятий генераторов случайных и псевдослучайных чисел и предложен подход к определению этих понятий, позволяющий при оценке генераторов учитывать как криптографические свойства используемых в них преобразований, так и характеристики применяемых источников случайности.


Без ограничения общности рассуждений можно считать, что любой ГСЧ, построен по следующей схеме: к выходам источника случайности a1,…, an применяется криптографическое преобразование, в результате чего получается последовательность случайных чисел b1,…, bm, причем ее длина не обязательно должна равняться длине исходной последовательности (рис. 1).


Рис 1. Обобщенная схема ГСЧ

Недетерминированность в работу ГСЧ вносится за счет источника случайности, то есть физического источника сигналов, выходы которого считаются случайными сами по себе. К ним с целью улучшения статистических характеристик может применяться криптографическое преобразование.

Рассмотрим наиболее часто встречающиеся определения генераторов псевдослучайных и случайных чисел (ГПСЧ и ГСЧ).

Определение 1. Генератором называется функция, вычислимая за полиномиальное от n время g: {0, 1}n ? {0, 1}q(n), q – некоторый полином.

Определение 2. Генератор g называется криптографически стойким ГПСЧ, если для любой полиномиальной вероятностной машины Тьюринга T, которая из двоичных строк длины q(n) вырабатывает один бит, для любого полинома p и всех достаточно больших n верно соотношение:


|P(T(r) = 1 | r ?R {0, 1}q(n)) – P(T(g(s)) = 1 | s ?R {0, 1}n)| < 1/p(n),

где вероятности определяются случайным выбором строк r и s и случайными величинами, используемыми машиной T, и функция g вычисляется при помощи детерминированного алгоритма.

Для криптографической стойкости ГПСЧ необходима однонаправленность функции g [1], причем существование криптографически стойких ГПСЧ равносильно существованию однонаправленных функций [2].

Определение 3. ГПСЧ называется способ преобразования короткой случайной последовательности в более длинную псевдослучайную последовательность с использованием детерминированного алгоритма [3].

Легко заметить, что эти определения рассматривают лишь свойства выполняемых в ГСЧ преобразований и совершенно не касаются свойств источника случайности. Отметим, что определения 1 и 2 рассматривают лишь бинарные входные и выходные последовательности.

В следующем определении делается попытка различить ГСЧ и ГПСЧ.

Определение 4. Если алгоритм получения случайных чисел является недетерминированным, то его реализация называется ГСЧ, а если – детерминированным, то ГПСЧ [4].

Однако в этом определении не рассматривается каких-либо количественных значений и оно мало пригодно для практического использования.

Используя энтропийный подход (по Шеннону), синтезируем на основе приведенных определение, свободное от отмеченных недостатков и учитывающее случай небинарной случайной последовательности.

Будем считать, что последовательности a1,…, an и b1,…, bm являются реализациями случайных величин ? и ?, оценим их энтропию H(?) и H(?).

Определение 5. Если H(?) ? H(?) и ? и ? независимы, назовем генератор ГСЧ, в противном случае – ГПСЧ.

Таким образом, в ГПСЧ часть энтропии выходной последовательности добавляется за счет детерминированного псевдослучайного преобразования, которое выглядит случайным и неотличимым от случайного в смысле определения 2.

__________________
bona fortuna

В более доступной форме - монета - ГСЧ на массиве (0,1),
игральный кубик - ГСЧ на массиве (1,2,3,4,5,6)...
Но на массиве (0...n) где п>>2 монета может быть только источником энтропии для реализации генератора ПСЕВДОслучайных чисел!
Если алгоритм этой реализации - первое испытание=первый разряд двоичного числа, второе=второй и т.д., то мы получим ГПСЧ с крайне неравномерным распределением...

__________________
bona fortuna

И еще...
Я понимаю на сколько разношерстным может быть состав пользователей интернетфорума. И я бы просто "похихикал в тряпочку" над сообщением юзера k345...если бы не - "LOL - иди учи тервер." и последующим выставлением мне отрицательного рейтинга.
Конечно минус от малограмотного суть есть плюс, но пускай еще и люди нас рассудят.

__________________
bona fortuna

Конечно, но какой смысл расматривать коня в ваккуме? Небывает иделаьных монеток.

Вы никогда не видели 64 гранных кубиков???? Честно?


ГСПЧ это опечатка. Помоему очевидно, и не понимаю зачем вам ерничать...

Я помоему писал выше - вообще-то ГСЧ это ГПСЧ с внешним источником энтропии.

Далее - я где нибудь сказал что ГСЧ (кстати почему только аппаратные) будет выдавать ПСЧ??? Можно указать? Безусловно он будет выдавать последовательность случайных чисел - вот только качество данных последовательностей может быть разное. Для этого и делаются тесты.

[/quote]

Тогда нужно определиться - либо мы говорим от ГСЧ, либо мы говорим о последующей обработки данных ГСЧ (например преобразовании случайно последовательности в определенный расклад карт). Все используют термины "кривизна ГСЧ" - следовательно мы говорим о первом? Или нет?

Если нет, то можно говорить еще о двух вещах - об алгоритмах обработки случайно последовательность чтобы сделать ее хорошо распределенной, и о преобразование уже полученной хорошо распределенной последовательности в конечный результат (а именно замешанную колоду карт).