Генератор случайных чисел с использованием 8051

1.1 Алгоритмы ГПСЧ

Любая последовательность, сгенерированная по жестко заданному алгоритму, не может считаться истинно случайной, поэтому, ведя речь об алгоритмических генераторах, употребляют термин псевдослучайная последовательность. Любой генератор псевдослучайных чисел (ГПСЧ) рано или поздно зацикливается, другое дело в том, что это «поздно» может наступить через несколько миллисекунд, а может через несколько лет. Длина цикла зависит от размера внутреннего состояния генератора N (фактически, это объем памяти, нужный генератору), и составляет от 2(N/2) до 2N бит.
Алгоритмов ГПСЧ придумано огромное множество, но далеко не все они удобны для реализации на микроконтроллерах. Мы сильно ограничены в быстродействии и доступном объеме памяти, многие контроллеры не поддерживают вещественную арифметику и даже команды умножения. Помня о подобных ограничениях, рассмотрим некоторые известные алгоритмы.

1.2 Линейный конгруэнтный метод

Очередной член последовательности рассчитывается по формуле
Xi+1 = (aXi + c) mod m
Число m определяет максимальный период последовательности, целые числа a и c — «магические» коэффициенты. Число m разумно выбирать равным степени двойки, в таком случае опреация приведения по модулю сводится к отбрасыванию старших битов. Для того, чтобы получить максимальный период, нужно соблюдать следующие условия:
— c и m должны быть взаимно простыми,
— a-1 должно быть кратно p для всех простых делителей p числа m,
— если m кратно 4 (а в нашем случае оно будет кратно), то и a-1 должно быть кратно 4.
Есть еще одна тонкость: в качестве результата следует брать только старшие биты переменной состояния X, так как для младших бит статистические параметры случайности значительно хуже. Линейный конгруэнтный алгоритм обычно реализован в качестве стандартного rand() во многих библиотеках.
Плюсы:

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

Минусы:

• 
  требуется операция умножения;
  
• 
  не все биты одинаково случайны.
  

Резюме: быстрый и простой алгоритм для не очень ответственных применений.