Factorial of any number using functions | Unix Linux Forums | Shell Programming and Scripting

  Go Back    


Shell Programming and Scripting Post questions about KSH, CSH, SH, BASH, PERL, PHP, SED, AWK and OTHER shell scripts and shell scripting languages here.

Factorial of any number using functions

Shell Programming and Scripting


Closed Thread    
 
Thread Tools Search this Thread Display Modes
    #1  
Old 04-07-2011
kullu kullu is offline
Registered User
 
Join Date: Apr 2011
Last Activity: 17 July 2012, 3:13 AM EDT
Posts: 8
Thanks: 1
Thanked 0 Times in 0 Posts
Factorial of any number using functions

how to write the code for factorial of any number using functions and arguments?????
Sponsored Links
    #2  
Old 04-07-2011
acmvillareal acmvillareal is offline
Registered User
 
Join Date: Mar 2011
Last Activity: 4 June 2014, 1:21 AM EDT
Location: Manila
Posts: 28
Thanks: 0
Thanked 2 Times in 2 Posts

Code:
#!/usr/bin/sh

INPUT=$1
COUNT=${INPUT}

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

echo ${INPUT}

Sponsored Links
    #3  
Old 04-09-2011
mirni mirni is offline
Registered User
 
Join Date: Mar 2011
Last Activity: 19 July 2014, 12:13 PM EDT
Posts: 686
Thanks: 51
Thanked 178 Times in 171 Posts
I don't think so...

Code:
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?

Code:
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

    #4  
Old 04-09-2011
alister alister is offline
Registered User
 
Join Date: Dec 2009
Last Activity: 11 June 2014, 8:40 PM EDT
Posts: 3,231
Thanks: 179
Thanked 973 Times in 789 Posts

Code:
#!/bin/sh

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

factorial $1

Regards,
Alister
The Following 2 Users Say Thank You to alister For This Useful Post:
fpmurphy (04-09-2011), vgersh99 (04-09-2011)
Sponsored Links
    #5  
Old 04-09-2011
itkamaraj's Avatar
itkamaraj itkamaraj is offline Forum Advisor  
^Kamaraj^
 
Join Date: Apr 2010
Last Activity: 8 August 2014, 4:56 AM EDT
Posts: 3,057
Thanks: 33
Thanked 657 Times in 636 Posts
Alister,

Can you please explain your code.
Sponsored Links
    #6  
Old 04-09-2011
alister alister is offline
Registered User
 
Join Date: Dec 2009
Last Activity: 11 June 2014, 8:40 PM EDT
Posts: 3,231
Thanks: 179
Thanked 973 Times in 789 Posts
Quote:
Originally Posted by itkamaraj View Post
Alister,

Can you please explain your code.
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.

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


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

Push onto the stack the starting point for the calculation.

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


Code:
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.

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


Code:
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.

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


Code:
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.

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


Code:
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.

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


Code:
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.

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


Code:
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

Code:
[d1!<BdlA*sA1-lFx]

Duplicates the value at the top of the stack.

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

Stack: 5, 5

Code:
[d1!<BdlA*sA1-lFx]

Then we push a 1.

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

Stack: 5, 5, 1

Code:
[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

Code:
[d1!<BdlA*sA1-lFx]

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

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

Stack: 5,5

Code:
[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

Code:
[d1!<BdlA*sA1-lFx]

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

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

Stack: 5, 5

Code:
[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

Code:
[d1!<BdlA*sA1-lFx]

Push a 1 onto the stack.

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

Stack: 5, 1

Code:
[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

Code:
[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

Last edited by alister; 04-09-2011 at 03:45 PM..
The Following 3 Users Say Thank You to alister For This Useful Post:
jim mcnamara (04-09-2011), Scott (04-09-2011), vgersh99 (04-09-2011)
Sponsored Links
    #7  
Old 04-09-2011
itkamaraj's Avatar
itkamaraj itkamaraj is offline Forum Advisor  
^Kamaraj^
 
Join Date: Apr 2010
Last Activity: 8 August 2014, 4:56 AM EDT
Posts: 3,057
Thanks: 33
Thanked 657 Times in 636 Posts
Thanks a lot for your wonderful explanation. It is very useful
Sponsored Links
Closed Thread

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

More UNIX and Linux Forum Topics You Might Find Helpful
Thread Thread Starter Forum Replies Last Post
changing number in bash (number is in form of string) Learnerabc Shell Programming and Scripting 3 11-02-2010 05:53 PM
BASH: Factorial using FOR loop not working Technext Shell Programming and Scripting 3 07-17-2010 07:58 AM
Number lines of file and assign variable to each number glev2005 Shell Programming and Scripting 1 01-26-2010 06:04 PM
get positive number n as argument script must calculate the factorial of its argument I-1 Shell Programming and Scripting 3 04-28-2009 09:24 AM



All times are GMT -4. The time now is 09:59 AM.