Большое число факториальное по модулю большое простое число

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 стеки кадров. Поскольку пространство стека очень ограничено, ввод большого числа вызывает переполнение стека.

Измените вашу реализацию, чтобы использовать итеративный расчет факториала, чтобы избежать сбоя.

Как только вы закончите исправлять сбой, справьтесь с числовым переполнением. Вместо того, чтобы вычислять модуль по окончании вычисления факториала, продолжайте применять модуль по каждому шагу вычисления.

Answer 2

В худшем случае вы генерируете 1 000 000 рекурсивных вызовов, для каждого из которых требуется часть стека для записи активации.

Размер стека обычно ограничен 1 МБ, и как только вы используете 2 Б для каждого вызова (на самом деле вы будете использовать более 2 байт, часто 32 Б или более), вы будете использовать более 1 МБ стека, вызывая ошибку сегментации.

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