大数阶乘取模大质数

Question

我需要计算一个大数（小于等于1,000,000）的阶乘，并且需要对1000000007取模得出结果。我写了下面的代码，但是在运行时会出现错误（test.exe已停止工作）。它只适用于小数字。

long long unsigned modulo(long long unsigned nr){
    return nr % 1000000007;
}

long long unsigned fact(long long unsigned nr){
    if(nr)return modulo(nr * fact(nr - 1));
    else return 1;
}

更新1：

long long unsigned fact(long long unsigned nr){
    long long unsigned r = nr;
    while(--nr){
        r = modulo(r * nr);
    }
    return r;
}

- Zack

---

使用模算术modmul代替*，避免N次递归以避免堆栈崩溃/溢出，并尽可能使用快速阶乘（例如，这个https://dev59.com/YXXYa4cB1Zd3GeqP-9ru#18333853是我的，但需要表格中的质数直到N，但还有更多...） - Spektre

不要忘记，你可以在O(sqrt(n))的时间内计算它。 - Tacet

Answer 1

这是因为您的实现使用了递归。对于小数字，它可以正常工作，但对于大数字，它会溢出堆栈。

这行

if(nr)return modulo(nr * fact(nr - 1));

创建nr个堆栈帧。由于堆栈空间非常有限，输入大量数字会导致堆栈溢出。

更改您的实现方式，使用迭代计算阶乘以避免崩溃。

一旦您完成了解决崩溃的问题，请处理数字溢出。不要在计算阶乘后再计算取模，而是在计算的每一步应用取模运算。

- Sergey Kalinichenko

---

那样做没有帮助。无论如何，计算1000000！都会溢出，无论是否使用递归。 - SomeWittyUsername

我认为按照问题中所写的代码没有任何数字溢出问题。 - Pascal Cuoq

@PascalCuoq +1，忽略我的评论，它对这段代码不正确。 - SomeWittyUsername

有没有更快的方法？我在一个问题的算法中使用这段代码，但是当我尝试测试它时，测试器会显示超出时间限制（内存限制为8192 kbytes，执行时间限制为0.7秒 - 在执行中我正在调用fact()三次）。 - Zack

@Zack 这里有一个 ideone 上的演示，可以在 0.34 秒内计算出 10,000,000 的答案。 - Sergey Kalinichenko

Answer 2

最坏情况下，您将生成1,000,000个递归调用，每个调用都需要一部分堆栈来记录其激活记录。

堆栈大小通常限制为1MB，一旦每个调用使用2B（实际上，您将使用更多的字节，通常是32B或更多），您将使用超过1MB的堆栈，导致段错误。

- Stefano Sanfilippo

Answer 3

/* C code to implement factorial of large number */
#include<stdio.h>
int main(){
int a[200],index,i,j,n,tmp,counter=0;
printf("\n Enter the no : ");
scanf("%d",&n);
a[0]=1;
index=0;
//Calculation Loop
for(j=n;j>=2;j--){
tmp=0;
/* This Loop is used to multiply the numbers */
for(i=0;i<=index;i++){
    tmp=(a[i]*j)+tmp; // here tmp is carry digir which should be added to next multiplied value
    a[i]=tmp%10; // Extracting last digit of number
    tmp=tmp/10; // Extracring carry digir
}
// This loop helps you to extract digits from last calculated carry digits
/* Supposse last carry digit is 25 then we must extract each digit( 5 & 2) and store it into array */
while(tmp>0){
    a[++index]=tmp%10;
    tmp=tmp/10;
}
}
//Loop to print output of calculated factorial
printf("\n The factorial of %d is : \n",n);
for(i=index;i>=0;i--)
printf("%d",a[i]);
return 0;
}

- user3818318