Factorial of large numbers in C - Unleash-Coding-Skills

Sunday, 25 March 2018

Factorial of large numbers in C

You can find factorial of large number program in:

https://unleash-coding-skills.blogspot.in/2018/03/factorial-of-number-recursive-and.html

But this does not work for factorial of large numbers since the range of our data types is not enough to give the result.



So this approach is used to print factorial of large numbers.


#include <stdio.h>

int main(void) {
long long i,j,k,n,sum,a[2000000],carry,more,t,r,ii;
      scanf("%lld",&n);
      for(i=0;i<=200;i++)
      a[i]=1;
      k=0;
      carry=0;
      for(i=1;i<=n;i++)
      {
            for(j=0;j<=k;j++)
            {
                  a[j]=a[j]*i+carry;
                  carry=a[j]/10;
                  a[j]=a[j]%10;
            }
            while(carry>0)
            {
                  k++;
                  r=carry%10;
                  carry=carry/10;
                  a[k]=r;
                  
            }
      }

      for(i=k;i>=0;i--)
      {
            printf("%lld",a[i]);
      }
      if(ii!=t-1)
      printf("\n");

        return 0;
}
 
Input:234
 
Output:
    22670150051024339208842996793945853659618105149432332891909162781453188496185286163298606516694886905607365190190959563064612945338703694136857684356961467817193275159683377314353662443780840896397239708288581036699483832395636246310971241224996315914676173236435465798388095261168098119711919219177465172417531870533071210963890951079600651352649259865692984172459046697905169775036847325733034393600000000000000000000000000000000000000000000000000000000
 
 

 

To understand this properly first we need to know how to multiply two numbers using an array.
Suppose the numbers can be 12 and 97 we need to multiply using an array.First take 1 in array and multiply with 12

Initially the array must contain '1' at the 0th index and remaining index values are considered as zeros and initial carry also '0'.

Initially the array contains  
             index                                                         1               0
                                                                               0              1*12 <= array values
=>                                                                          0                  12
Here now '2' should be at '0' location 1 is carry add to next index value
             index                                                          1             0
                                                                    0*12+ 1             2
                                                                                             
At every index multiply the array value with 97 and add the carry value to the array value and later put the arrayvalue%10  there and carry now becomes arrayvalue/10
Multiply with 97
         index                      3               2        1                               0
                                        0              0         1                            2*97 <=arrayvalues
                                                                   1                             194
                                        0              0         1*97+19                    4
                                                                   116                            4
                                        0      0*97+11       6                              4
                             0*97+1               1           6                              4
                                        1              1           6                              4

Now this logic is only applied for factorial in which each array value is multiplied by number in factorial multiplication in the above code.
These two logics only carry and addition of index values is applied in for loop logic.

So know we got the multiplication of two numbers using arrays now what we must implement for the factorial suppose the number is 5!
So we need to multiply as 5*4*3*2*1.
So initially array is multiplied between initial array and 5.
Then later the current array is multiplied by 4 and so on until we multiply 3 ,2, 1, on the array values. 

Now while printing the output print the value from highest index to the 0th index so this will be result of your factorial.

Happy Coding.............

Feel Free to make comment

 

No comments:

Post a comment