用于散列的伪随机数生成器，可以采用任何大小的制表符

Question

我正在构建一个用于哈希的伪随机数生成器。我需要使用的算法如下：

• 每次调用制表例程时，将整数R初始化为等于1
• 对于随机数的每次连续调用，设置R=R*5
• 屏蔽除乘积的低阶n+2位以外的所有位，并将结果放入R
• 设置P=R/4并返回

到目前为止，这是我所拥有的，适用于大小为2^n的表，但如何更改它，使它可以容纳任何大小的表？在

    def rand(size,i)
        n = math.log(size,2)
        r = 1
        random_list = []
        mask = (1 << 2+int(n)) - 1
        for n in range(1,size+1):
            r = r*5
            r &= mask
            p = r/4
            random_list = random_list + [p]
        if i == 0: return random_list
        else: return random_list[i-1]

Answer 1

我真的不明白你的代码和你的算法（什么是随机列表？）或者说代码应该如何构造，但我假设它与此类似：

class Rand:
    def __init__(self, n):
        # Initialize an integer R to be equal to 1 every time the tabling routine is called
        self.r = 1
        self.n = n

    def rand(self):
        # On each successive call for a random number, set R = R*5
        self.r *= 5
        # Mask all but the lower order n+2 bits of the product and place the result in R
        self.r = self.r & (pow(2, self.n)-1)
        # Set P = R/4 and return 
        self.p = self.r/4
        return self.p

在这种情况下，为了使它与任何大小的表一起工作，类变为：

^{pr2}$

一个简单的测试证明，当表格大小相同时，结果是相同的：

rnd = Rand(10)
for i in range(0, 10):
    print rnd.rand()

rnd2 = Rand2(pow(2, 10))
for i in range(0, 10):
    print rnd2.rand()

但是，就像我说的，我真的不明白你的代码和你的算法有什么关系。我猜TL太长了，读不下去了，这里用的是模算子。在