Создание настраиваемого LCG, который перемещается назад и вперед

Question

Как мне сделать так, чтобы LCG (тип генератора псевдослучайных чисел) перемещался в обоих направлениях? Я знаю, что путешествие вперед (a*x+c)%m но как я смогу изменить это? Я использую это, чтобы я мог хранить начальное число в позиции игрока на карте и иметь возможность генерировать вещи вокруг него, распространяя их вперед и назад в LCG (как какая-то линия случайных чисел).

Answer 1

Весь цикл LCG. В LCG, который достигает максимальной длины цикла, есть уникальный предшественник и уникальный преемник для каждого значения x (что не обязательно будет верно для LCG, которые не достигают максимальной длины цикла, или для других алгоритмов с поведением подциклов, таких как von Метод среднего квадрата Неймана).

Предположим, что наш LCG имеет длину цикла L. Поскольку поведение циклично, это означает, что после L итераций мы вернулись к начальному значению. Поиск значения предшественника с помощью одного шага назад математически эквивалентен шагу (L-1) вперед.

Большой вопрос, может ли это быть превращено в один шаг. Если вы используете мультипликативный LCG с основным модулем (где аддитивная константа равна нулю), это сделать довольно просто. Если x_{i + 1} = a * x_i % m, то x_{i + n} = aⁿ * x_i % m. В качестве конкретного примера рассмотрим PMMLCG с a = 16807 и m = 2³¹-1. Максимальная длина цикла равна m-1 (по очевидным причинам она не может быть равна 0), поэтому наша цель - выполнить итерацию m-2 раза. Мы можем предварительно рассчитать^m-2 % m = 1407677000, используя легкодоступные библиотеки возведения в степень / мод. Следовательно, шаг вперед определяется как x_{i + 1} = 16807 * x_i % 2³¹-1, а шаг назад определяется как x_i-1 = 1407677000 * x_i % 2³¹-1.

---

ДОПОЛНИТЕЛЬНЫЙ

Эту же концепцию можно распространить на универсальные LCG полного цикла, приведя переход к матричной форме и выполнив быстрое возведение в степень матрицы, чтобы получить эквивалентное одностадийное преобразование. Формула матрицы для x_{i + 1} = (a * x_i + c)% m равна X_{i + 1} = T · X_i % m, где T - матрица [[a c],[0 1]] и X - вектор столбца (x, 1) транспонированный. Множественные итерации LCG могут быть быстро рассчитаны путем повышения T до любой желаемой мощности с помощью методов быстрого возведения в степень с использованием возведения в квадрат и деления пополам мощности. Заметив, что возможности матрицы T никогда не изменяют второй ряд, я смог сосредоточиться только на вычислениях первого ряда и произвел следующую реализацию в Ruby:

def power_mod(ary, mod, power)
  return ary.map { |x| x % mod } if power < 2
  square = [ary[0] * ary[0] % mod, (ary[0] + 1) * ary[1] % mod]
  square = power_mod(square, mod, power / 2)
  return square if power.even?
  return [square[0] * ary[0] % mod, (square[0] * ary[1] + square[1]) % mod]
end

где ary является вектором, содержащим a и c, мультипликативный и аддитивный коэффициенты.

Используя это с power установив длину цикла - 1, я смог определить коэффициенты, которые дают предшественник для различных LCG, перечисленных в Википедии. Например, чтобы "обратить вспять" LCG с a = 1664525, c = 1013904223 и m = 2³², используйте a = 4276115653 и c = 634785765. Можно легко подтвердить, что последний набор коэффициентов переворачивает последовательность, полученную с помощью исходные коэффициенты.