c program to calculate factorial of large numbers

Discussion in 'C' started by teacher, Mar 27, 2011.

  1. teacher

    teacher New Member

    Joined:
    Mar 27, 2011
    Messages:
    66
    Likes Received:
    8
    Trophy Points:
    0
    Occupation:
    i hate jobs
    Location:
    india,agra
    Home Page:
    http://www.crazylearner.in
    This is my solution to calculate the factorial of large numbers upto 3300 and can be extended depending on your system memory.To increase range change constant ARRAY_SIZE:pleased::pleased:

    Code: cpp
    Code:
    #include <stdio.h>
    #include <math.h>
    /* INCREASE OR DECREASE ARRAY_SIZE TO INCREASE OR DECREASE THE
    *  RANGE OF NUMBERS WHOSE FACTORIAL YOU WANT TO CALCULATE 
    *  TESTED ON DEV C++ 
    *  AUTHOR: TEACHER    
    */
    #define ARRAY_SIZE 12000
    int fact(int a[],int number,int *f){
    int i,carry=0,temp;
    for(i=ARRAY_SIZE-1;i>=(*f);--i){
    temp=(a[i])*(number)+carry;
    a[i]=temp%10;
    carry=(temp/10);
    }
    while(carry){
    a[i]=carry%10;
    carry=carry/10;
    i--;
    }
    *f=i+1;
    }
    int main(){
    int i=ARRAY_SIZE-1,f=ARRAY_SIZE-1,n,x;
    static int a[ARRAY_SIZE];
    printf("enter number to calculate its  factorial: ");    
    scanf("%d",&x);
    if(x==0){
    printf("1");
    }
    else{
    int temp=x;
    while(temp){
    a[i]=temp%10;
    temp=temp/10;
    i--;
    }
    f=i+1;
    for(i=x-1;i>=1;--i){
    fact(a,i,&f);
    }
    for(i=f;i<=ARRAY_SIZE-1;++i){  
    printf("%d",a[i]);
    }
    printf("\n"); 
    }
    }
    
     
  2. kyle

    kyle Member

    Joined:
    Dec 28, 2010
    Messages:
    46
    Likes Received:
    0
    Trophy Points:
    6
    Occupation:
    don't have 1
    Location:
    i live in Italy,Milano
    thank you man
    i could really use that
     
  3. kyle

    kyle Member

    Joined:
    Dec 28, 2010
    Messages:
    46
    Likes Received:
    0
    Trophy Points:
    6
    Occupation:
    don't have 1
    Location:
    i live in Italy,Milano
    thank you man
    i could really use that
     
  4. teacher

    teacher New Member

    Joined:
    Mar 27, 2011
    Messages:
    66
    Likes Received:
    8
    Trophy Points:
    0
    Occupation:
    i hate jobs
    Location:
    india,agra
    Home Page:
    http://www.crazylearner.in
    hey buddy are you really getting the logic behind this or just copy paste.?dont,t do copy paste to get numbers.these numbers are not worth anything...
     
  5. kyle

    kyle Member

    Joined:
    Dec 28, 2010
    Messages:
    46
    Likes Received:
    0
    Trophy Points:
    6
    Occupation:
    don't have 1
    Location:
    i live in Italy,Milano
    i am trying to learn C++,but to be honest , don't understand a line there.
    that's not good at all (wish i could know C++)
    and i hate copying, i really do, even in real life.
     
  6. teacher

    teacher New Member

    Joined:
    Mar 27, 2011
    Messages:
    66
    Likes Received:
    8
    Trophy Points:
    0
    Occupation:
    i hate jobs
    Location:
    india,agra
    Home Page:
    http://www.crazylearner.in
    That's not a good sign .do you know c ?
    you must learn c before learning c++ ,actually above code is in c not in c++....
    can you differentiate between c and c++ ? srry but i think you can't
     
  7. elvirag

    elvirag New Member

    Joined:
    May 3, 2011
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    Code:
    #include <stdio.h>
    #include <math.h>
    
    #define N 2568
    
    //AUTHOR: elvirag@gmail.com :)
    
    //play with the N to enlarge the length of the answer...
    //more on the program outside of it...
    //PLUS explanations about the numbers in the example.
    
    int i,j,k,sum=0,fact=0;
    int a[N]={0};
    
    int main() {
    
    a[0]=1;
    printf("What factorial do you want to calculate? ");
    scanf("%d",&fact);
        
        for(i=2;i<=fact;i++){
            for(j=0;j<N;j++) a[j]*=i;
                 for(k=0;k<N;k++){
                     if(a[k]>9){
                        a[k+1]+=a[k]/10;
                        a[k]=fmod(a[k],10);
                     }
                    if(a[k+1]>9){
                        a[k+2]+=a[k+1]/10;
                        a[k+1]=fmod(a[k+1],10);
                    }
                 }
        }
    for (i=0;i<N;i++) {
        printf("%d",a[i]);
        }
        printf("\n");
        printf("Read the number from right to left!");
    return 0;
    }
    
    
    This code runs the factorial of 10,000, which has 35660 DIGITS(!)
    in the whooping time of 22.218 seconds, on my laptop which is a 4 year old HP.

    There is actually no limit whatsoever to what factorial you can calculate with this code, as long as you add to N the required length.

    I advise that if you start seeing zeroes at the end, you should make your N smaller.
    It will take less time.

    A standard and not a scary example of the power of this code:
    10! - N=7, 3.14 secs...
    100! - N=158, 1.906 secs...
    1000! - N=2568, 2.671 secs...

    As you can see, it's more powerful as the facts go up...

    Have fun.

    And sorry for the over enthusiasm, it's the first time I publish code online...:shy:
     
  8. teacher

    teacher New Member

    Joined:
    Mar 27, 2011
    Messages:
    66
    Likes Received:
    8
    Trophy Points:
    0
    Occupation:
    i hate jobs
    Location:
    india,agra
    Home Page:
    http://www.crazylearner.in
    sorry if i am being rude but the code you have posted is less practical to be used in real life problems

    first of all to print out the correct value of a factorial you must know the number of digits in the result in advance so that you can set the value of N

    for eg

    if N=3
    5!=021

    if N=4
    5!=0120 (wrong answer)

    tell me how the user will be able to know the number of digits in the result ?

    for eg if user wants to calculate 1331! ,from where he will get the value of N?

    again your code is printing the digits in a result in reverse order.that is also not cool if you want to use that result in another calculation.

    at last you said that your code is taking 22 secs to calculate 10000!.sorry if i am biased towards my code but my code is still taking less time ((my code ) 8 secs on my machine vs (your code) 20 secs on my machine ) to calculate 10000!.

    correct me if i am wrong

    thank you
     
  9. elvirag

    elvirag New Member

    Joined:
    May 3, 2011
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    Well, you can surely use it in another calculation, because the array is still there,
    it doesn't just print out the result and dissipates.

    Besides, I didn't say that my code was superior,
    I just said that it is more easily understandable to people who
    are not on a high level, which I myself wasn't the time I published the code.

    Now I am, but I can still relate to people who read your code and say
    "huh? I don't understand where it all goes..." cause that is what I felt.
    And when I ran your code (and I did, ofc) the results were quite similar. :)
    But the point is not the speed because it gives the result. :)

    And regarding the "if N=4
    5!=0120 (wrong answer)"
    No, the answer it will give if N=4 is: 0210
    which is correct if you read it from the right to the left.

    You are not supposed to KNOW the N, you print the result,
    then if you have zeroes at the beginning of the number,
    you make the N smaller, but you don't really have to.
    If you don't see zeroes,
    there is a risk that it's not all of the answer so you make the N bigger.

    I hope I was able to answer all of your questions,since this is my first time publishing code,
    I was never this excited about programming. :)
     
  10. teacher

    teacher New Member

    Joined:
    Mar 27, 2011
    Messages:
    66
    Likes Received:
    8
    Trophy Points:
    0
    Occupation:
    i hate jobs
    Location:
    india,agra
    Home Page:
    http://www.crazylearner.in
    yes i know the array is still there but as you can see the array will contain the values in reverse order

    for n=4
    5!===> a[0]=0,a[1]=2,a[2]=1,a[3]=0

    surely you can't use this array in that way.you have to first reverse it and then you have to left shift the whole array to come up with the proper answer.This is just like adding another level of complexity to the code...
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice