计算C中的大数因子

Question

在我的C代码中,我想计算1到100范围内的数字的阶乘.对于小数字,该函数可以工作,但对于更大的数字,例如100!它返回不正确的结果.有什么方法可以处理C中的大数阶因子？我正在使用的编译器是gcc v4.3.3.我的代码如下:

#include <stdio.h>
#include <math.h>

double print_solution(int);

int main(void)
{
        int no_of_inputs,n ;

        int ctr = 1;

        scanf("%d",&no_of_inputs); //Read no of inputs

        do
        {
                scanf("%d",&n); //Read the input

                printf("%.0f\n",print_solution(n));

                ctr++;  

        }while(ctr <= no_of_inputs);


        return 0;       
}

double print_solution(int n)
{
        if(n == 0 || n == 1)
                return 1;
        else
                return n*print_solution(n-1);


}

Answer 1

没有标准C数据类型可以准确处理大到100的数字!如果要通过库或自己完成任意精度整数运算,这是唯一的选择.

如果这只是一些爱好项目,我建议你自己尝试一下.这是一种有趣的运动.如果这与工作相关,请使用预先存在的库.

您通常会获得的最大C数据类型是64位整数.100!大约是¹⁰¹⁵⁷,它将500位的较好部分准确地存储为整数.

Answer 2

100阶乘是巨大的,准确地说是93326215443944152681699238856266700490715968264381621468592963895217 59999322991560894146397615651828625369792082722375825118521091686400 00000000000000000000.

也许你应该使用像GMP这样的bignum库.它有很好的文档,非常一致的界面,速度,如果你在Linux上你的发行版可能有一个包(我认为我默认安装它)

Answer 3

要近似计算大数的阶乘,您可以这样:

n! =  n * (n-1)!
so log(n!) = log(n) + log(n-1!)

现在你可以使用动态编程来计算log(n!)并计算
n!as(base)^(log-value)

Answer 4

如果您不想使用bigint库,那么使用stdlib最好的方法是使用long double和tgammal()来自math.h:

long double fact(unsigned n)
{
    return tgammal(n + 1);
}

这将使您100!在x86(即80位long double)上获得18位小数的精度.

确切的实现也不是那么复杂:

#include <math.h>
#include <stdio.h>
#include <string.h>

void multd(char * s, size_t len, unsigned n)
{
    unsigned values[len];
    memset(values, 0, sizeof(unsigned) * len);
    for(size_t i = len; i--; )
    {
        unsigned x = values[i] + (s[i] - '0') * n;
        s[i] = '0' + x % 10;
        if(i) values[i - 1] += x / 10;
    }
}

void factd(char * s, size_t len, unsigned n)
{
    memset(s, '0', len - 1);
    s[len - 1] = '1';
    for(; n > 1; --n) multd(s, len, n);
}

int main(void)
{
    unsigned n = 100;
    size_t len = ceill(log10l(tgammal(n + 1)));
    char dstr[len + 1];
    dstr[len] = 0;
    factd(dstr, len, n);
    puts(dstr);
}

Answer 5

每个人都在告诉你正确的答案,但还有几点.

1. 你最初使用double来获得更宽范围的想法是行不通的,因为double不能精确地存储这些数据.它可以进行计算,但需要进行大量舍入.这就是bigint库存在的原因.

2. 我知道这可能是教程或示例网站的一个例子,但是做无限递归会在某些时候咬你.您有一个基本上是迭代过程的递归解决方案.您将了解为什么当您尝试使用较大的值运行程序时,此站点的名称是什么(尝试10000).

一种简单的迭代方法如下

  int answer, idx;

  for (answer = 1, idx = 1; idx <= no_of_inputs; idx++ ) {
    answer = answer * idx;
  }
  printf("Factorial of %3d =  %d\n", no_of_inputs, answer);

Answer 6

我猜那是因为你溢出了 int 范围，最多可达大约。20亿。如果使用 unsigned int，最多可以获得 40 亿，但除此之外，还必须使用bigint 库。