有人能解释一下计算大阶乘的算法吗？

Question

有人能解释一下计算大阶乘的算法吗？

23

我发现了一个用于计算大整数阶乘（可以达到100位数）的程序……有人能够解释一下这个算法中使用的基本思想吗？我只需要了解计算阶乘所实现的数学知识。

#include <cmath>
#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{

      unsigned int d;

      unsigned char *a;

      unsigned int j, n, q, z, t;

      int i,arr[101],f;

      double p;


    cin>>n;
    p = 0.0;
    for(j = 2; j <= n; j++)
        p += log10(j);
    d = (int)p + 1;
    a = new unsigned char[d];
    for (i = 1; i < d; i++)
        a[i] = 0; //initialize
    a[0] = 1;
    p = 0.0;
    for (j = 2; j <= n; j++)
    {
        q = 0;
        p += log10(j);
        z = (int)p + 1;
        for (i = 0; i <= z/*NUMDIGITS*/; i++)
        {
            t = (a[i] * j) + q;
            q = (t / 10);
            a[i] = (char)(t % 10);
        }

    }
    for( i = d -1; i >= 0; i--)
        cout << (int)a[i];
    cout<<"\n";
    delete []a;

return 0;
}

- Vaibhav

3

你是从哪里获取到这个算法的？为了恰当地归属权，你应该始终包含这些信息，但这也可能有助于回答问题。 - Bill the Lizard

11

如果这不是为什么编写易读代码是一个巨大优势的典型例子，那我就不知道还有什么了。这段代码不应该解释，而应该重新编写。 - Lasse V. Karlsen

这个算法叫什么名字？ - mahendiran.b

依我之见，这里有一个 bug。应该是 a = new unsigned char[d+1];。 - user31264

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jason · Accepted Answer

请注意，这里需要说明的是：

n! = 2 * 3 * ... * n

< p > 以便 < /p>

log(n!) = log(2 * 3 * ... * n) = log(2) + log(3) + ... + log(n)

这很重要，因为如果k是正整数，那么log(k)的上限就是k在十进制中的位数。因此，这段代码计算了n!的位数。

p = 0.0;
for(j = 2; j <= n; j++)
    p += log10(j);
d = (int)p + 1;

然后，这些代码会分配空间来保存 n! 的数字：

a = new unsigned char[d];
for (i = 1; i < d; i++)
    a[i] = 0; //initialize

然后我们只需要使用小学阶段的乘法算法。

p = 0.0;
for (j = 2; j <= n; j++) {
    q = 0;
    p += log10(j);
    z = (int)p + 1;
    for (i = 0; i <= z/*NUMDIGITS*/; i++) {
        t = (a[i] * j) + q;
        q = (t / 10);
        a[i] = (char)(t % 10);
    }
}

外层循环从2到n运行，因为在每个步骤中，我们将用j乘以a中表示当前结果的数字。内层循环是小学乘法算法，我们在其中将每个数字乘以j，并在必要时将结果进位到q中。

嵌套循环之前的p = 0.0和循环内的p += log10(j)只是跟踪到目前为止答案中的数字数量。

顺便提一下，我认为程序的这部分存在一个错误。循环条件应该是i < z而不是i <= z，否则当z == d时，我们肯定会写过a的末尾。因此，请将其替换。

for (i = 0; i <= z/*NUMDIGITS*/; i++)

通过

for (i = 0; i < z/*NUMDIGITS*/; i++)

然后我们只需打印出数字即可。

for( i = d -1; i >= 0; i--)
    cout << (int)a[i];
cout<<"\n";

并释放已分配的内存

delete []a;