3

I need to calculate the factorial of a big number (<=1.000.000) and I need the result modulo 1000000007. I wrote the following but it generates an error when run (test.exe has stopped working). It works only for small numbers.

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

UPDATE 1:

long long unsigned fact(long long unsigned nr){
    long long unsigned r = nr;
    while(--nr){
        r = modulo(r * nr);
    }
    return r;
}
Zack
  • 385
  • 2
  • 3
  • 21
  • 1
    use modular arithmetics modmul instead of * , do not use N times recursion to avoid heap/stack trashing/overflows and use fast factorial instead if possible (for example this http://stackoverflow.com/a/18333853/2521214 is mine bud needs table of primes up to N , but there are more out there ...) – Spektre Jul 21 '14 at 06:45
  • Don't forget, that you can calculate it in `O(sqrt(n))` time. – Tacet Nov 13 '14 at 19:02

3 Answers3

7

This is because your implementation uses recursion. For small numbers it works fine, but for large numbers it overflows the stack.

This line

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

creates nr stack frames. Since the stack space is very limited, entering a large number causes stack overflows.

Change your implementation to use iterative calculation of the factorial to avoid the crash.

Once you are done fixing the crash, deal with the numeric overflow. Rather than computing the modulo after the factorial has been calculated, keep applying modulo at each step of the calculation.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • 1
    That won't help. computing 1000000! will overflow regardless of the recursion – SomeWittyUsername Jul 20 '14 at 12:04
  • 4
    I don't think is any numeric overflow issue with the code as written in the question. – Pascal Cuoq Jul 20 '14 at 12:07
  • @PascalCuoq +1, disregard my comment, it's not correct for this code – SomeWittyUsername Jul 20 '14 at 12:09
  • Is there any way to do it faster? I'm using this code in an algorithm for a problem and when I'm trying to test it, the tester says Time limit exceeded. (The memory limit is 8192 kbytes and the execution time limit is 0.7 sec - in an execution I'm doing three calls of fact() ) – Zack Jul 20 '14 at 12:27
  • 2
    @Zack Here is a [demo on ideone](http://ideone.com/2obFOz) that computes the answer for 10,000,000 in 0.34 seconds. – Sergey Kalinichenko Jul 20 '14 at 12:58
2

In worst case, you are generating 1 000 000 recursive calls, each one requiring a portion of the stack for its activation record.

Stack size is usually limited to 1MB, as soon as you use 2B per each call (actually, you will be using more than 2 bytes, often 32B or more), you will be using more than 1MB of stack, causing the segmentation fault.

Stefano Sanfilippo
  • 32,265
  • 7
  • 79
  • 80
0
/* C code to implement factorial of large number */
#include&lt;stdio.h&gt;
int main(){
int a[200],index,i,j,n,tmp,counter=0;
printf("\n Enter the no : ");
scanf("%d",&amp;n);
a[0]=1;
index=0;
//Calculation Loop
for(j=n;j&gt;=2;j--){
tmp=0;
/* This Loop is used to multiply the numbers */
for(i=0;i&lt;=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 &amp; 2) and store it into array */
while(tmp&gt;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&gt;=0;i--)
printf("%d",a[i]);
return 0;
}
user3818318
  • 3
  • 2