Algorithm for Factorial Computation

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n.

We can start the development of this algorithm by the definition of n!

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

 

In our design, we need to keep in mind that the computer’s arithmetic unit can only multiply two numbers at a time
Applying the factorial definition we get

    0!=1
    1!=1*1
    2!=1*2
    3!=1*2*3
    4!=1*2*3*4  etc.

We can see that 4! contains all factors of 3!. The only difference is 4. We can generalize this by observing that n!can always be obtained from (n-1)! by simply multiplying by n(for n>=1). that is,

    n!=n*(n-1)! for n>=1

 

Using this def we can write the first few factorial as

    1!=1*0!
    2!=2*1!
    3!=3*2!
    4!=4*3! etc.

 

If we start p=0!=1 we can write first few steps in computing n!as:

    p:= 1 =0!
    p:= p*1 =1!
    p:= p*2 =2!
    p:= p*3 =3!
    p:= p*4 =4!  etc.

 

From step 2 onwards we are actually repeating the same process over and over. For general (i+1)the step we have

    p := p*i (i+1)

 

This general step can be placed in a loop to iteratively generate n!. this allows us to take advantage of the fact that the computer 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 this problem, we need to generate a set of products. it follow from the general (i+1)th step that all factorials for n>=1 can be generated iteratively. The instance where n=0 is special case which must be accounted for directly by 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 special case (p := 1)
2. Build the each of the n remaining products from its predecessors by an iterative process.
3. Write out the value of n!

 

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 i th product p by multiplying i by the most recent product.
4. Return the result n!

Anwar Yakkiparamban

Anwar Yakkiparamban is the founder of Lauyou Learning. Prior to Lauyou learning, Anwar worked at ARD Engineering & Development, Qatar. He holds bachelor degree in Electronics and Communication Engineering from Govt. Engineering College Idukki.

You may also like...