Fibonacci numbers
The sequence 0,1,1,2,3,5,8,13,21,34,..., in which each number is the sum of the preceding two, was originated in 1202 by the Italian mathematician Leonardo Pisano (Leonardo of Pisa), who sometimes called Leonardo Fibonacci (Filius Bonacci, son of Bonaccio). Fibonacci numbers are defined by the recurrence relation
F0=0;F1=1;...;FN=FN-1+FN-2 for N>=2
Effective algorithm (see Technique: Recursion elimination) for calculation Nth Fibonacci number follows.
FIB: procedure
parse arg N
if N = 0 | N = 1 then return N
A = 0; B = 1
do N - 1
parse value(B (B + A)) with A B
end
return B
|
The worst case of Euclid's algorithm for computation GCD(A,B) occurs when A and B are consecutive Fibonacci numbers.
For testing this property we can arrange the FIB procedure. When we change the last statement to return B A, it'll return consecutive Fibonacci number Nth and (N-1)th.
In Chapter 9 of N. Wirth's book Systematisches Programmieren appears general formula for Nth Fibonacci number. We use it in the GENERAL_FIB function.
GENERAL_FIB: procedure
parse arg N, P
if N = 1 then return 1
Sqrt5 = SQRT(5, P); C = (1 + Sqrt5) / 2
return FORMAT(C ** N / Sqrt5,,0)
|
For N=10000 and P=2100 the FIB program requires 8.34 seconds but the GENERAL_FIB requires 63.39 sec. When we use the special function SQRT5 returning the beforehand computed value SQRT(5,2100) then GENERAL_FIB requires 26.47 seconds.
CONNECTIONS
|
