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 }

---

Nothing is printing..... :(...I m a beginner....please help

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.

By the way, people have done exactly this already, and made nice libraries for it.

For example: The GNU MP Bignum Library

Quote:

---

Originally Posted by ShubhamDepp

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.

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)