Fibonacci numbers

Algorithm description

A well-known recurrence relation is the one that defines the fibonacci numbers. The fibonacci numbers are defined as follows:

F₀=0, F₁=1, F_n=F_n-1+F_n-2 for n>=2

This defines the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21 and so on.

Algorithm implementation

 1  function fib (n : in natural) return natural 
 2  is
 3      i,h : natural := 1;
 4      j,k : natural := 0;
 5      t : natural;
 6  begin
 7      if n=0 then
 8          return(0); 
 9      end if;
10      if n=1 then
11          return(1);
12      end if;
13      discrete l:=n in reverse 1..n
14          new l := l/2
15      loop
16          if (l mod 2)/=0 then
17              t := j*h;
18              j := i*h + j*k + t;
19              i := i*k + t;
20          end if;
21          t := h*h;
22          h := 2*k*h + t;
23          k := k*k + t;
24          l := l/2;
25      end loop;
26      return (j);
27  end fib;

[ Sourcefile ]

Notes on design/Worst Case Performance

The improvement of this algorithm compared to a simple recursive program lies in the performance; this implementation uses

log n

iterations:

Be n_t the value of m at the end of the t^th run through the loop and n₁ = floor(n/2). Then it's plain to see that n_t= floor(n_t-1/2) <= n_t-1/2 for 2 <= t <= m. Furthermore n_t <= n_t-1/2 <= n_t-2/4 <= ... <=n₁/2^t-1 <= n/2^t and m = 1 + floor(lb(n)). These equations show that n_m <= n/2^m < 1. But n_m is a non-negative integer, therefore n_m = 0, which is the condition for the termination of the loop. We conclude that the loop is executed m times in the worst case, so our algorithm needs O(log n) in time.

Selected Bibliography

[AHU83, p. 355] [BB93, p. 36] [Sed88, p. 52]

[ Samples Overview | Bibliography | WOOP Project ]