Fibonacci numbers (OCaml)

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

This page explains how to implement Fibonacci numbers in OCaml. For this example, we will be using OCaml's "function" syntax for defining functions. We choose this style as it most closely resembles the problem definition.

Contents 1 A Recursive Solution 2 A Tail Recursive Solution 3 An Iterative Solution 4 Stream Based Solutions 5 Arbitrary Precision

A Recursive Solution

A simple recursive solution can be constructed in OCaml in a way that directly mirrors the mathematical definition of the function. We begin the code for this solution by defining a recursive value named fibonacci and indicate that this value will be a function

<<fibonacci.ml>>=
let rec fibonacci = function

We then use pattern matching on the function's parameter to handle the three cases given in the definition of the Fibonacci numbers. The first two cases we handle are the base cases of the recursion, when n = 0 or n = 1.

<<fibonacci.ml>>=
| 0 -> 0
| 1 -> 1

In the third case, when n > 1, a pair of recursive calls are made. The first call determines the F(n-1), and the second determines F(n-2), adding the two values to compute the F(n), the nth Fibonacci number.

<<fibonacci.ml>>=  
| n when n > 1 -> fibonacci (n-1) + fibonacci (n-2)

Finally, we add a final case to our pattern matching to catch all other cases. This is done for two reasons. First, Fibonacci numbers are only defined for non-negative integers. While that may be fine in math, when it comes to programming, one should be aware that invalid inputs may be used. These cases should be caught and handled. Here we raise an exception with an informative message that can be handled by the caller of fibonacci. Secondly, when using the when style guards in pattern matching, OCaml may be unable to determine if all possible cases are covered, and it issues a warning. Using the universal match pattern, _, we can catch any cases not covered by the above patterns (in this case anything involving negative integers).

<<fibonacci.ml>>=  
| _ -> raise (Invalid_argument "Fibonacci numbers are only defined over the non-negative integers")

A Tail Recursive Solution

let fib n = 
  let rec aux n b a = 
  if n <= 0 then a
  else aux (n-1) (a+b) b in
aux n 1 0

Will return 0 for n <= 0

An Iterative Solution

Unfortunately, the recursive solution shown above is a rather inefficient one, doubling the number of recursive calls for each successive value of n, thus requiring 2**n total function calls. A much more efficient iterative solution can be constructed, requiring just n recursive calls, at the expense of a bit of clarity.

For this solution, we will start with a recursive function definition that has a slightly different interface than the recursive solution above:

<<i_fib>>=  
let rec i_fib a b = function

Here, the parameters a and b represent the ith and i+1st Fibonacci numbers, and the third parameter represents how far we are from our goal. That is, if our goal is to compute F(n), and we have passed in F(i) as the parameter a, then the third parameter will be k = n-i.

If k = 0 or 1, then we can simply return a or b respectively, as they represent F(i) and F(i+1).

<<i_fib>>=  
| 0 -> a
| 1 -> b

If k is greater than 1, however, we simply move one step further in the iteration by computing Fibonacci number i+2 = a + b, and making a recursive call with parameters F(i+1), F(i+2), and (n-(i+1))=k-1. And finally we add our case to catch any invalid inputs.

<<i_fib>>=  
| k when k > 1 -> i_fib b (a+b) (k-1)
| _  -> raise (Invalid_argument "Fibonacci numbers are only defined over the non-negative integers")

Now, it should be easy to see that this definition will correctly compute the nth Fibonacci number when the initial arguments are 0 (F(0)), 1 (F(1)), and n. Unfortunately, this function requires the caller to pass in more arguments to compute the nth Fibonacci number than with the recursive solution. Additionally, if incorrect values are passed in for a and b, the returned value will not be equal to the nth Fibonacci number. In order to aleviate both of these problems, we will use i_fib as a function local to a wrapper function that presents the same interface to the caller as the recursive solution does..

<<fibonacci.ml>>=
let iterative_fib n =
  i_fib
  in
  i_fib 0 1 n

Stream Based Solutions

One can also use the streams of OCaml to build the Fibonacci numbers in a lazy fashion. This is host easily done with the camlp4 stream building syntax. To enable the use of this syntax in the OCaml toplevel environment, first enter the following directives:

<<fibonacci.ml>>=
#load "camlp4o.cma";; 
#load "pa_extend.cmo";;

Now the Fibonacci sequence can be defined as a function that takes in the ith and i+1st Fibonacci numbers and returns an infinite stream of Fibonacci numbers starting from i.

<<fibonacci.ml>>=
let rec f a b = [< 'a; f b (a+b) >]

One can see how this works by introducing the next parser, that strips the head off of the specified stream and returns it:

<<fibonacci.ml>>=
let next = parser [< 'x >] -> x

Some examples of the arbitrary precision variants are:

# let fibs = f 0 1;;
val fibs : int Stream.t = <abstr>
# next fibs;;
- : int = 0
# next fibs;;
- : int = 1
# next fibs;;
- : int = 1
# next fibs;;
- : int = 2
# next fibs;;
- : int = 3
# next fibs;;
- : int = 5
# next fibs;;
- : int = 8

Arbitrary Precision

One minor problem with all of these solutions is that they are defined using the native int type in OCaml which has an upper limit of (2**30) - 1 on 32 bit systems, and (2**62) - 1 on 64 bit systems. Because of this, the results will be incorrect for larger values of n (e.g. n > 44 on 32 bit systems). This can be fixed by using OCaml's arbitrary precision integer Big_int module. To use this module in the toplevel, enter the following directive:

<<fibonacci.ml>>=
#load "nums.cma";; 
open Big_int;;

Now we can rewrite the examples using the Big_int module:

<<fibonacci.ml>>=
let bfib n =
  let rec bfib_i a b = function
  | 0 -> a
  | 1 -> b
  | n when n > 1 ->  bfib_i b (add_big_int a b) (n-1)
  | _ -> raise (Invalid_argument "Fibonacci numbers are only defined over the non-negative integers")
  in
  bfib_i zero_big_int unit_big_int n

<<fibonacci.ml>>=
let rec big_f a b = [< 'a; big_f b (add_big_int a b) >]
let big_fibs = big_f zero_big_int unit_big_int
let big_next = parser [< 'x >] -> string_of_big_int x

# iterative_fib 44;;
- : int = 701408733
# string_of_big_int (bfib 44);;
- : string = "701408733"
# iterative_fib 45;;
- : int = -1012580478
# string_of_big_int (bfib 45);;
- : string = "1134903170"
# big_next big_fibs;;
- : string = "0"
# big_next big_fibs;;
- : string = "1"
# big_next big_fibs;;
- : string = "1"
# big_next big_fibs;;
- : string = "2"
# big_next big_fibs;;
- : string = "3"
# big_next big_fibs;;
- : string = "5"
# big_next big_fibs;;
- : string = "8"

Download code