如何确定程序使用unsigned long long计算阶乘的最大值？

Question

如何在C中编写一个适当的算法来确定程序可以使用的最大值计算因子unsigned long long int？

我的例子不能正常工作.使用Linux/64bit和GCC,它给了我65次迭代.

#include <stdio.h>

int main() {
    unsigned long long int num, i;
    unsigned long long int factorial = 1;
    num = 1;
    for (i = 1; i <= num; i++) {
        factorial = factorial * i;
        num++;
        if (factorial <= 0) {
           printf("\nMaximum number is: %d\n", i - 1);
           break;
        }
    }
}

Answer 1

您的程序无法正常运行,因为:

• factorial总是>= 0因为它有一个无符号类型.一旦你将足够的时间乘以2或2的倍数,程序停止的唯一原因就是factorial最终0.
• 你无法通过测试结果值来可靠地检测溢出:无符号算术以2的值为单位的幂值进行模数运算,因此你可以将结果与前一个因子进行比较,如果它更小则可以中断.但请注意,带符号的算术溢出实际上具有未定义的行为,因此测试结果变为负数总是错误的.

更可靠的方法是在执行乘法之前检查溢出:

#include <limits.h>
#include <stdio.h>

int main(void) {
    unsigned long long int i, factorial;
    for (i = factorial = 1; factorial <= ULLONG_MAX / i; i++) {
        factorial = factorial * i;
    }
    printf("\nMaximum number is: %llu! = %llu\n", i - 1, factorial);
    return 0;
}

输出:

Maximum number is: 20! = 2432902008176640000