对于c = 2 ^ N + -1,快速计算(a*b)mod c

Question

在32位整数数学中,add和multiply的基本数学运算隐式计算mod 2 ^ 32,这意味着你的结果将是add或multiply的最低位.

如果要使用不同的模数计算结果,您当然可以使用不同语言的任意数量的BigInt类.对于值a,b,c <2 ^ 32,您可以计算64位长整数的中间值,并使用内置的%运算符减少到右侧的答案

但是我被告知,当C的形式为(2 ^ N)-1或(2 ^ N)+1时,有一些特殊的技巧可以有效地计算a*b mod C,它们不使用64位数学或一个BigInt库,非常高效,比任意模数评估更有效,并且还可以正确计算在包含中间乘法时通常会溢出32位int的情况.

不幸的是,尽管听说这种特殊情况有快速的评估方法,但实际上我还没有找到该方法的描述."那不是在Knuth吗？" "这不就是维基百科上的某个地方吗？" 是我听到的咕噜声.

它显然是随机数生成器中的常用技术,其执行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(因为<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)