C 中的阶乘程序在 20 之后是错误的 [英] Factorial program in C is wrong after 20

问题描述

它一直工作到 20，但如果输入 21，它返回 1419745...当 21 阶乘实际上是 51090942171709440000.我假设这是因为 unsigned long 最大化，但是这个错误的数字(141...) 来自以及如何让程序计算出较大数字的阶乘?

It works up until 20 but if 21 is entered it returns 1419745... when 21 factorial is actually 51090942171709440000. I'm assuming that this is because of the unsigned long maxing out but where does this wrong number (141...) come from and how can I allow the program to work out the factorial of larger numbers?

#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);
}

推荐答案

这仅回答了您问题的一半(为什么会这样).

This answers only to half of your question (why it works this way).

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

The result you get is 21! mod 2^64. This is because you are using a 64-bit system and 21! is greater than the greatest number that can be stored as unsigned integer on 64 bits.

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

All factorials you compute for values greater than or equal to 21 are wrong; they cannot be represented on 64-bit integers because they are longer than that.

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

You can try to use unsigned long long as the type of the values returned by function fact() (and change into the printf() format string %lu with %llu); it could help but it depends on some factors. It doesn't help on my architecture, for example.

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

You can find out if it can help you by checking the value returned by sizeof(unsigned long long). If if is 8 then you are out of luck. 20 is the largest number for what you can compute factorial on that system.

如果您的目的是计算阶乘，那么您必须使用一个知道如何处理大数的库.但是，如果您需要其他计算的阶乘(例如，对于组合)，那么您可以尝试避免生成大量数字并找到一种方法将每个乘法与除法相匹配.这样，您使用的数字的大小介于 64 位整数的限制之间，并且您可以比 21 走得更远.

If your purpose is to compute factorials then you have to use a library that knows how to handle large numbers. However, if you need factorials for other computations (for example, for combinations) then you can try to avoid generating large numbers and find a way to match each multiplication with a division. This way the magnitude of the numbers you use is between the limits of 64-bit integers and you can go further than 21.

或者您可以使用 double 代替整数，然后您又重新开始工作，但精度有所下降.大浮点数正确存储数字的大小及其第一位数字.最后一位数字丢失.

Or you can use double instead of integers and you are again back in business but with loss of precision. Large floating point numbers store correctly the magnitude of the number and its first digits. The last digits are lost.

我最近很少用 C/C++ 编程，我不能向您推荐一个可以帮助您进行大量计算的库:-(

I didn't program very much in C/C++ recently, I cannot recommend you a library that can help you do computations with large numbers :-(

这篇关于C 中的阶乘程序在 20 之后是错误的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！