У меня внеочередной проект игры, который предполагалось сделать за день или два. Анонсирую его позже. Однако, начав писать прототип, я сразу же зарылся в одну проблему.
Игра онлайновая, поэтому серверная часть делается на PHP. Игра использует генератор случайных чисел, текущее состояние которого должно сохраняться между ходами. То есть у каждого игрока должна быть своя отдельная сессия игры, где используется своё отдельное состояние генератора.
Встроенная в PHP функция mt_rand() не позволяет получить текущее состояние, поэтому я обратился к самописному генератору. В качестве основы я взял уже зарекомендовавший себя алгоритм xoshiro:
Но реализовать его в PHP оказалось не так просто.
Итак, для начала я просто перенёс код в PHP:
Но при попытке его использовать сразу возникла ошибка. Вместо целых чисел стали получаться вещественные.
Проблема в том, что в PHP нет ограничения на длину целого числа. При переполнении оно автоматически превращается в вещественное с плавающей точкой.
Алгоритм, реализованный на C или Rust, использует умножения и сдвиги, при которых числа могут переполняться, но переполнение работает штатно, то есть число просто обрезается. В PHP получается совсем другое.
Соответственно, на всех этапах вычисления я должен был вручную контролировать, чтобы число оставалось целым и 32-битным.
Сначала функция rotl():
Здесь 32-битный аргумент $x сдвигается влево, что должно вызывать переполнение, но этого не происходит, так как число просто увеличивается в сторону 64 бит. Чтобы эти биты действительно исчезли, я применяю маску с числом 0xffffffff, оставляя только младшие 32 бита.
Теперь функция xoshiro_next():
Результат rotl() мы получаем 32-битным благодаря контролю в самой функции rotl(), но он умножается на 9, что опять же может привести к переполнению, поэтому применяем маску на младшие 32 бита.
Сдвиг влево на 9 также может привести к переполнению, поэтому тоже применяем маску.
Наконец, каждая операция XOR изменяет биты во всём числе, которое по умолчанию 64-битное. Поэтому после каждого XOR я тоже применял к результату маску, чтобы обнулить лишние биты. Но подумав, решил этого не делать. Если в числах изначально установлены только 32 бита, то старшие биты будут всё равно обнулены, а 0 XOR 0 всё равно даст 0.
Для проверки того, что получилось, я написал тест:
Функция rnd() принимает текущее состояние генератора $state (это то, что мне и требовалось), меняет его (т.е. получает следующее состояние) и возвращает псевдослучайное число в пределах, заданных аргументом $range.
Я сделал цикл на миллион повторений, в котором вычисляется псевдослучайное число от 0 до 9 и увеличивается соответствующий счётчик. При равномерном распределении счётчик выпадения каждого числа должен составить около 100 тысяч.
Смотрим результат:
Действительно, получается примерно по 100 тысяч на каждое число с максимальным разбросом около 600 (погрешность 0,006). Если запускать генератор повторно, в среднем каждый счётчик будет равен 100 тысяч. Генератор работает, можно продолжать.