algorithm - 有什么简单的方法可以进行 2^32 - 1 运算的模数吗？

Question

我刚刚听说 x mod (2^32-1) 和 x/(2^32-1) 会很简单，但是怎么做呢？

计算公式:

x_n = (x_n-1 + x_n-1/b)mod b。

对于 b = 2^32，很简单，x%(2^32) == x & (2^32-1)；和 x/(2^32) == x >> 32。 (这里的 ^ 不是 XOR)。当 b = 2^32 - 1 时如何做到这一点。

在页面https://en.wikipedia.org/wiki/Multiply-with-carry .他们说“模数 2^32 − 1 的算术只需要对 2^32 的算术进行简单的调整”。那么什么是“简单调整”呢？

Answer 1

(此答案仅处理 mod 情况。)

我假设 x 的数据类型超过 32 位(这个答案实际上适用于任何正整数)并且它是正数(负数只是 - (-x mod 2^32-1)), 因为如果它最多 32 位，问题可以通过

x mod (2^32-1) = 0 if x == 2^32-1, x otherwise
x / (2^32 - 1) = 1 if x == 2^32-1, 0 otherwise

我们可以以 2^32 为基数编写 x，其中包含数字 x0, x1, ..., xn。所以

  x = x0 + 2^32 * x1 + (2^32)^2 * x2 + ... + (2^32)^n * xn

这使得我们在计算模数时答案更加清晰，因为 2^32 == 1 mod 2^32-1。也就是

  x == x0 + 1 * x1 + 1^2 * x2 + ... + 1^n * xn (mod 2^32-1)
    == x0 + x1 + ... + xn (mod 2^32-1)

x mod 2^32-1 与基数 2^32 数字之和相同! (我们还不能删除 mod 2^32-1)。我们现在有两种情况，要么总和在 0 到 2^32-1 之间，要么更大。在前者，我们完成了；在后面，我们可以重复直到我们得到 0 和 2^32-1 之间。获取基数为 2^32 的数字很快，因为我们可以使用按位运算。在 Python 中(这不处理负数):

def mod_2to32sub1(x):
    s = 0 # the sum

    while x > 0: # get the digits
        s += x & (2**32-1)
        x >>= 32

    if s > 2**32-1:
        return mod_2to32sub1(s)
    elif s == 2**32-1:
        return 0
    else:
        return s

(这非常容易推广到 x mod 2^n-1，事实上，您只需在这个答案中用 n 替换任何出现的 32。)

(编辑:添加了 elif 子句以避免 mod_2to32sub1(2**32-1) 上的无限循环。EDIT2:替换了 ^ 与 **...哎呀。)