2个整数区间的非功率混合功能

Question

我正在寻找一个混合函数，它给出一个间隔<0的整数，n）从同一个区间返回一个随机的整数。区间大小n通常是2个数的复合非幂。我需要这个功能是一对一的。它只能使用O（1）存储器，O（1）时间是强烈优选的。我并不太关心输出的随机性，但在视觉上它看起来应该是随机的（参见下一段）。

我想在实时渲染器中使用此函数作为像素混洗步骤来选择渲染像素的顺序（输出将在固定时间后显示，如果还没有完成，这会给我一个嘈杂但快速的部分预习）。间隔大小n将是渲染中的像素数（n = 1920 * 1080 = 2073600将是典型值）。该函数必须是一对一的，以便我可以确保每个像素在完成时只渲染一次。

我看过hash prospector使用的可逆构建块，但这些构建块主要针对2个范围的功率。

我能想到的唯一另一种方法是乘以大素数，但它不会给出特别好的随机输出。

这里有什么其他选择？

Answer 1

这是一个基于模数为素数的原始根的思想的解决方案：

如果a是原始根mod p，则函数g(i) = a^i % p是非零元素的排列，其小于p。这对应于Lehmer prng。如果n < p，你可以得到0, ..., n-1的排列如下：给定i在该范围内，首先加1，然后重复乘以a，取结果mod p，直到你得到一个<= n元素，此时你返回结果 - 1。

为了填写细节，this paper包含一个表，该表给出了一系列素数（所有素数都接近2的各种幂）和相应的原始根，这些根被选择以便它们产生具有良好统计特性的生成器。这是该表的一部分，编码为Python字典，其中键是素数，原始根是值：

d = {32749: 30805,
     65521: 32236,
     131071: 66284,
     262139: 166972,
     524287: 358899,
     1048573: 444362,
     2097143: 1372180,
     4194301: 1406151,
     8388593: 5169235,
     16777213: 9726917,
     33554393: 32544832,
     67108859: 11526618,
     134217689: 70391260,
     268435399: 150873839,
     536870909: 219118189,
     1073741789: 599290962}

鉴于n（在一定范围内 - 如果您需要扩大该范围，请参阅论文），您可以找到最小的p：

def find_p_a(n):
    for p in sorted(d.keys()):
        if n < p:
            return p, d[p]

一旦你知道n和匹配的p,a，以下函数是0 ... n-1的排列：

def f(i,n,p,a):
    x = a*(i+1) % p
    while x > n:
        x = a*x % p
    return x-1

快速测试：

n = 2073600
p,a = find_p_a(n) # p = 2097143, a = 1372180
nums = [f(i,n,p,a) for i in range(n)]
print(len(set(nums)) == n) #prints True

f()的平均乘法次数是p/n，在这种情况下是1.011并且永远不会超过2（或者因为p不是2的精确幂而略大）。在实践中，这种方法与你的“乘以大素数”方法并没有根本的不同，但在这种情况下，更谨慎地选择因子，并且有时需要多于1次乘法以增加表观随机性。