Factorial Computation

This blog will explain about factorial computation algorithm development step by step.

Algorithm development

Start the development of this algorithm by examining the definition of n!

                                    n!=1*2*3*….(n-1)*n for n>=1

                  

and by definition. Computer's arithmetic unit can only multiply two numbers at a time. Applying the factorial definition we get,

                                                           

                                                            0!= 1

                                                            1!=l x l

                                                            2!  1x 2

                                                            3!=l x 2 x 3

                                                            4! = l x 2 x 3 x 4

4! contains all the factors of 3L The only difference is the inclusion of the number 4. n! can always be obtained from (n-1)! by simply multiplying it by n (for n~ 1). That ~is, n! = nx(n-l)! for n.>=1

From step (2) onwards the same process is repeated. For the general (i+ 1)th step,

p:=p*i     (i+1)

This general step can be placed in a loop to iteratively generate n!. This allows to take advantage of the fact that the computer's arithmetic unit can only multiply two numbers at a time. In many ways this problem is very much like the problem of summing a set of n numbers. In the summation problem we performed a set of additions, whereas in this problem we need to generate a set of products. It follows from the general (i+ 1)th step that all factorials for n~ 1

can be generated iteratively. The instance where n = 0 is a special case which must be accounted for directly by the assignment

                                                p:= 1 (by definition of 0!)

The central part of the algorithm for computing n! therefore involves a special initial step followed by n iterative steps.

1. Treat 0! as a special case (p := 1).
2. Build each of the n remaining products p from its predecessor by an iterative process.
3. Write out the value of n factorial.

Algorithm description

1. Establish n, the factorial required where n≥0.

2. Set product p for 0! (special case). Also set product count to zero.

3. While less than n products have been calculated repeatedly do

            (a) increment product count,

            (b) compute the ith product p by multiplying i by the most recent product.

4. Return the result n!.

This algorithm is most usefully implemented as a function that accepts as input a number n and returns as output the value of n! In the Pascal implementation p has been replaced by the variable factor.

Sample code for Factorial:

The below code will compute the factorial for 25.

for (c = 1; c <= 25; c++)
    fact = fact * c;
 
  printf("Factorial of %d = %d\n", n, fact);
 

Happy coding!!!!