Fibonacci numbers (Oz)

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

Contents 1 Implementation 2 Recursive 3 Memoized recursion 4 Iteration 5 Test driver

Implementation

We describe several different implementations for calculating the fibonacci numbers in Oz:

<<Fib.oz>>=
functor
import
   System
   Application
define
   recursive fib
   memoized fib
   iterative fib
   testdriver
end

Recursive

Here is a very simple recursive implementation. This will become slow on big numbers, because the numbers are recalculated for each recursion.

<<recursive fib>>=
fun {RecursiveFib N}
   if N < 2 then N else {RecursiveFib N - 1} + {RecursiveFib N - 2} end
end

Memoized recursion

Although the recursive implementation given above is elegant and close to the mathematical definition, it is not very practical. Calculating the nth fibonacci number requires calculating two smaller fibonacci numbers, which in turn require two additional recursive calls each, and so on until all branches reach 1. As a consequence, the time required to calculate the fibonacci numbers is exponential in n (it is about Φⁿ, where Φ is the golden ratio). To remedy this, we can employ memoization to cache previous computations:

<<memoized fib>>=
Memo = {NewDictionary}
fun {MemoizedFib N}
   if {Dictionary.member Memo N}
   then {Dictionary.get Memo N}
   else
      FibN
   in
      if N < 2 then FibN = N else FibN = {MemoizedFib N - 1} + {MemoizedFib N - 2} end
      {Dictionary.put Memo N FibN}
      FibN
   end
end

This memoized recursive implementation makes use of Oz's mutable Dictionary datatype to store and retrieve previously computed values.

Iteration

Another alternative for fast computation of fibonacci numbers is a simple linear-time iterative approach which calculates each fibonacci number successively. Although Oz supports mutable variables and for-loops, we have chosen here to implement a compact iterative routine that performs a tail-recursive, accumulative calculation:

<<iterative fib>>=
fun {IterativeFib N}
   fun {Fib N F1 F2}
     if N < 1 then F1 else {Fib (N - 1) F2 (F1 + F2)} end
   end
in
   {Fib N 0 1}
end

Test driver

The test driver procedure runFib computes and prints the fibonacci numbers from n = 0 up to n = 30.

<<testdriver>>=
proc {RunFib F}
   for X in 0..30 do
      {System.showInfo "{" # {System.printName F} # " " # X # "} = " # {F X}}
   end
end

We apply RunFib to each of the implementations described above, and then exit.

<<testdriver>>=
{RunFib RecursiveFib}
{RunFib MemoizedFib}
{RunFib IterativeFib}
{Application.exit 0}

Download code