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.
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
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.
[AHU83, p. 355] [BB93, p. 36] [Sed88, p. 52]
[ Samples Overview | Bibliography | WOOP Project ]