Как генерировать «случайные», а также «уникальные» числа?

Question

Как генерируются случайные числа.? Как языки, такие как Java и т. Д. Генерируют случайные числа, особенно, как это делается для GUID.? я обнаружил, что алгоритмы, такие как генератор псевдослучайных чисел, используют начальные значения.

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

Answer 1

Первое: если число гарантированно никогда не повторится, оно не очень случайное.

Второе: существует множество алгоритмов PRNG .

UPDATE:

В-третьих: существует IETF RFC для UUID (что MS называет GUID), но вы должны признать, что (U | G) UID не криптографически безопасны, если это забота о вас.

ОБНОВЛЕНИЕ 2:

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

ОБНОВЛЕНИЕ 3:

Вот документы для .NET GUID

Answer 2

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

Но есть и другие способы получения случайных чисел, которые требуют специального оборудования для получения ИСТИННЫХ случайных чисел. Я знаю о некоторых покерных сайтах , которые используют это оборудование. Очень интересно читать, как они это делают.

Answer 3

Я понимаю, что вы ищете способ генерирования случайного числа с использованием C #. Если да, RNGCryptoServiceProvider - это то, что вы ищете.

[EDIT]

Если вы генерируете довольно большое количество байтов с помощью RNGCryptoServiceProvider, он, вероятно, будет уникальным, но нет гарантии. В теории истинные случайные числа не означают быть уникальными. Вы бросаете кости 2 раза, и вы можете получить голову оба раза, но они все еще случайны. НАСТОЯЩИЙ СЛУЧАЙ!

Я полагаю, чтобы применить проверку на уникальность, вам просто нужно развернуть свой собственный механизм хранения истории ранее сгенерированных чисел.

Answer 4

В частности, относительно Java:

• java.util.Random использует линейный конгруэнтный генератор , что не очень хорошо
• java.util.UUID#randomUUID() использует java.security.SecureRandom, интерфейс для множества криптографически безопасных ГСЧ - я полагаю, что по умолчанию используется SHA-1.
• UUID / GUID не обязательно случайные
• В сети легко найти реализации ГСЧ, которые намного лучше, чем java.util.Random, такие как Mersenne Twister или умножение с переносом

Answer 5

Вы можете использовать этот пример кода: http://xkcd.com/221/ Или вы можете использовать эту книгу: http://www.amazon.com/Million-Random-Digits-Normal-Deviates/dp/0833030477

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

Answer 6

Большинство генераторов случайных чисел имеют способ «случайной» повторной инициализации начального значения. (Иногда называется randomize).

Если это невозможно, вы также можете использовать системные часы для инициализации начального числа.