Fibonacci numbers (Erlang)
From LiteratePrograms
- Other implementations: ALGOL 68 | Alice ML | bc | C | C Plus Plus templates | dc | E | Eiffel | Erlang | Forth | FORTRAN | Haskell | Hume | Icon | Java | JavaScript | Lisp | Logo | Lua | Mercury | OCaml | occam | Oz | Pascal | PIR | PostScript | Python | Ruby | Scala | Scheme | Sed | sh | sh, iterative | Smalltalk | 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
- 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.
Here are the fibo functions possible in this all functional language and runtime.
To test them we pass the function as parameter to the print_nfibos/2.
Contents |
The fibonacci function
<<regular recursive fibonacci>>= fibo(0) -> 0 ; fibo(1) -> 1 ; fibo(N) when N > 0 -> fibo(N-1) + fibo(N-2) .
Tail recursive fibonacci
Given that the series of pairs of consecutive fibo values can be expressed in the following way
S0 = (fib0, fib1) = (0, 1) ;
for n >= 1, succ (fibn-1, fibn) = (fibn, fibn+1) = (fibn, fibn-1 + fibn) ;
Naming (fibn-1, fibn) as (result, next) then succ (result, next) = (next, (result+next))
<<tail recursive fibonacci>>= fibo2_tr( 0, Result, _Next) -> Result ; %% last recursion output fibo2_tr( Iter, Result, Next) when Iter > 0 -> fibo2_tr( Iter -1, Next, Result + Next) . fibo2( N) -> fibo2_tr( N, 0, 1) .
Fast tail recursive fibonacci
Using the following formula we can derive a few useful identities to speed up the computation.
Here are the useful identities:
- Fn + m = Fn − 1Fm + FnFm + 1 = (Fn + 1 − Fn)Fm + FnFm + 1
- Fn + m + 1 = FnFm + Fn + 1Fm + 1
If we can keep track of pairs of fibonacci numbers we end up with an algorithm identical to exponentiation by squaring:
<<fast fibonacci>>= fibo3(N) -> {Fib, _} = fibo3(N, {1, 1}, {0, 1}), Fib. fibo3(0, _, Pair) -> Pair; fibo3(N, {Fib1, Fib2}, Pair) when N rem 2 == 0 -> SquareFib1 = Fib1*Fib1, fibo3(N div 2, {2*Fib1*Fib2 - SquareFib1, SquareFib1 + Fib2*Fib2}, Pair); fibo3(N, {FibA1, FibA2}=Pair, {FibB1, FibB2}) -> fibo3(N-1, Pair, {FibA1*FibB2 + FibB1*(FibA2 - FibA1), FibA1*FibB1 + FibA2*FibB2}).
Test module
Let's print N fibonacci numbers in ascending order.
<<fib.erl>>= -module(fib). -export([fibo/1, fibo2/1, fibo3/1, print_nfibos/2]). %% print fibo arg. and result, with function as parameter print_nfibos( N, FiboFunc) -> printfibos( N, FiboFunc, 0). printfibos( 0, FiboFunc, N) -> %% last recursion Res = FiboFunc(N), io:fwrite("~w ~w~n", [N, Res]) ; printfibos( Iter, FiboFunc, N) when Iter > 0 -> Res = FiboFunc(N), io:fwrite("~w ~w~n", [N, Res]), printfibos( Iter -1, FiboFunc, N +1). regular recursive fibonacci tail recursive fibonacci fast fibonacci
Testing with the bytecode interpreter
erl> c(fib). %% compile fib.erl to bytecode
{ok,fib}
> fib:print_nfibos(10, fun fib:fibo/1). %% print n fibo values with function fib:fibo/1
produces the output
0 0 1 1 2 1 3 2 4 3 5 5 6 8 7 13 8 21 9 34 10 55 ok
Change the second parameter to "fun fib:fibo2/1" or "fun fib:fibo3/1" and you will get the same result, but faster.
| Download code |