[Bull]

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

[CorwinXX]

Сообщение от k345 писал чт, 14 июня 2007 16:19

Те имея обычную монету с орлом и решкой можно генерить хоть 100!. - здесь возможна ошибка в рассуждениях связаная с распределением диапозона возможных чисел. В остальном, все что написал -аргументировал, смотри выше, и не надо выдирать куски фраз.

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

[k345]

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

[alles]

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

[k345]

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

[alles]

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

[alles]

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

[Dustangel]

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

[k345]

Сообщение от Dustangel писал чт, 14 июня 2007 21:11

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

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

Сообщение от Цитата:

И давай убирай каракули которые ты мне в рейтинг понаставлял.

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

[alles]

Сообщение от Dustangel писал чт, 14 июня 2007 21:11

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

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

Сообщение от Цитата:

И давай убирай каракули которые ты мне в рейтинг понаставлял.
p -> 0. Могу только добавить если очень хочешь.

Дафай, дафай

[Young]

Сообщение от CorwinXX писал чт, 14 июня 2007 16:54

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

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

И так у нас есть ГСПЧ с внешним источником энтропии. В данном случае это либо монетка либо например 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. ГСПЧ с внешним источником энтропии == ГСЧ, для утверждения терминологии.

[Young]

Сообщение от k345 писал пн, 11 июня 2007 14:35

И вообще по всей видимости выбор аналогового ГСЧ выбран по вопросам безопастности и быстродействия.

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

[k345]

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

[Young]

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

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

[k345]

Сообщение от Цитата:

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

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

[AVG51]

Сообщение от Young писал пт, 15 июня 2007 15:04

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

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

Сообщение от Young писал пт, 15 июня 2007 15:04

а бросок кубика последовательность от 000000 до 111111.

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

Сообщение от Young писал пт, 15 июня 2007 15:04

Далее. Все для проверки качества ГСПЧ его подвергают

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

Сообщение от Young писал пт, 15 июня 2007 15:04

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

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

[alles]

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

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


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


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


Без ограничения общности рассуждений можно считать, что любой ГСЧ, построен по следующей схеме: к выходам источника случайности 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.

[alles]

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

[alles]

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

[Young]

Сообщение от AVG51 писал вс, 17 июня 2007 02:51

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

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

Сообщение от AVG51 писал вс, 17 июня 2007 02:51

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

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

Сообщение от AVG51 писал вс, 17 июня 2007 02:51

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

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

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

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

[/quote]

Сообщение от AVG51 писал вс, 17 июня 2007 02:51

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

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

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