Генератор случайных чисел всего из трёх XOR и сдвиговВ 2003 году Джордж Марсалья представил xorshift - один из самых простых и быстрых генераторов псевдослучайных чисел.
Классический
xorshift32:
uint32_t xorshift32(void)
{
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
return state;
}
Фактически весь алгоритм:
shift → XOR
shift → XOR
shift → XOR
При ненулевом начальном
state период может достигать:
2³² - 1
Никаких умножений, делений или тяжёлой математики, поэтому подобные RNG отлично подходят для игр, симуляций и procedural generation, где важна скорость.
Но есть нюанс: xorshift нельзя использовать для криптографии. Его внутреннее состояние можно предсказать, поэтому для ключей, паролей и токенов нужны криптографически стойкие генераторы.
Иногда действительно полезный алгоритм помещается буквально в три строки.
#Programming #Algorithms #C #Random
