For finding the factorial of a large number

This is a discussion on For finding the factorial of a large number within the C Programming forums, part of the General Programming Boards category; Here is my algorithm :- You know to calculate factorial of a number , you should multiply all number s ...

  1. #1
    Registered User
    Join Date
    Sep 2012
    Location
    Hyderabad, Andhra Pradesh, India
    Posts
    8

    Post For finding the factorial of a large number

    Here is my algorithm :-
    You know to calculate factorial of a number, you should multiply all numbers from 1 to itself, for example:
    http://cboard.cprogramming.com/1000-...iles/minus.gif Collapse | Copy Code
    [IMG]file:///images/minus.gif[/IMG] Collapse | Copy Code

    1000! = 1*2*3**998*999*1000 There is no variable in any programming language that can store the result of this multiplication exactly; except storing in scientific notation. Because of sequential multiplication's huge result, finding a new strategy or mechanism is necessary.In my recommended algorithm, the number is not looked at as a number, instead it is treated as sequential digits where each one has its own numerical value. In fact, an array of digits is available. Each time, the second numberis multiplied by each digit of the first number (index of array) and then added with carry number up from the previous multiplication.
    This process is shown, for example 12!:
    http://cboard.cprogramming.com/1000-...iles/minus.gif Collapse | Copy Code
    [IMG]file:///images/minus.gif[/IMG] Collapse | Copy Code

    12! = 11! * 12 11! = 39916800 12! = 479001600 http://cboard.cprogramming.com/1000-...es/article.jpg
    • If the result is less than 10, the result will be placed in the cell of array.
    • If it is equal to or greater than 10, it will be divided by 10 and then the remainder will be placed in the array's cell and quotient placed in variable that will be added with next multiplication's response.
      Note: Notice that all the numbers are stored from end of array, the same as normal calculation (real calculation).

    Code:
    #include<stdio.h>
      2 int main()
      3 {
      4         int t,count,n,p,count1,i,carry=0,total,k=0;
      5         int array[500];
      6         scanf("%d",&t);
      7         for(count=1;count<=t;count++)
      8         {
      9                 scanf("%d",&n);
     10                 array[499]=1;
     11                 if(n>1)
     12                 {
     13                         printf("*");
     14                         for(count1=2;count1<=n;count++)
     15                         {
     16                                 carry=0;
     17                                 for(i=0;i<n;i++)
     18                                 {
     19                                         array[499-i]=(array[499-i]*count1)+carry;
     20                                         if(array[499-i]>9)
     21                                         {
     22                                                 carry=array[499-i]/10;
     23                                                 array[499-i]=array[499-i]%10;
     24                                                 if(count1==n)
     25                                                         k++;
     26                                         }
     27                                         else if(array[499-i]<=9)
     28                                         {
     29                                                 carry=0;
     30                                                 if(count1==n)
     31                                                         k++;
     32                                         }
     33                                 }
     34                         }
     35                 }
     36                 if(n==1)
     37                         k=1;
     38                 for(p=500-k;p<500;p++)
     39         //      for(p=475;p<500;p++)
     40                         printf("*%d",array[500-k]);
          printf("*");
     42         }
     43         return 0;
     44 }

  2. #2
    Registered User
    Join Date
    Sep 2012
    Location
    Hyderabad, Andhra Pradesh, India
    Posts
    8
    Nothing is printing..... ...I m a beginner....please help

  3. #3
    Been here, done that.
    Join Date
    May 2003
    Posts
    1,157
    You know you could make your loops simpler by using
    for (i=499; i>=0; i--)
    It would be easier to see what's happening.

    Easiest way to debug something without using the debugger is to print values at key places to follow what your program is doing.

    Also, 500? How about 10? Get it working with a short array, then lengthen it later. This also lets you work on your error processing when the array gets full. And make the maximum size a #define so you only need to change the value in 1 place.
    Definition: Politics -- Latin, from
    poly meaning many and
    tics meaning blood sucking parasites
    -- Tom Smothers

  4. #4
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    By the way, people have done exactly this already, and made nice libraries for it.

    For example: The GNU MP Bignum Library

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by ShubhamDepp View Post
    Nothing is printing..... ...I m a beginner....please help
    As suggested above, you ALWAYS want to work with a simple example of the problem, and THEN go on to the larger problem.


    Any run-time constraints facing this program? What is the expected range of N, where N! is what the program is calculating?

    Your links were not working for me. I'll look it over tomorrow, but I expect you'll have worked out the bugs by then, anyway.

    I am interested though, in what you expect for this program.

  6. #6
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,323
    I recently did a similar question on projecteuler.net and it looks like you are confusing yourself with those for loops

    The way I did this is to make an array (just like you did) - I then made a subroutine that had an array (A) and a multiplication number (B) as inputs:

    //A = A * B
    mult(A,B);

    The way I developed the algorithm for this was to start with an random number and observed how I was multiplying on a whiteboard (highly recommend everyone to get a whiteboard!) - I multiplied more than 1 digit at a time, because I wanted to save time.

    847362 x 99

    Let
    A[2] = 84; A[1] = 73; A[0] = 62; b = 99; carry = 0

    See if you can work out what is going on looking at the following and using a calculator - don't forget about carry
    Code:
    00  84 73  62  X  99
          
               38    c61
           88        c72
        88           c83
    83  88 88  38

    The factorial of anything can be worked out by starting A=1 and using a for loop to vary B from 1 to your factorial number.
    A = 1
    A = A * 1
    A = A * 2
    A = A * 3
    ...
    A = A * 1000


    For my final code I ended up using an array of __int64 (windows) and calculating 10 digits at a time (mod 10000000000ULL)
    Last edited by Click_here; 09-24-2012 at 11:29 PM. Reason: fixing spacing in algorithm
    Fact - Beethoven wrote his first symphony in C

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Finding Factorial of a large number using array
    By ShubhamDepp in forum C Programming
    Replies: 1
    Last Post: 09-23-2012, 06:28 AM
  2. Finding Factorial in C language.
    By redworker in forum C Programming
    Replies: 3
    Last Post: 05-11-2011, 11:30 PM
  3. problem with large number factorial calculation
    By afr_c2011 in forum C++ Programming
    Replies: 2
    Last Post: 01-29-2011, 09:49 AM
  4. Replies: 8
    Last Post: 08-15-2010, 05:59 PM
  5. request for C code for factorial of any wish number
    By neverthought in forum C Programming
    Replies: 17
    Last Post: 05-28-2010, 06:27 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21