Fibonacci numbers (sh, iterative)

From LiteratePrograms

Jump to: navigation, search
Other implementations: Alice ML | bc | C | C Plus Plus templates | dc | E | Eiffel | Erlang | Forth | Haskell | Hume | Icon | Java | JavaScript | Lisp | Logo | Lua | Mercury | OCaml | occam | Oz | Pascal | PIR | PostScript | Python | Ruby | Scala | Scheme | Sed | sh | sh, iterative | T-SQL | Visual Basic .NET

The Fibonacci numbers are the integer sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, ..., in which each item is formed by adding the previous two. The sequence can be defined recursively by

F(n) = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F(n-1)+F(n-2) & n > 1 \\ \end{cases} .

Fibonacci number programs that implement this definition directly are often used as introductory examples of recursion. However, many other algorithms for calculating (or making use of) Fibonacci numbers also exist.


Generating the first few fibonacci numbers in a POSIX Shell:

[edit]

implementation

This is an iterative implementation, so instead of the recursive definition above, we use the formula

\mbox{fibs} = 0 , 1 , \mbox{fibs}_{0\ldots\infty}\ +\ \mbox{fibs}_{1\ldots\infty}

and implement it with the following loop 

a,b = 0,1
loop {
    yield a
    a,b = b, a+b 
}

<<fibonacci.sh>>=
#!/bin/sh
initialize state
while true; do
    yield first value
    update state
done

We could use shell variables to implement the state, but parallel assignment is easier with the positional parameters. The POSIX shell performs arithmetic expansions, so we'll try using them to do the sum. 

<<initialize state>>=
set -- 0 1
<<update state (first try)>>=
set -- $2 $(($1+$2))

To yield the first value all we need do is print the first parameter. 

<<yield first value>>=
echo $1
[edit]

refinement

Sure enough, this sequence starts out well: 

> sh fibonacci.sh | head -11
0
1
1
2
3
5
8
13
21
34
55

but by the 50th line, F(49) has obviously overflowed the shell's arithmetic. So perhaps we should borrow an idea from the recursive sh implementation and use an external arbitrary-precision package to evaluate the sums? 

<<update state (second try)>>=
set -- $2 $(dc "$1 $2 + p")

However, by the 333th line, F(332) runs into trouble, because dc pretty-prints the output for a 70+ digit result. By discarding all the extraneous characters we can mitigate this overly-helpful behavior. 

<<update state>>=
set -- $2 $(dc -e "$1 $2 + p" | tr -cd "[0-9]")

Now our program happily yields a 200+ digit result for F(1000)
(and a much longer one for F(2005)) 

> sh fibonacci.sh | sed -n '1001{p;q;}'
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
> sh fibonacci.sh | sed -n '2006{p;q;}'
46852600298055947871347159552877348883016598667579666121068607250933338025150662196445042393682993546898356896464346048214111545098503421477515666629326719004287741506349295212254756663843983831644410910292272148019586623569601244805557609991712285173149932788787519142120100061671455759635656953660995586804142989200178971496381031035783701810508180109386510974966175633982948458557222003800352979942704043730514564505
Download code
Retrieved from "http://en.literateprograms.org/Fibonacci_numbers_%28sh%2C_iterative%29"
Personal tools