Fibonacci numbers


Algorithm description

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

F0=0, F1=1, Fn=Fn-1+Fn-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 nt the value of m at the end of the tth run through the loop and n1 = floor(n/2). Then it's plain to see that nt= floor(nt-1/2) <= nt-1/2 for 2 <= t <= m. Furthermore nt <= nt-1/2 <= nt-2/4 <= ... <=n1/2t-1 <= n/2t and m = 1 + floor(lb(n)). These equations show that nm <= n/2m < 1. But nm is a non-negative integer, therefore nm = 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 ]