C 中的阶乘程序在 20 之后是错误的

Question

它一直工作到 20，但如果输入 21，它会 returns 1419745... 当 21 的阶乘实际上是 51090942171709440000 时。我假设这是因为 unsigned long 最大化但这是在哪里错误的数字 (141...) 来自哪里，我怎样才能让程序计算出更大数字的阶乘？

#include <stdio.h>

unsigned long fact(unsigned long input);

int main()

{

    int input;

    printf("Enter an integer to find the factorial of: ");
    scanf(" %d", &input);

    printf("The Factorial of %d = %lu\n" , input, fact(input)); 

    return 0;
}

unsigned long fact(unsigned long input)
{
    if (input == 0)
            return 1;
    else    
        return input * fact(input - 1);
}

Answer 1

数字来自溢出。无符号算术以模（该类型的最大值）完成，所以一点数学应该可以解释为什么你得到你做的结果。

有符号整数溢出的结果是未定义的，所以如果你一直使用有符号整数，你可能会得到任何东西（尽管它在很多系统上可能完全相同）

Answer 2

这只回答了你问题的一半（为什么它会这样）。

您得到的结果是 21! mod 2^64。这是因为您使用的是 64 位系统，并且 21! 大于可以在 64 位上存储为无符号整数的最大数。

您为大于或等于 21 的值计算的所有阶乘都是错误的；它们不能用 64 位整数表示，因为它们比 64 位整数长。

你可以尝试使用unsigned long long作为函数返回值的类型fact()（并改为printf()格式字符串%lu和%llu);它可能会有所帮助，但这取决于某些因素。例如，它对我的架构没有帮助。

您可以通过检查 sizeof(unsigned long long) 返回的值来了解它是否可以帮助您。如果 if 是 8 那么你就不走运了。 20 是您可以在该系统上计算阶乘的最大数。

如果您的目的是计算阶乘，那么您必须使用知道如何处理大数的库。但是，如果其他计算需要阶乘（例如 combinations），那么您可以尽量避免生成大数，并找到一种方法将每个乘法与除法相匹配。这样，您使用的数字的大小在 64 位整数的限制之间，您可以比 21.

走得更远

或者您可以使用 double 代替整数，这样您就可以重新开始工作，但精度会下降。大浮点数正确存储数字的大小及其第一位数字。最后一位数字丢失了。

我最近没怎么用C/C++编程，我不能向你推荐一个可以帮助你做大数计算的库:-(

C 中的阶乘程序在 20 之后是错误的

Factorial program in C is wrong after 20

c

unsigned

factorial

long-integer