Factorial of any number using functions

Shell Programming and Scripting
1

how to write the code for factorial of any number using functions and arguments?????

2 
#!/usr/bin/sh

INPUT=$1
COUNT=${INPUT}

while [ ${COUNT} -ne "1" ]
do
COUNT=`expr ${COUNT} - 1`
INPUT=`expr ${INPUT} \* ${COUNT}`
done

echo ${INPUT}
3

I don't think so...

miro@miro-ntb:tmp$ cat fact.sh
#!/bin/sh

INPUT=$1
COUNT=${INPUT}

while [ ${COUNT} -ne "1" ]
do
COUNT=`expr ${COUNT} - 1`
INPUT=`expr ${INPUT} \* ${COUNT}`
done

echo ${INPUT}miro@miro-ntb:tmp$ ./fact.sh 30
expr: *: Numerical result out of range
expr: syntax error
expr: syntax error
expr: syntax error
...

How about letting bc do all the dirty work?

miro@miro-ntb:tmp$ cat fact.sh
#!/bin/bash
function fac {
  N=$1
  fact=1
  while [ $N -gt 1 ] ; do 
    fact="${fact}*${N}"
    ((N--))
  done
  echo $fact | bc
}

fac $1

miro@miro-ntb:tmp$ ./fact.sh 6
720
miro@miro-ntb:tmp$ ./fact.sh 150
57133839564458545904789328652610540031895535786011264182548375833179\
82912484539839312657448867531114537710787874685420416266625019868450\
44663559491959220665749425920957357789293253572904449624724054167907\
22118445437122269675520000000000000000000000000000000000000

:slight_smile:

4 
#!/bin/sh

factorial() {
        printf '%d %s\n' $1 '1sA [q]sB [d1!<BdlA*sA1-lFx]sF lFx lAp' | dc
}

factorial $1

Regards,
Alister

2 Likes
5

Alister,

Can you please explain your code.

6

Hello, itkamaraj:

I can try. Allow me to apologize ahead of time for my feeble WYSIWYG web editor skills. I have very little experience with them. Here goes...

While some dc commands are uppercase letters, it turns out that I only used lowercase commands. To make it easier to read, I chose only uppercase for register names.

A = accumulator: this register stores the value after each multiplication
B = register with macro to break out of the computation
F = register with the factorial macro

THE BIG PICTURE

Initialize the accumulator to 1. Check the value on the stack, n. Is n 0 or 1? If so, we're done. Copy the accumulator's 1 to the stack and print it. If the value on the stack, n, is greater than 1, then we need to start computing the factorial. Multiply n, by what's in the accumulator, store the result back into the accumulator, decrement n and repeat (except for initializing the accumulator).

THE DETAILS

Let's assume that the function was called thusly, "factorial 5". Initially, dc's stack is empty.

##############################################################

5 1sA [q]sB [d1!<BdlA*sA1-lFx]sF lFx lAp

Push onto the stack the starting point for the calculation.

##############################################################

5 1sA [q]sB [d1!<BdlA*sA1-lFx]sF lFx lAp

Push a 1 onto the stack and then store it (s) in register A. This initializes the accumulator.

##############################################################

5  1sA [q]sB [d1!<BdlA*sA1-lFx]sF lFx lAp

define a macro that does nothing but quit itself and its caller. Brackets are used in dc to delimit a string. s is a store command. B is the name of the register.

##############################################################

5 1sA [q]sB [d1!<BdlA*sA1-lFx]sF lFx lAp

Same as the previous step with B, but stores the factorial macro in register F. I'll break this macro down in a moment.

##############################################################

5  1sA [q]sB [d1!<BdlA*sA1-lFx]sF lFx lAp

lF loads the macro stored in register F (this means that the string in F is copied/pushed onto the stack). x pops the top value from the stack (the contents of F which we just loaded) and executes it as a macro.

##############################################################

5  1sA [q]sB [d1!<BdlA*sA1-lFx]sF lFx lAp

lA loads (pushes a copy of) the value in register A, the accumulator, which at this point holds the final result of the computation, onto the stack. p prints the top value on the stack.

##############################################################

5 1sA [q]sB [d1!<BdlA*sA1-lFx]sF lFx lAp

Now, let's take a closer look at the factorial macro in register F by tracing its first run. Initially, there is nothing on the stack but a single number. This number is the starting point for the computation ($1 in the shell script). So, if calculating 5!, the stack consists of one item, 5.

##############################################################

Stack: 5

[d1!<BdlA*sA1-lFx]

Duplicates the value at the top of the stack.

##############################################################

Stack: 5, 5

[d1!<BdlA*sA1-lFx]

Then we push a 1.

##############################################################

Stack: 5, 5, 1

[d1!<BdlA*sA1-lFx]

!<B pops two values from the top of the stack and compares them. If the top of the stack is not less-than (!<) the second value, execute the macro in register B. This acts as a conditional expression which allows us to know when we need to stop executing the factorial macro.

In this case, the top value is 1 and the next value is 5, since 1 is less-than 5, the test returns false and the macro in register B (to break out from the current macro and its parent) is not executed.

Note that the test consumes the top two values on the stack. This is why we had to duplicate the 5; so we could perform this test and yet still have a copy of it for later use (since we still need it).

##############################################################

Stack: 5

[d1!<BdlA*sA1-lFx]

Duplicate the top value again. We still need it for multiplication and subtraction operations.

##############################################################

Stack: 5,5

[d1!<BdlA*sA1-lFx]

Push the current value of register A, the accumulator, on the stack. The first time through, the accumulator still has its initial value of 1.

##############################################################

Stack 5, 5, 1

[d1!<BdlA*sA1-lFx]

The * will pop two values from the stack, multiply them, then push the result.

##############################################################

Stack: 5, 5

[d1!<BdlA*sA1-lFx]

Pops a value from the stack and stores it in the accumulator (which was 1 and now is 5).

##############################################################

Stack: 5

[d1!<BdlA*sA1-lFx]

Push a 1 onto the stack.

##############################################################

Stack: 5, 1

[d1!<BdlA*sA1-lFx]

Subtraction pops two values on the stack (the only two in this case) and pushes the result. Here we decrement by 1 to leave the stack with only one value, which will be the starting point for the next iteration.

##############################################################

Stack: 4

[d1!<BdlA*sA1-lFx]

At the end, the factorial macro will call itself and begin another iteration.

##############################################################

Hope that helped.

There are a couple of more stack-centric approaches in the dc wikipedia page, but they are both buggy. One can't handle a 0! (segfaults with my dc) and the other cannot handle a 0! or 1!. Still, they're worth reading to see how to do this while using a few less registers. Just note that they're incomplete.

Regards,
Alister

3 Likes
7

Thanks a lot for your wonderful explanation. It is very useful

8

wow.... sure is cryptic