预计阶乘溢出

我在想如何预测下一次迭代是否会在计算阶乘F时产生整数溢出？预计阶乘溢出

假设在每次迭代中我有一个int I，最大值是MAX_INT。

这听起来像一个功课，我知道。不是。这只是我问自己“愚蠢”的问题。

补遗

我虽然约，给定数目的位（宽度的整数可以采取，在比特），我可以向上舍余数2的下一个功率，并且如果移位，以检测左边会超过BITS。但算法如何呢？

2010-06-06 Flavius

这不一定是你的问题的答案，所以我不会发布它是这样的，但它可能是最有效的硬编码这些值到您的程序。这不像是阶乘的价值会发生变化，而且如果像这样的查找设置很好，你可以在恒定时间内看到阶乘是否会溢出。 – avpx 2010-06-06 21:54:17

@avpx：在C++中，您甚至可以使用模板在编译时以便携方式生成适合该编译器的整数大小的表和查找代码。 – Omnifarious 2010-06-06 22:18:13

替代提示：

a * b ≤ MAX_INT

相当于

a ≤ MAX_INT/b

若B> 0

2010-06-06 21:55:23 kennytm

Duh！我无法想象为什么这种方法不会发生在我身上！ – swestrup 2010-06-06 23:53:24

阶乘是一系列乘法运算，保持乘法结果所需的位数是两个被乘数位的总和。因此，保持结果中使用了多少位的总数以及保存您所乘数值所需的当前位数。如果这大于剩余位数，您即将溢出。

2010-06-06 21:53:48 swestrup

我会咀嚼它，但我会接受KennyTM的答案，因为它在数学上更直观。 @SO用户：请为此投票，这是一个很酷的答案！ – Flavius 2010-06-06 21:59:24

......但这只是非常粗略的举例：2 * 2 * 2 * 2 = 16个4位值的乘法，每个2位产生一个4位值，但是3 * 3 * 3 * 3 = 81，也是4个值的乘法，每个2位，产生一个6位值。 Moron的解决方案更加准确。 – Curd 2010-06-06 22:14:19

这种天真的实现会导致你低估你何时会溢出。因子在乘法的最后阶段从大到小逐渐变好，所以当溢出之前的最后一个阶乘靠近MAX_INT时，这只会让你陷入困境，但它可以。 4代表3位表示和3代表2，但12只需要4位表示，而不是5. – Omnifarious 2010-06-06 22:15:09

如果你这么远m = (n-1)!和你有关n乘，你可以通过检查

m <= MAX_INT/n

2010-06-06 21:57:27

LN（N！）= N * LN（N） - N + LN（2 * PI * N）/ 2 + O（1/N）

并且会相当准确。

你实际上并不需要去尝试繁殖等。当然，这并不直接回答你问的问题，但鉴于你只是好奇，希望这有助于。

2010-06-06 22:02:52

+1这就是我想要回答的。并且：值的日志与表示值所需的位数成正比。所以这就是Flavius需要的。 – Curd 2010-06-06 22:06:07

这也是我的第一个想法，但我不记得近似公式的名字。愚蠢的是，它和我的名字一样。： - / – swestrup 2010-06-06 23:52:45

回答