Реализация генератора псевдослучайных чисел в стандартной библиотеке C (в частности, в rand() и srand()) часто использует линейный конгруэнтный метод или похожий алгоритм, который работает с заданным зерном для генерирования последовательности чисел. Этот метод имеет форму:
X_{n+1} = (a * X_n + c) % m
Где:
X_n — текущее псевдослучайное число,
a, c, и m — константы, которые определяют характеристики генератора,
% — операция взятия остатка от деления.
Для понимания, как это может быть реализовано в коде, предположим, что мы создаем собственную реализацию генератора псевдослучайных чисел с линейным конгруэнтным методом.
#include <stdio.h>
#include <stdlib.h>
static unsigned long seed = 0;
void my_srand(unsigned int s) {
seed = s;
}
int my_rand(void) {
// Линейный конгруэнтный генератор
// X_{n+1} = (a * X_n + c) % m
const unsigned long a = 1664525; // Множитель
const unsigned long c = 1013904223; // Прибавка
const unsigned long m = 4294967296; // Модуль (2^32)
seed = (a * seed + c) % m; // Обновляем зерно
return (int)(seed >> 16); // Возвращаем результат, смещенный на 16 бит для получения диапазона 0-32767
}
int main() {
my_srand(42); // Устанавливаем зерно
for (int i = 0; i < 10; ++i) {
printf("%d\n", my_rand()); // Генерируем случайные числа
}
return 0;
}