快速算法计算大数 n! mod 2³²

Question

我想计算 N! mod 2³² 的确切值。N 可以高达 2³¹。

任何语言都可以，但我希望得到详细的算法说明。 时间限制为 <1 秒。

- user2129227

---

这个问题有实际应用吗？数字(2^31)!非常巨大。请查看https://dev59.com/VHM_5IYBdhLWcg3waiiJ以获取更多讨论。 - Nick Mitchinson

一个（标准桌面）计算机在不到一秒钟的时间内甚至无法写下那么大的数字。 - Andrew

@Andrew：大约40亿，其实并不是那么巨大。 - BlueRaja - Danny Pflughoeft

@BlueRaja-DannyPflughoeft，我说的是(2^32)!而不是2^32。前者包含超过十亿位数字。 - Andrew

在正常情况下（即p为质数时），计算n! mod p时，每次乘法后都要进行模运算；这样处理的数字永远不会大于p。有关更多信息，请参阅我在此处的评论：（https://dev59.com/MWkw5IYBdhLWcg3wrsdS#9728079）。 - BlueRaja - Danny Pflughoeft

Answer 1

在Python中：

if n > 33:
  return 0
else
  return reduce(lambda x, y: x*y, range(1, n+1)) % 2**32

理由：

我们知道34!可以被2³²整除，因为在下列序列中：

1 * 2 * 3 * 4 * ... * 34

有：

17 multiples of 2
 8 multiples of 4
 4 multiples of 8
 2 multiples of 16
 1 multiple  of 32
--
32 multiplications by 2

这是每个更大的阶乘的因子，所以所有更大的数都模2³²为0。

对于小的N值，如果没有大数计算，您可以对每个乘法进行模2³²运算，或者您可以预先计算阶乘中的2的幂次方，这很容易计算（见上文）。

- rici

---

模数2 ** 32部分仅在Python支持bigint math时需要。在大多数正常的语言中，您只需要对32位类型进行直接乘法运算，结果已经自动模2³²。 - phuclv

Answer 2

通常情况下可以通过计算阶乘（将数字1、2、3等相乘）并在每次乘法后执行取模操作来得到小值的N的结果。

对于较大的N，同样可以采用相同的方法。很快，您的中间结果将为0，然后您可以立即停止循环并返回0。停止的点将相对较快：当N == 64时，结果已经是0，因为1..64的乘积包含32个偶数，因此可被2^32整除。实际上，使得结果为0的最小值N将小于64。

- interjay

---

实际上，当你得到0时，N的最小值将会小于64*34，正如rici和Joni在同一天所说的那样，如果以后的话。 - greybeard

Answer 3

一般来说，您可以在大多数编程语言中使用整数类型（int、long）实现对小二次幂取模的算法，而无需使用大数或模数缩减。对于模 2^32，您将使用一个 32 位 int。"整数溢出"处理模算术。 在这种情况下，由于只有 34 个不同的结果，查找表可能比计算阶乘更快，假设阶乘被使用得足够频繁以使表被加载到 CPU 缓存中。执行时间将以微秒为单位测量。

- Joni

Answer 4

当乘以任意长度的两个数字时，低位总是精确的，因为它不依赖于高位。这就是2-进制或p-进制乘法的工作原理。基本上，a×b mod m = [(a mod m)×(b mod m)] mod m，所以要计算N! mod m，只需执行以下操作。

1×2×...×N mod m = (...(((1×2 mod m)×3 mod m)×4 mod m)...)×N mod m

模2的n次方是一个特殊情况，因为使用AND操作很容易得到模数。模2的32次方更加特殊，因为在C语言和大多数类C语言中，所有无符号操作都会对32位无符号类型进行模2的32次方的缩减。

因此，你只需要将数字乘以一个两倍宽度的类型，然后再用2的32次方减1进行AND操作，就可以得到模数。

uint32_t p = 1;
for (uint64_t i = 1; i <= n && p /* early exit because product = 0 */; i++)
    p = uint32_t(p*i); // or p = p*i & 0xFFFFFFFFU;
return p;

- phuclv

Answer 5

计算模数是一项非常快速的操作，特别是2的幂次方的模数。相比之下，乘法代价很高。

最快的算法将阶乘的因子分解为质数（由于数字小于33，因此非常快）。通过在每次乘法之间取模，并从大数开始将它们全部相乘来获得结果。

例如：要计算10！mod 2³²：使用de Polignac的公式获取10！的质因数，这会给你：

10！= 7 * 5 * 5 * 3 * 3 * 3 * 3 * 2 ...

这比基本算法更快，因为计算(29！mod 2³²) X 30比乘以5、3和2，并在每次之间取模要困难得多。

- bruce_ricard

---

这实际上会慢很多。首先，在因式分解方面有很多额外的工作，然后需要进行更多的乘法运算。我不知道你为什么认为每次乘以5、3和2并执行模运算比乘以30更快。 - interjay

再次强调，要进行因数分解的数字非常小，所以很容易分解。但是要进行乘法的数字很大，所以很难。显然，如果您可以减少中间结果的大小，则会更快。尝试计算67 * 4 mod 100。最好的方法是：67 * 2 = 134，34 * 2 = 68。通过这样做，我避免了将134乘2的运算。 - bruce_ricard

乘法并不是“一种操作”，尽管复杂性理论试图这样教导。是的，这个算法执行的乘法比第一个算法多，但每个乘法的复杂度要小得多。 - bruce_ricard

@double_squeeze：实际上，您可以完全省略因子2，正如我在我的答案中提到的。然而，对于n < 34，这几乎不值得：我可以在我的普通笔记本电脑上计算整个范围，包括Python启动，仅用32毫秒。 - rici

是的，我同意，对于这个小例子来说，这并不值得。但是假设你没有可用的计算机，并且需要手动完成它，那么你肯定想这样做。 - bruce_ricard

@double_squeeze：如果你是手动计算，你会想要使用http://en.wikipedia.org/wiki/De_Polignac%27s_formula而不是尝试一个一个地分解所有这些数字，无论它们有多小，这都将非常低效。 - rici