javascript - 線形合同法のA、C、Mの選択

Question

指定された期間があり、その期間中は衝突がないことが保証されている単純な疑似乱数ジェネレーター（PRNG）を実装しようとしています。いくつかの調査を行った後、私は完璧な非常に有名なLCGに出くわしました。問題は、それを適切に構成する方法を理解するのに苦労していることです。これが私の現在の実装です：

    function LCG (state)
    {
        var a = ?;
        var c = ?;
        var m = ?;

        return (a * state + c) % m;
    }

すべてのシード値に対して完全な期間を設定するには、次の条件が満たされている必要があると記載されています。

cとmは互いに素です
a-1はmのすべての素因数で割り切れる
mが4の倍数である場合、a-1は4の倍数です

1と3は、理解とテストが簡単です。しかし、2についてはどうでしょうか、それが何を意味するのか、それをチェックする方法がよくわかりません。そして、Cはどうですか、それはゼロになることができますか？ゼロ以外の場合はどうなりますか？

全体として、 48 ^ 5 -1の期間を持つように、A、C、およびMを選択する必要があります。Mは周期に等しいので、AとCについてはよくわかりません。

score 14 · Accepted Answer

ウィキペディアから：

cがゼロ以外の場合、 LCGは、次の場合にのみ、すべてのシード値に対して完全な期間を持ちます。

cとmは互いに素であり、

a -1は、 mのすべての素因数で割り切れます。

mが4の倍数である場合、 -1は4の倍数です。

48 ⁵ -1の期間が必要だと言ったので、m≥485-1を選択する必要があり^ます。m = 48 ⁵ -1を選択してみて、それがどこに行くのか見てみましょう。ウィキペディアの記事の条件では、期間をmにしたい場合は、c =0を選択できません。

11、47、541、および911はすべて素数であり、11 * 47 * 541 * 911 = 48 5 -1であるため、485-1^の^素因数であることに注意してください。

これらの各条件を見ていきましょう。

cとmが互いに素であるためには、cとmに共通の素因数があってはなりません。したがって、 11、47、541、および911以外の素数を選択し、それらを掛け合わせてcを選択します。
-1がmのすべての素因数で割り切れるようなものを選択する必要があります。つまり、選択した任意のxに対してa = x * 11 * 47 * 541 * 911+1です。
mは4の倍数ではないため、3番目の条件は無視してかまいません。

要約すれば：

m = 48 ⁵ -1
c = 11、47、541、および911以外の素数の積（また、cはm未満でなければなりません）、
a = x * 11 * 47 * 541 * 911 + 1、選択した非負のxの場合（また、aはm未満である必要があります）。

^{これは、48 2} -1（素因数7と47）の期間を使用する（Pythonの）より小さなテストケースです。

def lcg(state):
    x = 1
    a = x*7*47 + 1
    c = 100
    m = 48**2 - 1
    return (a * state + c) % m

expected_period = 48**2 - 1
seeds = [5]
for i in range(expected_period):
    seeds.append(lcg(seeds[-1]))
print(len(set(seeds)) == expected_period)

必要に応じて出力Trueします。（Pythonの読み取りに問題がある場合は、お知らせください。JavaScriptに翻訳できます。）

score 1 · Accepted Answer

Snowballの回答とコメントに基づいて、完全な例を作成しました。set == list小さい数の比較を使用できます。48^5-1私は記憶に収まりませんでした。

この問題を回避するためにa < m、ターゲットを数回インクリメントして、可能な数（素因数が重複している）をa見つけ< mますm。驚くべきことに、多くの数には+2で十分です。いくつかの余分な数字は、後で反復中にスキップされます。

import random

def __prime_factors(n):
    """
    https://stackoverflow.com/a/412942/6078370
    Returns all the prime factors of a positive integer
    """
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
        if d * d > n:
            if n > 1: factors.append(n)
            break
    return factors

def __multiply_numbers(numbers):
    """multiply all numbers in array"""
    result = 1
    for n in numbers:
        result *= n
    return result

def __next_good_number(start):
    """
    https://en.wikipedia.org/wiki/Linear_congruential_generator#c%E2%89%A00
    some conditions apply for good/easy rotation
    """
    number = start
    factors = __prime_factors(number)
    while len(set(factors)) == len(factors) or number % 4 == 0:
        number += 1
        factors = __prime_factors(number)
    return number, set(factors)

# primes < 100 for coprime calculation. add more if your target is large
PRIMES = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
        43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97])

def create_new_seed(target):
    """be aware, m might become > target"""
    m, factors = __next_good_number(target)
    a = __multiply_numbers(factors) + 1
    # https://en.wikipedia.org/wiki/Coprime_integers
    otherPrimes = [p for p in PRIMES if p not in factors]
    # the actual random part to get differnt results
    random.shuffle(otherPrimes)
    # I just used arbitary 3 of the other primes
    c = __multiply_numbers(otherPrimes[:3])
    # first number
    state = random.randint(0, target-1)
    return state, m, a, c

def next_number(state, m, a ,c, limit):
    newState = (a * state + c) % m
    # skip out of range (__next_good_number increases original target)
    while newState >= limit:
        newState = (a * newState + c) % m

    return newState

if __name__ == "__main__":
    target = 48**5-1
    state, m, a, c = create_new_seed(target)
    print(state, m, a, c, 'target', target)

    # list and set can't fit into 16GB of memory
    checkSum = sum(range(target))
    randomSum = 0
    for i in range(target):
        state = newState = next_number(state, m, a ,c, target)
        randomSum += newState
    print(checkSum == randomSum) # true

LCGは非常に魅力的で、ゲームなどで使用できます。
決定論的なランダムな順序で物事の巨大なリストを繰り返すことができます。リスト全体をシャッフルして保存する必要はありません。

def riter(alist):
    """ iterate list using LCG """
    target = len(alist)
    state, m, a, c = create_new_seed(target)
    for _ in range(target):
        yield alist[state]
        state = next_number(state, m, a ,c, target)

反復ステップの間に状態を保存するのは簡単です。

savedState = '18:19:25:6:12047269:20'
print('loading:', savedState)
i, state, m, a, c, target = (int(i) for i in savedState.split(':'))
state = next_number(state, m, a, c, target)
i += 1
print('i:', i, 'is random number:', state, 'list done:', i+1 == target)
print('saving:', '{}:{}:{}:{}:{}:{}'.format(i, state, m, a, c, target))

javascript - 線形合同法のA、C、Mの選択

2 に答える 2

Related

Reference