Генератор псевдослучайных чисел для хеширования, который может принимать таблицу любого размера - PullRequest
Новая
       7

Генератор псевдослучайных чисел для хеширования, который может принимать таблицу любого размера

1 голос
/ 01 июля 2011

Я создаю генератор псевдослучайных чисел для хеширования.Алгоритм, который мне нужно использовать, следующий:

  • Инициализировать целое число 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]

1 Ответ

0 голосов
/ 13 июля 2011

Я не совсем понял, как ваш код связан с вашим алгоритмом (что такое random_list?) Или как код должен быть структурирован, но я предполагаю, что это что-то похожее на это: 

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

Вв этом случае, чтобы заставить его работать с таблицей любого размера, класс становится следующим: 

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

    def rand(self):
        # On each successive call for a random number, set R = R*5
        self.r *= 5
        # A bit mask is essentially a modulus operation, which is what we do instead
        self.r = self.r % self.tableSize
        # Set P = R/4 and return
        self.p = self.r/4
        return self.p

Простой тест подтверждает, что результат одинаков, когда размеры таблицы идентичны: 

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; dr здесь использует оператор модуля вместо битовой маски.

...