大数阶因数模数大素数

我需要计算一个大数的阶乘（<= 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; }