Sponsored Content
Top Forums Shell Programming and Scripting Factorial of any number using functions Post 302512346 by alister on Saturday 9th of April 2011 03:25:06 PM
Old 04-09-2011
Quote:
Originally Posted by itkamaraj
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 04:45 PM..
These 3 Users Gave Thanks to alister For This Post:
 

10 More Discussions You Might Find Interesting

1. Shell Programming and Scripting

Regarding functions

Hi, I have a function or script like this. show() { echo "Hi" } | tee -a log show This creates a logfile and prints Hi in it. Now when I try to do the same for sql like this: show() { sqlplus -s scott/tiger<<! select * from details; ! } | tee -a log show Then it gives me a... (2 Replies)
Discussion started by: sendhilmani
2 Replies

2. Shell Programming and Scripting

functions in

hi could anybody please suggest me how to put a function memory for particular user. say i am a user rao. want have a function foo in memory . i have done this .typed the function function in the shell it worked for the session.but next time i do login its not there . i can i have a... (6 Replies)
Discussion started by: Raom
6 Replies

3. Shell Programming and Scripting

Use of functions

Hi my shell is tcsh can I have functions in my shell scripting? Is the below shell script correct. Can I have two functions and call one of them as required. ---------- echo "functions" f1 f1 () { echo "hello" } f2 () (1 Reply)
Discussion started by: amitrajvarma
1 Replies

4. Shell Programming and Scripting

get positive number n as argument script must calculate the factorial of its argument

Can someone please help me with this SHELL script? I need to create a script that gets a positive number n as an argument. The script must calculate the factorial of its argument. In other words, it must calculate n!=1x2x3x...xn. Note that 0!=1. Here is a start but I have no clue how to... (3 Replies)
Discussion started by: I-1
3 Replies

5. Shell Programming and Scripting

Need a little help with functions

I'm semi new to unix/linux and am trying to convert a program I wrote in C++ to a bash script. It's a program that prints Fibonacci's series. I have found scripts that will do it, but I'm trying persistently to get this one to work. The problem occurs when I try to return a value from the function.... (3 Replies)
Discussion started by: Glowworm
3 Replies

6. Shell Programming and Scripting

BASH: Factorial using FOR loop not working

Hi, I am trying to run the factorial script but it’s not working. The code is mentioned below: ------------------------------------------------------------------ /home/gc> cat fact.sh #!/bin/bash # using one command line parameter factorial=1 for (( number = 1; number <= $1 ;... (3 Replies)
Discussion started by: Technext
3 Replies

7. Shell Programming and Scripting

i think i need functions ?

Hi, im making a little script but need some help Code i have so far is read -p 'Bot Nickname:' ecnick read -p 'Bot Username:' ecusername read -p 'Bot Realname:' ecrealname read -p 'Your Email:' ecemail echo '' echo Your bots nickname is set to $ecnick echo Your bots username is set to... (2 Replies)
Discussion started by: Gemster
2 Replies

8. Programming

Functions

Hi All, Can any one help me. I am calling in a function2 with string as parameter from function1, the function1 gives 3 values. how i get the 3 values from funciton2 to function1. i have to give a return or something. thanks in advance. (2 Replies)
Discussion started by: uday.sena.m
2 Replies

9. Shell Programming and Scripting

How to execute functions or initiate functions as command line parameters for below requirement?

I have 7 functions those need to be executed as command line inputs, I tried with below code it’s not executing function. If I run the ./script 2 then fun2 should execute , how to initiate that function I tried case and if else also, how to initiate function from command line if then... (8 Replies)
Discussion started by: saku
8 Replies

10. Shell Programming and Scripting

README: Factorial quick chart with sed & bc:

Hi all, While doing some checks I found a kind of interesting arithmetic factorial chart with sed, sharing this may be simple but thought to share, # n=20;for i in `seq $n`;do printf "`seq $i|xargs|sed 's/ /*/g'`= ";echo "`seq $i|xargs|sed 's/ /*/g'`"| bc;done 1= 1 1*2= 2 1*2*3= 6... (6 Replies)
Discussion started by: rveri
6 Replies
All times are GMT -4. The time now is 03:52 PM.
Unix & Linux Forums Content Copyright 1993-2022. All Rights Reserved.
Privacy Policy