math - 快速计算(a * b)mod c，其中c = 2 ^ N + -1

Question

在32位整数数学中，加法和乘法的基本数学运算隐式地计算为mod 2 ^ 32，这意味着您的结果将是加法或乘法的最低位。

如果要使用不同的模数计算结果，则可以使用不同语言的任意数量的BigInt类。对于值a，b，c <2 ^ 32，您可以使用64位长整数计算中间值，并使用内置的％运算符将其减小为正确的整数。

但是有人告诉我，当C的格式为(2 ^ N)-1或(2 ^ N)+1时，有一些特殊技巧可以有效地计算a * b mod C，而无需使用64位数学运算或一个BigInt库，并且比任意模数评估更有效，并且还可以正确计算大小写，如果包括中间乘法，则通常会溢出32位int。

不幸的是，尽管听说这种特殊情况具有快速评估方法，但实际上我还没有找到该方法的描述。 “那不是在克努斯吗？” “这不是维基百科上的某个地方吗？”是我听到的喃喃自语。

显然，这是随机数生成器中的一种常用技术，它会乘以a * b mod 2147483647，因为2147483647是等于2 ^ 31 -1的质数。

所以我会问专家。我找不到任何讨论的这个聪明的特殊情况乘法与mod方法是什么？

Answer 1

我认为诀窍如下(我将在基础10中进行操作，因为它比较容易，但是原理应该成立)

假设您要乘a*b mod 10000-1，然后

a = 1234 = 12 * 100 + 34
b = 5432 = 54 * 100 + 32

现在a*b = 12 * 54 * 10000 + 34 * 54 * 100 + 12 * 32 * 100 + 34 * 32

12 * 54 * 10000 =  648 * 10000
34 * 54 * 100   = 1836 * 100
12 * 32 * 100   =  384 * 100
34 * 32         = 1088

自x * 10000 ≡ x (mod 10000-1) [1]起，第一项和最后一项变为648 + 1088。第二和第三项是“技巧”的来源。请注意:

1836 = 18 * 100 + 36
1836 * 100 ≡ 18 * 10000 + 3600 ≡ 3618 (mod 10000-1).

这实质上是一个循环移位。给出648 + 3618 + 8403 + 1088的结果。还要注意，在所有情况下，相乘的数字均<10000(因为a <100和b <100)，因此，如果您只能同时将2位数字相乘，则可以计算得出，然后添加它们。

在二进制文件中，它将类似地工作。

以a和b开头，均为32位。假设您想将它们乘以mod 2 ^ 31-1，但是您只有一个16位的乘法器(给定32位)。该算法将是这样的:

 a = 0x12345678
 b = 0xfedbca98
 accumulator = 0
 for (x = 0; x < 32; x += 16)
     for (y = 0; y < 32; y += 16)
         // do the multiplication, 16-bit * 16-bit = 32-bit
         temp = ((a >> x) & 0xFFFF) * ((b >> y) & 0xFFFF)

         // add the bits to the accumulator, shifting over the right amount
         total_bits_shifted = x + y
         for (bits = 0; bits < total_bits_shifted + 32; bits += 31)
             accumulator += (temp >> (bits - total_bits_shifted)) & 0x7FFFFFFF

         // do modulus if it overflows
         if (accumulator > 0x7FFFFFFFF)
             accumulator = (accumulator >> 31) + (accumulator & 0x7FFFFFFF);

已经晚了，所以其中的累加器部分可能无法正常工作。我认为原则上是正确的。有人可以随意编辑以使其正确。

展开后，这也非常快，我猜这就是PRNG的用途。

[1]:x * 10000≡x *(9999 + 1)≡9999 * x + x≡x(mod 9999)