| Advanced Bash-Scripting Guide: An in-depth exploration of the art of shell scripting | ||
|---|---|---|
| Prev | Chapter 16. External Filters, Programs and Commands | Next |
Decompose an integer into prime factors.
bash$ factor 27417 27417: 3 13 19 37 |
Example 16-46. Generating prime numbers
1 #!/bin/bash
2 # primes2.sh
3
4 # Generating prime numbers the quick-and-easy way,
5 #+ without resorting to fancy algorithms.
6
7 CEILING=10000 # 1 to 10000
8 PRIME=0
9 E_NOTPRIME=
10
11 is_prime ()
12 {
13 local factors
14 factors=( $(factor $1) ) # Load output of `factor` into array.
15
16 if [ -z "${factors[2]}" ]
17 # Third element of "factors" array:
18 #+ ${factors[2]} is 2nd factor of argument.
19 # If it is blank, then there is no 2nd factor,
20 #+ and the argument is therefore prime.
21 then
22 return $PRIME # 0
23 else
24 return $E_NOTPRIME # null
25 fi
26 }
27
28 echo
29 for n in $(seq $CEILING)
30 do
31 if is_prime $n
32 then
33 printf %5d $n
34 fi # ^ Five positions per number suffices.
35 done # For a higher $CEILING, adjust upward, as necessary.
36
37 echo
38
39 exit |
Bash can't handle floating point calculations, and it lacks operators for certain important mathematical functions. Fortunately, bc gallops to the rescue.
Not just a versatile, arbitrary precision calculation utility, bc offers many of the facilities of a programming language. It has a syntax vaguely resembling C.
Since it is a fairly well-behaved UNIX utility, and may therefore be used in a pipe, bc comes in handy in scripts.
Here is a simple template for using bc to calculate a script variable. This uses command substitution.
variable=$(echo "OPTIONS; OPERATIONS" | bc) |
Example 16-47. Monthly Payment on a Mortgage
1 #!/bin/bash
2 # monthlypmt.sh: Calculates monthly payment on a mortgage.
3
4
5 # This is a modification of code in the
6 #+ "mcalc" (mortgage calculator) package,
7 #+ by Jeff Schmidt
8 #+ and
9 #+ Mendel Cooper (yours truly, the ABS Guide author).
10 # http://www.ibiblio.org/pub/Linux/apps/financial/mcalc-1.6.tar.gz
11
12 echo
13 echo "Given the principal, interest rate, and term of a mortgage,"
14 echo "calculate the monthly payment."
15
16 bottom=1.0
17
18 echo
19 echo -n "Enter principal (no commas) "
20 read principal
21 echo -n "Enter interest rate (percent) " # If 12%, enter "12", not ".12".
22 read interest_r
23 echo -n "Enter term (months) "
24 read term
25
26
27 interest_r=$(echo "scale=9; $interest_r/100.0" | bc) # Convert to decimal.
28 # ^^^^^^^^^^^^^^^^^ Divide by 100.
29 # "scale" determines how many decimal places.
30
31 interest_rate=$(echo "scale=9; $interest_r/12 + 1.0" | bc)
32
33
34 top=$(echo "scale=9; $principal*$interest_rate^$term" | bc)
35 # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
36 # Standard formula for figuring interest.
37
38 echo; echo "Please be patient. This may take a while."
39
40 let "months = $term - 1"
41 # ====================================================================
42 for ((x=$months; x > 0; x--))
43 do
44 bot=$(echo "scale=9; $interest_rate^$x" | bc)
45 bottom=$(echo "scale=9; $bottom+$bot" | bc)
46 # bottom = $(($bottom + $bot"))
47 done
48 # ====================================================================
49
50 # --------------------------------------------------------------------
51 # Rick Boivie pointed out a more efficient implementation
52 #+ of the above loop, which decreases computation time by 2/3.
53
54 # for ((x=1; x <= $months; x++))
55 # do
56 # bottom=$(echo "scale=9; $bottom * $interest_rate + 1" | bc)
57 # done
58
59
60 # And then he came up with an even more efficient alternative,
61 #+ one that cuts down the run time by about 95%!
62
63 # bottom=`{
64 # echo "scale=9; bottom=$bottom; interest_rate=$interest_rate"
65 # for ((x=1; x <= $months; x++))
66 # do
67 # echo 'bottom = bottom * interest_rate + 1'
68 # done
69 # echo 'bottom'
70 # } | bc` # Embeds a 'for loop' within command substitution.
71 # --------------------------------------------------------------------------
72 # On the other hand, Frank Wang suggests:
73 # bottom=$(echo "scale=9; ($interest_rate^$term-1)/($interest_rate-1)" | bc)
74
75 # Because . . .
76 # The algorithm behind the loop
77 #+ is actually a sum of geometric proportion series.
78 # The sum formula is e0(1-q^n)/(1-q),
79 #+ where e0 is the first element and q=e(n+1)/e(n)
80 #+ and n is the number of elements.
81 # --------------------------------------------------------------------------
82
83
84 # let "payment = $top/$bottom"
85 payment=$(echo "scale=2; $top/$bottom" | bc)
86 # Use two decimal places for dollars and cents.
87
88 echo
89 echo "monthly payment = \$$payment" # Echo a dollar sign in front of amount.
90 echo
91
92
93 exit 0
94
95
96 # Exercises:
97 # 1) Filter input to permit commas in principal amount.
98 # 2) Filter input to permit interest to be entered as percent or decimal.
99 # 3) If you are really ambitious,
100 #+ expand this script to print complete amortization tables. |
Example 16-48. Base Conversion
1 #!/bin/bash
2 ###########################################################################
3 # Shellscript: base.sh - print number to different bases (Bourne Shell)
4 # Author : Heiner Steven (heiner.steven@odn.de)
5 # Date : 07-03-95
6 # Category : Desktop
7 # $Id: base.sh,v 1.2 2000/02/06 19:55:35 heiner Exp $
8 # ==> Above line is RCS ID info.
9 ###########################################################################
10 # Description
11 #
12 # Changes
13 # 21-03-95 stv fixed error occuring with 0xb as input (0.2)
14 ###########################################################################
15
16 # ==> Used in ABS Guide with the script author's permission.
17 # ==> Comments added by ABS Guide author.
18
19 NOARGS=85
20 PN=`basename "$0"` # Program name
21 VER=`echo '$Revision: 1.2 $' | cut -d' ' -f2` # ==> VER=1.2
22
23 Usage () {
24 echo "$PN - print number to different bases, $VER (stv '95)
25 usage: $PN [number ...]
26
27 If no number is given, the numbers are read from standard input.
28 A number may be
29 binary (base 2) starting with 0b (i.e. 0b1100)
30 octal (base 8) starting with 0 (i.e. 014)
31 hexadecimal (base 16) starting with 0x (i.e. 0xc)
32 decimal otherwise (i.e. 12)" >&2
33 exit $NOARGS
34 } # ==> Prints usage message.
35
36 Msg () {
37 for i # ==> in [list] missing. Why?
38 do echo "$PN: $i" >&2
39 done
40 }
41
42 Fatal () { Msg "$@"; exit 66; }
43
44 PrintBases () {
45 # Determine base of the number
46 for i # ==> in [list] missing...
47 do # ==> so operates on command-line arg(s).
48 case "$i" in
49 0b*) ibase=2;; # binary
50 0x*|[a-f]*|[A-F]*) ibase=16;; # hexadecimal
51 0*) ibase=8;; # octal
52 [1-9]*) ibase=10;; # decimal
53 *)
54 Msg "illegal number $i - ignored"
55 continue;;
56 esac
57
58 # Remove prefix, convert hex digits to uppercase (bc needs this).
59 number=`echo "$i" | sed -e 's:^0[bBxX]::' | tr '[a-f]' '[A-F]'`
60 # ==> Uses ":" as sed separator, rather than "/".
61
62 # Convert number to decimal
63 dec=`echo "ibase=$ibase; $number" | bc` # ==> 'bc' is calculator utility.
64 case "$dec" in
65 [0-9]*) ;; # number ok
66 *) continue;; # error: ignore
67 esac
68
69 # Print all conversions in one line.
70 # ==> 'here document' feeds command list to 'bc'.
71 echo `bc <<!
72 obase=16; "hex="; $dec
73 obase=10; "dec="; $dec
74 obase=8; "oct="; $dec
75 obase=2; "bin="; $dec
76 !
77 ` | sed -e 's: : :g'
78
79 done
80 }
81
82 while [ $# -gt 0 ]
83 # ==> Is a "while loop" really necessary here,
84 # ==>+ since all the cases either break out of the loop
85 # ==>+ or terminate the script.
86 # ==> (Above comment by Paulo Marcel Coelho Aragao.)
87 do
88 case "$1" in
89 --) shift; break;;
90 -h) Usage;; # ==> Help message.
91 -*) Usage;;
92 *) break;; # First number
93 esac # ==> Error checking for illegal input might be appropriate.
94 shift
95 done
96
97 if [ $# -gt 0 ]
98 then
99 PrintBases "$@"
100 else # Read from stdin.
101 while read line
102 do
103 PrintBases $line
104 done
105 fi
106
107
108 exit |
An alternate method of invoking bc involves using a here document embedded within a command substitution block. This is especially appropriate when a script needs to pass a list of options and commands to bc.
1 variable=`bc << LIMIT_STRING 2 options 3 statements 4 operations 5 LIMIT_STRING 6 ` 7 8 ...or... 9 10 11 variable=$(bc << LIMIT_STRING 12 options 13 statements 14 operations 15 LIMIT_STRING 16 ) |
Example 16-49. Invoking bc using a here document
1 #!/bin/bash
2 # Invoking 'bc' using command substitution
3 # in combination with a 'here document'.
4
5
6 var1=`bc << EOF
7 18.33 * 19.78
8 EOF
9 `
10 echo $var1 # 362.56
11
12
13 # $( ... ) notation also works.
14 v1=23.53
15 v2=17.881
16 v3=83.501
17 v4=171.63
18
19 var2=$(bc << EOF
20 scale = 4
21 a = ( $v1 + $v2 )
22 b = ( $v3 * $v4 )
23 a * b + 15.35
24 EOF
25 )
26 echo $var2 # 593487.8452
27
28
29 var3=$(bc -l << EOF
30 scale = 9
31 s ( 1.7 )
32 EOF
33 )
34 # Returns the sine of 1.7 radians.
35 # The "-l" option calls the 'bc' math library.
36 echo $var3 # .991664810
37
38
39 # Now, try it in a function...
40 hypotenuse () # Calculate hypotenuse of a right triangle.
41 { # c = sqrt( a^2 + b^2 )
42 hyp=$(bc -l << EOF
43 scale = 9
44 sqrt ( $1 * $1 + $2 * $2 )
45 EOF
46 )
47 # Can't directly return floating point values from a Bash function.
48 # But, can echo-and-capture:
49 echo "$hyp"
50 }
51
52 hyp=$(hypotenuse 3.68 7.31)
53 echo "hypotenuse = $hyp" # 8.184039344
54
55
56 exit 0 |
Example 16-50. Calculating PI
1 #!/bin/bash
2 # cannon.sh: Approximating PI by firing cannonballs.
3
4 # Author: Mendel Cooper
5 # License: Public Domain
6 # Version 2.2, reldate 13oct08.
7
8 # This is a very simple instance of a "Monte Carlo" simulation:
9 #+ a mathematical model of a real-life event,
10 #+ using pseudorandom numbers to emulate random chance.
11
12 # Consider a perfectly square plot of land, 10000 units on a side.
13 # This land has a perfectly circular lake in its center,
14 #+ with a diameter of 10000 units.
15 # The plot is actually mostly water, except for land in the four corners.
16 # (Think of it as a square with an inscribed circle.)
17 #
18 # We will fire iron cannonballs from an old-style cannon
19 #+ at the square.
20 # All the shots impact somewhere on the square,
21 #+ either in the lake or on the dry corners.
22 # Since the lake takes up most of the area,
23 #+ most of the shots will SPLASH! into the water.
24 # Just a few shots will THUD! into solid ground
25 #+ in the four corners of the square.
26 #
27 # If we take enough random, unaimed shots at the square,
28 #+ Then the ratio of SPLASHES to total shots will approximate
29 #+ the value of PI/4.
30 #
31 # The simplified explanation is that the cannon is actually
32 #+ shooting only at the upper right-hand quadrant of the square,
33 #+ i.e., Quadrant I of the Cartesian coordinate plane.
34 #
35 #
36 # Theoretically, the more shots taken, the better the fit.
37 # However, a shell script, as opposed to a compiled language
38 #+ with floating-point math built in, requires some compromises.
39 # This decreases the accuracy of the simulation.
40
41
42 DIMENSION=10000 # Length of each side of the plot.
43 # Also sets ceiling for random integers generated.
44
45 MAXSHOTS=1000 # Fire this many shots.
46 # 10000 or more would be better, but would take too long.
47 PMULTIPLIER=4.0 # Scaling factor.
48
49 declare -r M_PI=3.141592654
50 # Actual 9-place value of PI, for comparison purposes.
51
52 get_random ()
53 {
54 SEED=$(head -n 1 /dev/urandom | od -N 1 | awk '{ print $2 }')
55 RANDOM=$SEED # From "seeding-random.sh"
56 #+ example script.
57 let "rnum = $RANDOM % $DIMENSION" # Range less than 10000.
58 echo $rnum
59 }
60
61 distance= # Declare global variable.
62 hypotenuse () # Calculate hypotenuse of a right triangle.
63 { # From "alt-bc.sh" example.
64 distance=$(bc -l << EOF
65 scale = 0
66 sqrt ( $1 * $1 + $2 * $2 )
67 EOF
68 )
69 # Setting "scale" to zero rounds down result to integer value,
70 #+ a necessary compromise in this script.
71 # It decreases the accuracy of this simulation.
72 }
73
74
75 # ==========================================================
76 # main() {
77 # "Main" code block, mimicking a C-language main() function.
78
79 # Initialize variables.
80 shots=0
81 splashes=0
82 thuds=0
83 Pi=0
84 error=0
85
86 while [ "$shots" -lt "$MAXSHOTS" ] # Main loop.
87 do
88
89 xCoord=$(get_random) # Get random X and Y coords.
90 yCoord=$(get_random)
91 hypotenuse $xCoord $yCoord # Hypotenuse of
92 #+ right-triangle = distance.
93 ((shots++))
94
95 printf "#%4d " $shots
96 printf "Xc = %4d " $xCoord
97 printf "Yc = %4d " $yCoord
98 printf "Distance = %5d " $distance # Distance from
99 #+ center of lake
100 #+ -- the "origin" --
101 #+ coordinate (0,0).
102
103 if [ "$distance" -le "$DIMENSION" ]
104 then
105 echo -n "SPLASH! "
106 ((splashes++))
107 else
108 echo -n "THUD! "
109 ((thuds++))
110 fi
111
112 Pi=$(echo "scale=9; $PMULTIPLIER*$splashes/$shots" | bc)
113 # Multiply ratio by 4.0.
114 echo -n "PI ~ $Pi"
115 echo
116
117 done
118
119 echo
120 echo "After $shots shots, PI looks like approximately $Pi"
121 # Tends to run a bit high,
122 #+ possibly due to round-off error and imperfect randomness of $RANDOM.
123 # But still usually within plus-or-minus 5% . . .
124 #+ a pretty fair rough approximation.
125 error=$(echo "scale=9; $Pi - $M_PI" | bc)
126 pct_error=$(echo "scale=2; 100.0 * $error / $M_PI" | bc)
127 echo -n "Deviation from mathematical value of PI = $error"
128 echo " ($pct_error% error)"
129 echo
130
131 # End of "main" code block.
132 # }
133 # ==========================================================
134
135 exit 0
136
137 # One might well wonder whether a shell script is appropriate for
138 #+ an application as complex and computation-intensive as a simulation.
139 #
140 # There are at least two justifications.
141 # 1) As a proof of concept: to show it can be done.
142 # 2) To prototype and test the algorithms before rewriting
143 #+ it in a compiled high-level language. |
See also Example A-37.
The dc (desk calculator) utility is stack-oriented and uses RPN (Reverse Polish Notation). Like bc, it has much of the power of a programming language.
Similar to the procedure with bc, echo a command-string to dc.
1 echo "[Printing a string ... ]P" | dc
2 # The P command prints the string between the preceding brackets.
3
4 # And now for some simple arithmetic.
5 echo "7 8 * p" | dc # 56
6 # Pushes 7, then 8 onto the stack,
7 #+ multiplies ("*" operator), then prints the result ("p" operator). |
Most persons avoid dc, because of its non-intuitive input and rather cryptic operators. Yet, it has its uses.
Example 16-51. Converting a decimal number to hexadecimal
1 #!/bin/bash
2 # hexconvert.sh: Convert a decimal number to hexadecimal.
3
4 E_NOARGS=85 # Command-line arg missing.
5 BASE=16 # Hexadecimal.
6
7 if [ -z "$1" ]
8 then # Need a command-line argument.
9 echo "Usage: $0 number"
10 exit $E_NOARGS
11 fi # Exercise: add argument validity checking.
12
13
14 hexcvt ()
15 {
16 if [ -z "$1" ]
17 then
18 echo 0
19 return # "Return" 0 if no arg passed to function.
20 fi
21
22 echo ""$1" "$BASE" o p" | dc
23 # o sets radix (numerical base) of output.
24 # p prints the top of stack.
25 # For other options: 'man dc' ...
26 return
27 }
28
29 hexcvt "$1"
30
31 exit |
Studying the info page for dc is a painful path to understanding its intricacies. There seems to be a small, select group of dc wizards who delight in showing off their mastery of this powerful, but arcane utility.
bash$ echo "16i[q]sa[ln0=aln100%Pln100/snlbx]sbA0D68736142snlbxq" | dc Bash |
1 dc <<< 10k5v1+2/p # 1.6180339887 2 # ^^^ Feed operations to dc using a Here String. 3 # ^^^ Pushes 10 and sets that as the precision (10k). 4 # ^^ Pushes 5 and takes its square root 5 # (5v, v = square root). 6 # ^^ Pushes 1 and adds it to the running total (1+). 7 # ^^ Pushes 2 and divides the running total by that (2/). 8 # ^ Pops and prints the result (p) 9 # The result is 1.6180339887 ... 10 # ... which happens to be the Pythagorean Golden Ratio, to 10 places. |
Example 16-52. Factoring
1 #!/bin/bash 2 # factr.sh: Factor a number 3 4 MIN=2 # Will not work for number smaller than this. 5 E_NOARGS=85 6 E_TOOSMALL=86 7 8 if [ -z $1 ] 9 then 10 echo "Usage: $0 number" 11 exit $E_NOARGS 12 fi 13 14 if [ "$1" -lt "$MIN" ] 15 then 16 echo "Number to factor must be $MIN or greater." 17 exit $E_TOOSMALL 18 fi 19 20 # Exercise: Add type checking (to reject non-integer arg). 21 22 echo "Factors of $1:" 23 # ------------------------------------------------------- 24 echo "$1[p]s2[lip/dli%0=1dvsr]s12sid2%0=13sidvsr[dli%0=\ 25 1lrli2+dsi!>.]ds.xd1<2" | dc 26 # ------------------------------------------------------- 27 # Above code written by Michel Charpentier <charpov@cs.unh.edu> 28 # (as a one-liner, here broken into two lines for display purposes). 29 # Used in ABS Guide with permission (thanks!). 30 31 exit 32 33 # $ sh factr.sh 270138 34 # 2 35 # 3 36 # 11 37 # 4093 |
Yet another way of doing floating point math in a script is using awk's built-in math functions in a shell wrapper.
Example 16-53. Calculating the hypotenuse of a triangle
1 #!/bin/bash
2 # hypotenuse.sh: Returns the "hypotenuse" of a right triangle.
3 # (square root of sum of squares of the "legs")
4
5 ARGS=2 # Script needs sides of triangle passed.
6 E_BADARGS=85 # Wrong number of arguments.
7
8 if [ $# -ne "$ARGS" ] # Test number of arguments to script.
9 then
10 echo "Usage: `basename $0` side_1 side_2"
11 exit $E_BADARGS
12 fi
13
14
15 AWKSCRIPT=' { printf( "%3.7f\n", sqrt($1*$1 + $2*$2) ) } '
16 # command(s) / parameters passed to awk
17
18
19 # Now, pipe the parameters to awk.
20 echo -n "Hypotenuse of $1 and $2 = "
21 echo $1 $2 | awk "$AWKSCRIPT"
22 # ^^^^^^^^^^^^
23 # An echo-and-pipe is an easy way of passing shell parameters to awk.
24
25 exit
26
27 # Exercise: Rewrite this script using 'bc' rather than awk.
28 # Which method is more intuitive? |