Mathjax

jsxgraph

Tuesday, June 11, 2013

Factorial - scripts - sh, csh, dc, bc

Bourne shell, sh


A shell allows the user to interact with the computer much easier than older methods.  The shell mainly takes care of converting text commands to instructions for the computer.  A shell can operate in different modes including interactive and as a script.  In interactive mode commands go straight to the computer while a script ( or macro) is a file with a sequence of commands that get sent to the computer in sequence.  To be consistent with other of the factorial programs,  these programs will be scripts.  This script will also work with shells derived from sh bash (Bourne Again Shell) and  kshell (Korn Shell).

 1:#!/bin/sh  
 2:# A program to compute the factorial of a number  
 3:declare -i n  
 4:while true ; do  
 5:  read -p "Enter a number > 0, or 0 to quit :" n  
 6:  if test $n -lt 1 ; then  
 7:    break  
 8:  fi  
 9:  let k=1  
10:  for (( i=1;i<=n;i++ )) ; do  
11:    ((k=$k*$i))  
12:  done  
13:  echo ${n}"! = "$k  
14:done

Line-by-Line description

  1.  # indicates a one line comment line with the special two character sequence "#!" ( sha-bang ) is used to indicate the shell or interpreter for this file.  "/bin/sh" is where the interpreter is on my system it may be in a different place on  your system.  There can also be options for the shell like -v which will repeat lines as they are executed, a method to find out where an error is occurring.
  2. A one line comment stating what the program does.
  3. Optional line to declare that n is an integer.  All variables do not need to be declared unless a prior option to force all variables to be declared is set.
  4. Begin the main loop which goes to the "done" on line 14.  While will repeat as long as it argument is true.  Note- "True" is not true, character case is significant.  Also the semicolon could be omitted if the "do" is on the next line.  Actually the semicolon is the same as a new line to the script or you can think of it as combining lines.
  5. A read command which reads from standard input with a prompt option (-p).  The prompt is our standard question asking for input.  The result of the read is put into the variable "n".
  6. if the the command after the "if" is true then run its "then" statements.  The "test" command  checks a  comparison of number and returns true(1) or false (0).  The '$' before the 'n' indicates to use the value of 'n'.  '-lt' means less than, i.e. is the value of 'n' less than 1.  The semicolon combines the next line.
  7. "break" will leave the while loop thus ending the script.
  8. The end of the "if" instructions, "if" spelled backwards. 
  9. The "let" command assigns values.  Note there are no spaces in the assignment "k=1".
  10. Start a loop, initializing the loop variable i to 1, checking whether the value of i is less than or equal to the value of "n", then add one to the value of "i" at the end of the loop.  'do' the commands until the "done" repeatedly.
  11. The double parenthesis indicate a mathematical operation where the value of "k" is set to the value of "k" times the value of "i".
  12. The end of the factorial loop. Return to the start of the loop.
  13. Write to standard output the rest of the line.  "${n}" is the value of "n" where the braces are optional to isolate it from additional characters.  The quoted text will be echoed without the quotes. Then the value of "k" will be output.
  14. The end of the while loop.  Return to line 4.
Exercises -
Save the code above to "fact.sh", see note below.
Make the code executable (chmod u+x or use a file manager)
Run the code ( ./fact.sh) and enter numbers including 5,10,12,13,19,20,21 and 70

Note: a shell can be used to remove the line numbers easily.  Save the code

#!/bin/sh
sed -i -e 's/^.\{1,3\}://' $1

to a file "unn", make it executable,  and run it with the name of the file with line numbers( ./unn fact.sh ) .  This script runs the stream editor, sed, inplace ( -i ) with the instruction ( -e ) to substitute ( s ) matches of ( / ... / ) the beginning of the line( ^ ) followed by 1 to 3 ( \{1,3\} ) of any character ( . ) followed by a colon ( : ) with nothing ( // ).  This also passes the first argument of the script ( $1 ) as the file for sed to change.


C shell - csh, tcsh

The C shell was intended to have a syntax similar to the popular programming language "C".   "tcsh" added many useful features for interactive use including tab completion and history.

 1:#!/bin/csh
 2:#  A program to compute the factorial of a number
 3:while (1)
 4:  printf "Enter a number > 0, or 0 to quit :"
 5:  set n = $<
 6:  if ($n < 1) then
 7:    break
 8:  endif
 9:  @ k = 1
10:  @ i = 1
11:  while ( $i <= $n ) 
12:    @ k = $k * $i
13:    @ i = $i + 1
14:  end
15:  echo ${n}"! = "$k
16:end 

Line-by-line description
  1. Comment line to indicate the interpreter to use for running this code
  2. A one line comment
  3. Start a while loop - repeat while the parenthesis contents are true.  1 is true.
  4. print formatted the string without a new line
  5. set the value of "n" to what is read from standard input "$<"
  6. Test if the value of "n" ($n) is less than 1 if it is less than 1 execute the commands up to the matching "endif" otherwise skip to past the "endif"
  7. break out of the while loop to quit the program
  8. mark the end of the "if" statements
  9. @ indicates a math operation follows which sets the value of "k" to 1.  The spaces are necessary.
  10. set the value of "i" to 1
  11. start of the factorial loop.  Repeat while the value of "i" ($i) is less than or equal to the value of "n" ($n).
  12. @ indicates a math operation, set the value of "k" to the product of the values of "k" and "i"
  13. A math operation to add 1 to the value of "i"
  14. The end of the factorial while loop.  Return to line 11.
  15. print (echo) the rest of the line to standard output.  The line includes the value of "n" (${n}), the string "! = ", and the valuie of "k".  The braces on "n" are optional but can be used to isolate the name of the variable.
  16. The end of the main while loop.  Return to line 3.


Exercises -Save the code above to "fact.sh", see note below.
Make the code executable (chmod u+x or use a file manager)
Run the code ( ./fact.sh) and enter numbers including 5,10,12,13,19,20,21 and 70

dc - Desktop Calculator


dc is a stack based  calculator that can be programmed.  dc has been around for a long time and is still useful.  It has only 45 terse instructions so should be easy to learn.  With a stack, items are pushed onto the top of the stack and pulled from the top of the stack.  For example a multiplication takes the top two items, multiplies them together, then pushes the result onto the top of the stack.  Many things are done on computers using stack systems.  Post script and pdf are a stack based system for printing graphically.  dc is a fun way to learn stack based programming because it is an arbitrary precision calculator showing results to many digits.  The programs are usually one liners where almost every character does something.  This code has been expanded to be more readable.  Most of the action occurs on the last line.

 1:#!/usr/bin/dc
 2:[[Enter a number > 0, or 0 to quit :]P]sa
 3:[q]sb
 4:[d[d1-d1<F*]dsFxrn[! = ]Pn[
 5:]P]sc
 6:[lax?d1>blcxdx]dx

Line-by-line description
  1. # starts a comment, #! on the first line indicates the interpreter to use for executing the program
  2. Save the string that when executed will print the instruction to enter a number to standard output.  The string is saved in register "a"
  3. Save the string that will quit the program into register "b"
  4. Lines 4 and 5 compute the factorial and print the results.  The table below shows an example if a three was in the top of the stack at the start of line 4.  These are saved into register "c"
  5. A continuation of the string of instructions from line 4.
  6. The main command sequence.
    1. lax - load register "a" and execute it
    2. ? - read input from standard input
    3. d1>b - test if 1 > the number input and run register "b" to exit if it is true
    4. lcx - load register "c" to compute the factorial and print the result
    5. dx - duplicate the top which will be this string and execute it
    6. [ ... ]dx - duplicate the string for the prior "dx" so that it is available after the factorial and execute (run) the string.
Note that the string in line 2 could be substituted for "lax" in line 6 and "lcx" could be replaced by the string of lines 4 and 5.  The following table show the stack contents after each command of lines 4 and 5 assuming 3 is on the stack at the start.  Additional stack contents including the string of line 6, are not shown as they would just push on down the stack.

    Command Stack After Command Comment

    3 top element of the stack
    d 3 duplicate the top for later output
    3
    [d1-d1<F*] [d1-d1<F*] push the string “d1-d1<F*”
    3
    3
    d [d1-d1<F*] duplicate
    [d1-d1<F*]
    3
    3
    sF [d1-d1<F*] save into register “F”
    3
    3
    x (d1-d1<F*) 3 execute the string
    3
    d 3 duplicate
    3
    3
    1 1 push 1
    3
    3
    3
    - 2 subtract the top from the second
    3
    3
    d 2 duplicate
    2
    3
    3
    1 1 Push 1
    2
    2
    3
    3
    <F 2 if top is less than second ( 1 < 2) execute F
    3
    3
    x (d1-d1<F*) 2 Execute "F", Note that the multiply in the first string has not been used yet.
    3
    3
    d 2 duplicate
    2
    3
    3
    1 1 Push 1
    2
    2
    3
    3
    - 1 subtract the top from the second ( 2-1)
    2
    3
    3
    d 1 duplicate the top
    1
    2
    3
    3
    1 1 Push 1
    1
    1
    2
    3
    3
    <F 1 if top is less than second ( 1 < 1) execute F.
    F is not executed again.
    2
    3
    3
    * 2 multiply top two elements (1*2), This is the second "*"
    3
    3
    * 6 multiply top two elements (2*3), This is the first "*"
    3
    r 3 reverse the first two elements
    6
    n 6 Print and remove the top element
    [! = ] [! = ] push the string “! = “
    6
    P 6 Print the string “! = “
    n
    Print and remove the top element
    [
    ]
    [
    ]
    push a string with a new line in it
    P
    Print the new line

    Exercises -
    Save the code to a file without the line numbers (fact.dc)
    Make the file executable (chmod u+x)
    Run the program (./fact.dc)
    Enter some numbers including 5,19,20,21,70
    Enter "15 3 /" ( without quotation marks)
    Enter "7 10 *"
    Enter _3 - On input an underscore is used to represent a negative number since a dash would difference the top two stack items.
    Restart and enter "2 k 20"
    Assuming the computer memory is large enough, this code will give "exact" results for all positive numbers except for one number.  Which number gives the wrong answer and why?  Fix the code to give the correct answer for all positive integers.

    bc - Basic Calculator


    Since dc was difficult for some people to use, a more natural "C" like calculator with arbitrary precision was desired.  The original "bc" used "dc"  to perform its computations. This code uses gnu extensions to read "n" and print the results.

     1:#!/usr/bin/bc
     2:/* A program to compute the factorial of a number */
     3:while(1) {
     4:  "Enter a number > 0, or 0 to quit :"; n=read()
     5:  if( n < 1) break;
     6:  k=1;
     7:  for(i=1;i<=n;i++) k=k*i;
     8:  print n,"! = ",k,"\n"
     9:}
    10:quit
    

    Line-byline description
    1. Tell the system to use /usr/bin/bc as an interpreter.  # starts a comment
    2. A multi-line style comment.  A # could also be used for one line comments.
    3. Begin the while loop.  Repeat if 1 is true.  1 is true so repeat forever.  Braces enclose the code to be repeated.
    4. If there is no assignment the result is written to standard output.  Here the question string is written then "n" is read from standard input.
    5. Test if n is less than one break out of the loop.  This also illustrates a one line "if" statement
    6. Initialize k to 1.  It will be 0 if not initialized.
    7. A one line for loop with an index variable of "i" starting at 1 till it is not less than or equal to the value of "n" and increasing by 1 each loop.  Each loop sets the value of "k" to the product of the values of "k" and "i"
    8. print the results to standard output.
    9. end of the while loop,  go to line 3.
    10. quit the program.  Without this statement bc would continue to run after the main loop ended.
    Exercises -
    Save the code as "fact.bc"
    Run the code (./fact.bc)
    Enter numbers some numbers.

    No comments:

    Post a Comment