大数阶因数模数大素数

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

Answer 1

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

这条线

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

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

更改您的实现以使用factorial的迭代计算来避免崩溃。

完成崩溃后，处理数字溢出。不是在计算阶乘之后计算模数，而是在计算的每个步骤继续应用模数。

Answer 2

在最坏的情况下，您正在生成1 000 000个递归调用，每个调用都需要一部分堆栈作为其激活记录。

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

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