Ping based random number generator

[mxustin]

Думаю, что разумно было бы хоть с чем-то сравнивать, что ли... Сделал визуализацию моего PBRNG рядом со стандартным "дельфовым" Random. Особых отличий, правда, пока не вижу. Тешу себя надеждой, что все-таки мои числа — истинно случайные, а System.Random генерирует псевдо-случайные числа.

[kvitaliy]

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

Сообщение от mxustin

Тешу себя надеждой, что все-таки мои числа — истинно случайные

По-настоящему случайными могут быть только квантовые процессы.

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

Вам всё же удалось добиться большего?

[p51x]

А без инета какая будет картинка?

[mxustin]

Сообщение от kvitaliy

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

По-настоящему случайными могут быть только квантовые процессы.

Вам всё же удалось добиться большего?

Думаю, что, наверное нет )))) раз там ученые месяцами бьются и лишь 42 случайных числа получили за это время. Но, я хотел бы попросить Вас, если не трудно, пояснить немного свою мысль. Вероятно Вы (или те ученые) под «подлинно случайными» числами подразумевают что-то особенное...

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

На сколько я понимаю, псевдослучайные числа — это такие числа, которые генерируются некоторым полностью детерминированным алгоритмом, то есть, потенциально могут быть воспроизведены в любой момент с полной точностью. Если же в основе генератора лежит некий физический процесс, который заранее предсказать невозможно, то даже несмотря на то, что алгоритм все же детерминирован, числа, сгенерированные им, будут случайными. Разве нет?

Другое дело, что есть еще такое понятие, как распределение. Человек, например, — это хороший источник случайных чисел, но, надо полагать, что числа, «генерируемые» человеком будут очень плохо распределены. (Каких-то будет всегда больше, а других — меньше.) Я, вот, например, стараюсь свои пароли делать «как можно более случайными» (а «генерирую» их путем «хаотичного тыканья» по клавиатуре). Однако, на деле, когда я посмотрел список своих паролей, то увидел в нем, что некоторые последовательности встречаются явно чаще других. (Собственно, после этого я и решил запилить генератор случайных чисел.)

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

Про кучу обезьян, конечно помню да. На сколько я знаю, даже есть некий «monkey-test» для псевдо-случайных последовательностей. Когда-нибудь, надеюсь, доберусь до того, чтобы разобраться с ним.

А без инета какая будет картинка?

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

(Сделаю ремарку, что я подразумеваю, что в моем случае, числа, которые генерируются с использованием энтропии, полученной от пинг-а — вроде как, истинно случайные, ибо: а) я никак не могу влиять на время пинга, б) заранее невозможно предсказать, каким именно будет время пинга).

Со своей стороны хочу сделать апдэйт.

Я построил частотный тест (пока что провел 100 тыс. испытаний). Сравнивал мой ГСЧ и System.Random (Delphi). Вот, что получилось:



На иллюстрации сверху — результаты работы моего ГСЧ (PBRNG), а снизу - результаты работы System.Random (Delphi).

Первый столбец — это цифра (тест был рассчитан на выпадение цифр от 0 до 9).
Второй столбец — это количество выпадений данной цифры (в абсолютном выражении).
Третий столбец — это процентное отношение количества выпадений определенной цифры к общему количеству испытаний (внизу можно видеть: Total: 100016).
Четвертый столбец — это пометка максимального и минимального числа «выпадений».
Пятый столбец — это процентная разница между количеством выпадений данной цифры и количеством выпадений той цифры, которая выпала максимальное число раз.

Можно видеть, что в случае PBRNG на 100000 испытаний получается, что разница между максимумом и минимумом немного меньше, чем в случае System.Random. Правда, я должен сознаться, что бывало (на протяжении этих 100 тыс. испытаний) и наоборот.

У PBRNG за эти 100 тыс. испытаний чаще всего выпадала четверка (ее количество — 10235, что составляет 10.233% от 100016). Реже всех выпадала тройка (она выпала «всего лишь» 9754 раза, что составляет 9.752% от 100016). Таким образом, разница между «самой популярной» и «наименее популярной» цифрами составляет 0.481%.

У System.Random эта разница составляет 0.532%.


P.S. Что я еще понял, — так это то, что картинки надо разных размеров рисовать. Где на одном размере не будет заметен частотный узор, то на другом размере — будет.

[kvitaliy]

Сообщение от mxustin

под «подлинно случайными» числами подразумевают что-то особенное...

Ну в общем да. Если мы говорим о *действительно* случайных числах — то только квантовые аппаратные генераторы, там жестко подперто, что за рандомность отвечает вселенная в лице квантовой механики.

(Сделаю ремарку, что я подразумеваю, что в моем случае, числа, которые генерируются с использованием энтропии, полученной от пинг-а — вроде как, истинно случайные, ибо: а) я никак не могу влиять на время пинга, б) заранее невозможно предсказать, каким именно будет время пинга).

Предсказать невозможно, но практический диапазон значений невелик.
Тогда чем хуже использование энтропии, полученной от кол-ва секунд, прошедшего с включения компьютера? Тоже число случайное.
Но диапазон таких чисел конечный и известен.
Отсюда вопрос - если мне нужно сгенерировать 1000000 случайных чисел подряд, я должен для каждого числа получить свой пинг, или один раз на все 1000000 чисел?
Любой ответ на мой вопрос вскрывает тот или иной недостаток вашего метода.

[mxustin]

Сообщение от kvitaliy

Ну в общем да. Если мы говорим о *действительно* случайных числах — то только квантовые аппаратные генераторы, там жестко подперто, что за рандомность отвечает вселенная в лице квантовой механики.


Предсказать невозможно, но практический диапазон значений невелик.
Тогда чем хуже использование энтропии, полученной от кол-ва секунд, прошедшего с включения компьютера? Тоже число случайное.
Но диапазон таких чисел конечный и известен.
Отсюда вопрос - если мне нужно сгенерировать 1000000 случайных чисел подряд, я должен для каждого числа получить свой пинг, или один раз на все 1000000 чисел?
Любой ответ на мой вопрос вскрывает тот или иной недостаток вашего метода.

Вас понял. То есть, грубо говоря, если для получения 1 млн. случайных чисел пинговать миллион раз — то вскрывается недостаток, который заключается в крайне невысокой скорости получения СЧ (при таких запросах, как миллион (или более) СЧ, получается, что время пинга (которое, как правило, исчисляется несколькими миллисекундами, а иногда — десятками миллисекунд) оказывается «слабым звеном»). Если же «пингануть» один раз, и на основе этого сгенерировать миллион числе (как у меня и делается), — то получается, что вскрывается другой недостаток, а именно: слишком малое количество изначальной энтропии. Верно?

[kvitaliy]

Ваши рассуждения абсолютно совпадают с моими.

[mxustin]

Сделал «масштабную» шумовую визуализацию:

[mxustin]

Сообщение от kvitaliy

Ваши рассуждения абсолютно совпадают с моими.

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

[Аватар]

RandSeed инициализирован своим способом, а дальше обычный Random? Это ни чем не отличается от делфийского способа