|
линейный конгруэнтный метод.
Применяется в простых случаях и не обладает криптографической стойкостью.
Этот алгоритм заключается в итеративном применении следующей формулы:
X[k+1]=(a*X[k]+c) mod m
Этот алгоритм используется в ANSI-C. Рассмотрим его:
#define RAND_MAX 32767
unsigned long next=1;
int rand(void) {
next=next*1103515245m;
return((unsigned int)(next/65536)2768);
}
void srand(unsigned int seed) {
next=seed;
}
Где a > 0, c > 0, m > 0 - некоторые целочисленные константы. Получаемая
последовательность зависит от выбора стартового числа X0 и при разных его
значениях получаются различные последовательности случайных чисел. В то же
время, многие свойства последовательности Xk определяются выбором коэффициентов
в формуле и не зависят от выбора стартового числа. Ясно, что последовательность
чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим m.
При этом длина периода равна m тогда и только тогда, когда:
1) НОД(c,m) = 1 (т.е. c и m взаимно просты);
2) a - 1 кратно p для всех простых p - делителей m;
3) a - 1 кратно 4, если m кратно 4.
При реализации выгодно выбирать m = 2e, где e - число бит в машинном слове,
поскольку это позволяет избавиться от относительно медленной операции
приведения по модулю. Младшие двоичные разряды сгенерированных таким образом случайных чисел
демонстрируют поведение, далёкое от случайного, поэтому рекомендуется
использовать только старшие разряды. Для генерации числа в диапазоне *0 - 2^32 -1* достаточно простого
умножения на мультипликатор и сложения с инкрементом. Деление по модулю
будет произведено автоматически при переполнении. Значения
мультипликатора и инкремента для этого случая получены в исследованиях
D. Knuth и H.W. Lewis.
Они рекомендуют использовать следующие коэффициенты:
a = 1664525, c = 1013904223, m = 2^32
Вот этой формулой рекомендуют пользоваться для генерации 32 битного числа.
next=64525*next+10 |
