A well-known recurrence relation is the one that defines the fibonacci numbers. The fibonacci numbers are defined as follows:
F_{0}=0, F_{1}=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.
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 ]
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_{1} = 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_{1}/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.
[AHU83, p. 355] [BB93, p. 36] [Sed88, p. 52]
[ Samples Overview | Bibliography | WOOP Project ]