18

我希望实现一个简单的伪随机数生成器(PRNG),它具有指定的周期并保证在该周期内没有冲突。在做了一些研究之后,我遇到了非常有名的LCG,它非常完美。问题是,我无法理解如何正确配置它。这是我当前的实现:

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

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

它说,为了使所有种子值都有一个完整的周期,必须满足以下条件:

  1. cm互质
  2. a-1能被m的所有素因子整除
  3. 如果m是4 的倍数,则a-1是 4 的倍数

13很容易理解和测试。但是2怎么样,我不太明白这意味着什么或如何检查它。那么C呢,它可以为零吗?如果它不为零怎么办?

总的来说,我需要选择 A、C 和 M 以使我的周期为48^5 - 1。M等于周期,我不确定A和C。

4

2 回答 2

14

来自维基百科:

假设c不为零,当且仅当以下情况时,LCG 将具有所有种子值的完整周期:

  1. cm互质,
  2. a -1 可以被m的所有素因子整除,
  3. 如果m是 4 的倍数,则a -1 是 4的倍数。

你说你想要一个 48 5 -1 的周期,所以你必须选择m ≥48 5 -1。让我们尝试选择m =48 5 -1 看看它会把我们带到哪里。如果您希望期间为m,则维基百科文章中的条件禁止您选择c =0 。

请注意,11、47、541 和 911 是 48 5 -1 的质因数,因为它们都是质数并且 11*47*541*911 = 48 5 -1。

让我们来看看这些条件中的每一个:

  1. 为了使cm互质,cm必须没有共同的质因数。因此,选择除 11、47、541 和 911以外的任何素数,然后将它们相乘以选择您的c
  2. 您需要选择a使得a -1 可以被m的所有主要因子整除,即对于您选择的任何x , a = x *11*47*541*911 + 1 。
  3. 您的m不是 4 的倍数,因此您可以忽略第三个条件。

总之:

  • m = 48 5 -1,
  • c = 除 11、47、541 和 911 以外的任何素数乘积(同样,c必须小于m),
  • a = x *11*47*541*911 + 1,对于您选择的任何非负x(同样,a必须小于m)。

这是一个较小的测试用例(在 Python 中),使用周期为 48 2 -1 (其质因数为 7 和 47):

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。)

于 2012-08-23T17:02:40.763 回答
1

根据 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))
于 2018-07-17T21:24:27.523 回答