代码之家 › 专栏 › 技术社区 › SPWorley

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

knuth prng modulo integer math

SPWorley · 技术社区 · 15 年前

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

如果您想用不同的模计算结果,您当然可以使用不同语言中任意数量的BigInt类。对于值a、b、c<2^32您可以计算64位长整数中的中间值,并使用内置的%运算符将其缩减为正确的answe

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

不幸的是,尽管听说这种特殊情况有一种快速评估方法,但我实际上还没有找到该方法的描述。“这不是用Knuth写的吗?”“这不是维基百科上的某个地方吗?”是我听到的咕哝声。

显然,这是随机数生成器中的一种常见技术,该生成器将a*b mod 2147483647相乘,因为2147483647是一个等于2^31-1的素数。

所以我会问专家们。我找不到任何讨论的这个巧妙的特例乘模方法是什么?

6 回复 | 直到 15 年前

James Ko 8 年前

我认为诀窍如下(我将在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)

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)

phuclv 9 年前

假设你可以把a*b计算为 p*2^N+q . 这可能需要64位计算,或者您可以将a和b拆分为16位部分,并在32位上进行计算。

然后 a*b mod 2^N-1 = p+q mod 2^N-1 自从 2^N mod 2^N-1 = 1

和 a*b mod 2^N+1 = -p+q mod 2^N+1 自从 2^N mod 2^N+1 = -1 .

在这两种情况下,都没有按 2^N-1 或 2^N+1

Jonathan Rupp 15 年前

快速搜索发现以下内容: http://home.pipeline.com/~hbaker1/AB-mod-N.pdf

Pontus Gagge 15 年前

Montgomery reduction (还有其他 descriptions )降低模乘运算的成本。不过,这仍然没有使用N是2的正/负幂的性质。

phuclv 9 年前

你要找的身份是 x mod N = (x mod 2^q)- c*floor(x/2^q) ,鉴于 N = 2^q + c

第9.2.3节:“特殊形式的模量” 在里面 “素数:计算的视角” 理查德·克兰德尔和卡尔·波默兰斯。除了理论之外,它还包含实现上述关系的算法的伪代码。

SPWorley 15 年前

我找到了一份工作 rather extensive page 在这个话题上,我们不仅要讨论算法,还要讨论具体的算法历史问题和解决方案以及人们使用解决方案的方式。