Переносимость и воспроизводимость методов ГСЧ

Question

Я могу использовать один из двух методов для создания последовательности псевдослучайных чисел, которая имеет две важные характеристики: (1) она воспроизводима на разных машинах, и (2) последовательность никогда не повторяет число в пределах диапазона, пока все не будут выпущены .

Мой вопрос: есть ли у этих методов потенциальные проблемы в отношении переносимости (ОС, версии Python и т. Д.)? Например, кто-нибудь знает, получу ли я один набор результатов в одной системе, а другой - в другой, если значение XXX истинно?

Я на самом деле не спрашиваю совета о том, какой метод использовать сам по себе, только если я должен следить за X в системе Y, когда Z истинно.

Я пробовал несколько версий Linux, все 64-битные, и они кажутся согласованными, но у меня нет легкого доступа к Windows или 32-битным версиям.

Обратите внимание, что они не дают одинаковые диапазоны, но это нормально для моих целей. Числа просто должны казаться случайными для человеческого глаза.

Метод 1
генерирует случайную выборку из диапазона с использованием собственных функций библиотеки Python. Это медленно, если я использую большие диапазоны (10 м или более), но хорошо для относительно небольших, и намного легче понять для людей без степени по математике:

import random
random.seed(5)
x = random.sample(range(10000,99999),89999)
for i in range(10):
   print(x[i])

Метод 2
использует алгоритм не из библиотеки Python:
(https://en.wikipedia.org/wiki/Linear_congruential_generator)
Это супер быстро даже для больших диапазонов, но сложнее для понимания и поэтому выявляет потенциальные проблемы с:

def lcg(modulus, a, c, seed):
  while True:
    seed = (a * seed + c) % modulus
    yield seed


m = 10000019
c = int(m/2)
a = 5653
s = a

g = lcg(m,a,c,s)
for _ in range(10):
  print(next(g))

Заметьте, я более чем открыт для альтернатив; оригинальный вопрос был задан здесь: https://math.stackexchange.com/questions/3289084/generate-a-pseudo-random-predictable-non-repeating-integer-sequence-purely-math

Answer 1

Наиболее переносимая версия, IMO, будет LCG с периодом, равным натуральному размеру слова машины.Он использует переполнение регистра для модуля, что делает его еще быстрее.Для этого нужно использовать типы данных NumPy, здесь приведен простой код, константы a, c взяты из таблицы 4 здесь

import numpy as np

def LCG(seed: np.uint64, a: np.uint64, c: np.uint64) -> np.uint64:
    with np.errstate(over='ignore'):
        while True:
            seed = (a * seed + c)
            yield seed

a = np.uint64(2862933555777941757)
c = np.uint64(1)

rng64 = LCG(np.uint64(17), a, c)

print(next(rng64))
print(next(rng64))
print(next(rng64))

И для Linux x64, и для Windows x64, а также для ОСX VM работает точно так же.

Что касается воспроизводимости, единственным преимуществом является сохранение первых чисел пары и сравнение их с выводом LCG на этапе инициализации приложения - если они в порядке, вы продолжаете.

Еще одной особенностью LCG, которая мне нравится, является ее способность прыгать вперед в журнале ₂ (N) времени, где N - количество пропусков.Я мог бы предоставить вам код для этого.Используя скачок вперед, вы можете обеспечить неперекрывающиеся последовательности для параллельных независимых случайных потоков

UPDATE

Вот перевод моего кода C на Python / NumPy, похоже, работает.В логарифмическом времени он может пропускать как вперёд, так и назад.

import numpy as np

class LCG(object):

    UZERO: np.uint64 = np.uint64(0)
    UONE : np.uint64 = np.uint64(1)

    def __init__(self, seed: np.uint64, a: np.uint64, c: np.uint64) -> None:
        self._seed: np.uint64 = np.uint64(seed)
        self._a   : np.uint64 = np.uint64(a)
        self._c   : np.uint64 = np.uint64(c)

    def next(self) -> np.uint64:
        self._seed = self._a * self._seed + self._c
        return self._seed

    def seed(self) -> np.uint64:
        return self._seed

    def set_seed(self, seed: np.uint64) -> np.uint64:
        self._seed = seed

    def skip(self, ns: np.int64) -> None:
        """
        Signed argument - skip forward as well as backward

        The algorithm here to determine the parameters used to skip ahead is
        described in the paper F. Brown, "Random Number Generation with Arbitrary Stride,"
        Trans. Am. Nucl. Soc. (Nov. 1994). This algorithm is able to skip ahead in
        O(log2(N)) operations instead of O(N). It computes parameters
        A and C which can then be used to find x_N = A*x_0 + C mod 2^M.
        """

        nskip: np.uint64 = np.uint64(ns)

        a: np.uint64 = self._a
        c: np.uint64 = self._c

        a_next: np.uint64 = LCG.UONE
        c_next: np.uint64 = LCG.UZERO

        while nskip > LCG.UZERO:
            if (nskip & LCG.UONE) != LCG.UZERO:
                a_next = a_next * a
                c_next = c_next * a + c

            c = (a + LCG.UONE) * c
            a = a * a

            nskip = nskip >> LCG.UONE

        self._seed = a_next * self._seed + c_next    


np.seterr(over='ignore')

a = np.uint64(2862933555777941757)
c = np.uint64(1)
seed = np.uint64(1)

rng64 = LCG(seed, a, c) # initialization

print(rng64.next())
print(rng64.next())
print(rng64.next())

rng64.skip(-3) # back by 3
print(rng64.next())
print(rng64.next())
print(rng64.next())

rng64.skip(-3) # back by 3
rng64.skip(2) # forward by 2
print(rng64.next())

В любом случае, краткий обзор ГСЧ:

1. С хорошими константами (см. Ссылку на статью L'Ecuyer)он будет охватывать весь диапазон [0 ... 2 ⁶⁴ ) без повторения.В основном идеальное отображение [0 ... 2 ⁶⁴ ) -> [0 ... 2 ⁶⁴ ), вы можете установить 0,1,2,3, ... в качестве входных данныхи получить вывод всего диапазона
2. Это обратимо, вы можете получить предыдущее начальное число, так что отображение фактически является биекцией, [0 ... 2 ⁶⁴ ) <-> [0 ... 2* +1032 * 64 * * тысяча тридцать три).Подробнее см. Обратимый генератор псевдослучайных последовательностей
3. . Он имеет логарифмический пропуск вперед и назад, поэтому нет проблем с поиском подходящих интервалов для параллельных вычислений - начните с одного начального числа, а затем затемпоток будет пропущен (seed, 2 ⁶⁴ / N), следующий поток пропущен (seed, 2 ⁶⁴ / N * 2) и так далее и так далее.Гарантированно не перекрываются
4. Это просто и быстро, хотя и не очень высокого качества RNG

Answer 2

Существует множество способов, которыми алгоритм (в частности, генератор псевдослучайных чисел) может дать противоречивые результаты на разных компьютерах. Наиболее заметный способ - если алгоритм использует числа с плавающей запятой (которые почти всегда имеют ограниченную точность) и округление с плавающей запятой.

Некоторые языки программирования более подвержены проблемам переносимости, чем другие. Например, в отличие от Python, в C или C ++ могут возникать противоречивые результаты из-за & mdash;

• Неопределенное поведение целочисленных переполнений со знаком или
• как по-разному определяются длины определенных типов данных, в частности int и long в разных компиляторах.

Мне неизвестно, каким образом код Python в методе 2 может давать противоречивые результаты на разных компьютерах. С другой стороны, может ли метод 1 сделать это, зависит от того, реализован ли random.sample одинаково для всех версий Python, которые вам интересны, и для всех компьютеров.

Answer 3

LCG - это хорошо. Если вы хотите сделать LCG более понятными, вы можете реализовать их рекурсивно, а не итеративно, чтобы выделить рекурсивную формулу, на которой она основана. Делайте это, только если вы не слишком беспокоитесь о сложности.

В противном случае, я думаю, что метод 2 достаточно ясен для PRNG.