Кнут хорошо освещает тему случайности.
Мы не очень хорошо понимаем случайность.Как что-то предсказуемое может быть случайным?И все же псевдослучайные последовательности могут показаться совершенно случайными с помощью статистических тестов.
Существует три категории генераторов случайных чисел, которые усиливаются в приведенном выше комментарии.
Во-первых, у вас есть генераторы псевдослучайных чиселгде, если вы знаете текущее случайное число, легко вычислить следующее.Это облегчает обратный инжиниринг других чисел, если вы обнаружите несколько.
Тогда есть криптографические алгоритмы, которые делают это намного сложнее.Я полагаю, что они все еще являются псевдослучайными последовательностями (вопреки тому, что подразумевается в приведенном выше комментарии), но с очень важным свойством, что знание нескольких чисел в последовательности НЕ делает очевидным, как вычислить остальные.Это работает так, что крипто-подпрограммы имеют тенденцию хэшировать число, поэтому, если один бит изменяется, в результате равный шанс может измениться каждый бит.
Рассмотрим простой генератор по модулю (аналогично некоторым реализациям вC rand ())
int rand () {возврат семян = seed * m + a;}
если m = 0 и a = 0, это паршивый генератор с периодом 1: 0, 0, 0, 0, .... если m = 1 и a = 1, это тоже не оченьслучайный вид: 0, 1, 2, 3, 4, 5, 6, ...
Но если вы выберете m и a в качестве простых чисел около 2 ^ 16, то это будет очень красиво выглядеть очень случайнымесли вы случайно осматриваете.Но поскольку оба числа нечетные, вы увидите, что младший бит будет переключаться, то есть число будет попеременно нечетным и четным.Не отличный генератор случайных чисел.А поскольку в 32-битном числе только 2 ^ 32 значения, по определению после максимум 2 ^ 32 итераций вы будете повторять последовательность еще раз, делая очевидным, что генератор НЕ является случайным.
Если выПредставьте, что средние биты хороши и скремблированы, в то время как младшие биты не так случайны, из нескольких из них вы можете построить лучший генератор случайных чисел, с различными битами XOR, сгруппированными вместе, чтобы все биты были хорошо покрыты,Что-то вроде:
(rand1 () >> 8) ^ rand2 () ^ (rand3 ()> 5) ...
Тем не менее, каждое число синхронизируется, что делает этопредсказуемы.И если вы получите два последовательных значения, они будут коррелированы, так что если вы построите их, вы получите линии на экране.Теперь представьте, что у вас есть правила, объединяющие генераторы, так что последовательные значения не являются следующими.Например,
v1 = rand1 () >> 8 ^ rand2 () ... v2 = rand2 () >> 8 ^ rand5 () ..
и представьте, что семена нет всегда вперед.Теперь вы начинаете делать что-то, что намного сложнее предсказать, основываясь на обратном инжиниринге, и последовательность длиннее.
Например, если вы каждый раз вычисляете rand1 (), но только продвигаете начальное число в rand2 () каждый третий раз объединяющий их генератор может не повторяться гораздо дольше, чем период одного из них.
Теперь представьте, что вы прокачиваете свой (довольно предсказуемый) генератор случайных чисел по модулю через DES или другое шифрованиеалгоритм.Это будет накапливать биты.
Очевидно, есть лучшие алгоритмы, но это дает вам представление.У Числовых Рецептов есть много алгоритмов, реализованных в коде и объясненных.Один очень хороший трюк: генерировать не одно, а блок случайных значений в таблице.Затем используйте независимый генератор случайных чисел, чтобы выбрать одно из сгенерированных чисел, сгенерировать новое и заменить его.Это нарушает любую корреляцию между соседними парами чисел.
Третья категория - это фактические аппаратные генераторы случайных чисел, например, основанные на атмосферном шуме
http://www.random.org/randomness/
Это, согласно современной науке, действительно случайно.Возможно, когда-нибудь мы обнаружим, что оно подчиняется некоторому основному правилу, но в настоящее время мы не можем предсказать эти значения, и они «действительно» случайны, насколько нам известно.
В библиотеке boost есть отличные реализации на С ++ генераторов Фибоначчи, царствующих королей псевдослучайных последовательностей, если вы хотите увидеть некоторый исходный код.