2 整数区间非幂的混合函数

Question

我正在寻找一个混合函数，它给定区间 <0, n) 中的整数 returns 相同区间中的随机整数。区间大小 n 通常是 2 的复合非幂数。我需要一对一的功能。它只能使用 O(1) 内存，强烈推荐 O(1) 时间。我不太关心输出的随机性，但在视觉上它应该看起来足够随机（见下一段）。

我想将此函数用作实时渲染器中的像素改组步骤，以 select 渲染像素的顺序（输出将在固定时间后显示，如果未完成但这给了我一个嘈杂但快速的部分预览）。间隔大小 n 将是渲染中的像素数（n = 1920*1080 = 2073600 是一个典型值）。该函数必须是一对一的，这样我才能确定每个像素在完成时都只渲染一次。

我查看了 hash prospector 使用的可逆构建块，但这些大多特定于 2 次幂范围。

我能想到的唯一其他方法是乘以大质数，但它并没有给出特别好的随机输出。

这里还有哪些其他选项？

Answer 1

这是一个基于原根思想的解决方案modulo a prime:

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

为了补充细节，this paper包含一个table，它给出了一系列素数（所有素数都接近2的各种幂）和相应的原根被选择以便它们产生具有良好统计特性的生成器。这是 table 的一部分，编码为 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 的精确幂）。在实践中，这种方法与您的 "multiply by a large prime" 方法没有根本区别，但在这种情况下，因子的选择更加谨慎，而且有时需要多次乘法会增加明显的随机性。

2 整数区间非幂的混合函数

Mixing function for non power of 2 integer intervals

math

hash

unsigned-integer