快速乘法和模运算

Question

我需要计算：

x=(x*a+b)/2 % 2**128

很多次。 x,a,b 是 128 位数字（随机选择）。如何以最快的方式做到这一点？我想到了 numpy，它能以某种方式提供帮助吗？现在大约慢了100倍......有没有办法做得更快？当然它必须单独完成，一步一步，算法比这个更复杂（a，b在几步之后改变），所以我们不能在这里尝试做任何数学或快速求幂。

更完整的代码示例：

a=333
b=555
c=777
d=999
x=12345

for i in range(128):
    if x % 2 == 1:
        x=((x * a + b)/2) % 340282366920938463463374607431768211456
    else:
        x=(x * c/2 + d) % 340282366920938463463374607431768211456
    print(x)

Answer 1

如果这是整数运算，您应该使用整数除法。这将避免不必要的浮点数转换。此外，对模数使用按位运算可能会更快。

mask128 = 2**128 - 1

x = ( (x*a+b)//2 ) & mask128

Answer 2

你会遇到一些麻烦，因为你做的事情本质上是低效的 operations:128 位整数不是大多数 Python 实现的本机，并将招致 longint 操作的惩罚。但是，如果您使用移位和掩码操作而不是除法和取模 2 的幂，则可以将执行时间减少大约 20%:

import timeit

a=333
b=555
c=777
d=999
x=12345
two_128 = 2 ** 128
mask = two_128 - 1

def rng_orig(x):
    for i in range(128):
        if x % 2 == 1:
            x=((x * a + b)/2) % two_128
        else:
            x=(x * c/2 + d) % two_128


def rng_bit(x):
    for i in range(128):
        if x & 1:
            x=((x * a + b) >> 1) & mask
        else:
            x=(x * (c >> 1) + d) & mask


repeat = 100000
print(timeit.timeit(lambda: rng_orig(x), number = repeat))
print(timeit.timeit(lambda: rng_bit (x), number = repeat))

计时结果：

5.1968478000000005
3.965898900000001

快速乘法和模运算

Fast multiplication and modulo operation

python

python-2.7