Fibonacci numbers (E)

From LiteratePrograms
Jump to: navigation, search
Other implementations: bc | C | C Plus Plus templates | dc | E | Forth | FORTRAN | Haskell | Icon | Java | JavaScript | Lisp | Lua | occam | Oz | PIR | Prolog | Python | Sed | sh | sh, iterative | 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.


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

[edit] 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

[edit] 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 Φn, 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>>=
var 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). We encapsulate both the memoization cache and the fib function in an object with a single method, run (which E calls by default if no other methods are available.

<<fib object>>=
def makeFib() {
  fibmap

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

Because the memoized fib function is wrapped in an object, we have to make an object before we can test the function. However, since we used of the run method to define the fib function, the resulting object can be treated as if it is a function (i.e. there's no need to explicitly call a method by name):

<<fib_memo.e>>=
#!/usr/bin/env rune

pragma.syntax("0.9")

fib object

def fib := makeFib()
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 purelt 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
hijacker
hijacker
hijacker
hijacker