Fibonacci numbers (E)

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

Here we present several ways to compute the Fibonacci numbers using the language E.

Recursion

The recursive definition can be translated directly into E as follows:

<<fib_recursive.e>>=
#!/usr/bin/env rune
pragma.syntax("0.9")
def fib(n :(int >= 0)) :int {
  switch (n) {
    match == 0 { return 0 }
    match == 1 { return 1 }
    match _    { return fib(n-1) + fib(n-2) }
  }
}
testing

Here we've used a guard to ensure that the fib function cannot be passed a negative number (which would result in an infinite recursion).

We can test the fib function using a simple for-loop

<<testing>>=
for i in 0..20 {
  print(" ", fib(i))
}

which produces the following output:

 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

Recursion with memoization

Although the recursive implementation given above is elegant and close to the mathematical definition, it is not very practical. Calculating fib(n) 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 fib(n) is exponential in n (it is about Φⁿ, where Φ is the golden ratio). To remedy this, we can employ memoization to cache previous computations.

The memoization cache is an E FlexMap consisting of entries composed of a key n, and a corresponding value fib(n). We initialize the map with the first two Fibonacci numbers (the .diverge() turns the initial constant map into a mutable FlexMap):

<<fibmap>>=
def fibs := [0 => 0, 1 => 1].diverge()

The memoized fib function recursively computes and stores the value of fib(n) if it hasn't been previously stored in the fibs map. Otherwise it simply returns the memoized value of fib(n).

<<fib object>>=
fibmap
def fib(n :(int >= 0)) :int {
  if (!fibs.maps(n)) {
    fibs[n] := fib(n-1) + fib(n-2)
  }
  return fibs[n]
}

We can now use the memoized fib function just as we used the purely recursive one:

<<fib_memo.e>>=
#!/usr/bin/env rune
pragma.syntax("0.9")
fib object
for i in 0..20 {
  print(" ", fib(i))
}

One interesting test of our memoized fib function is to compare the execution time required for the purely recursive and memoized version of fib:

$ time ./fib_recursive.e
 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
real    5m3.129s
user    4m26.099s
sys     0m4.572s

$ time ./fib_memo.e
 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
real    0m12.297s
user    0m10.252s
sys     0m0.601s

The memoized version of the fib function is clearly substantially faster than the purely recursive version. In addition, based on timing results for a simple E Hello World program

$ time ./helloworld.e 
Hello World!
real    0m10.667s
user    0m9.293s
sys     0m0.563s

it's clear that a significant chunk of the reported execution time for the memoized fib function is startup overhead for the E interpreter.

Download code