Fibonacci numbers

Larry Bartholdi & his gang

July 24, 2024

We will discuss generation of Fibonacci numbers [LEONARDO DA PISA in Liber Coniculorum, vol. I, p. 283–284]. This family of numbers is recursively defined over $\cal {N}$ by

F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2.

Our goal is to simulate this processus in PCSCHEME code, and then to derive a closed form for Fn.

Here would be a first try: (define (fibo n) (if (< n 2) n (+ (fibo (- n 1)) (fibo (- n 2)))))

This is a very poor algorithm indeed: |(fibo n)| rises exponentially (as we shall soon see), and the algorithm sums ones and zeroes, so its running time is obviously exponential.

A better method comes from the observation that some values are computed many times: |(fibo 0)| and |(fibo 1)| are computed roughly |(fib n)| times; and figures decrease rapidly. If we memorize the values of |(fib 0)| through |(fib n)|, which requires linear storage, the execution time becomes linear. In fact, we can do even better, as only the last two evaluations are needed. This is trivially coded as: (define (fib n) (define (fibintern a0 a1 n) (if (= n 0) a0 (fibintern a1 (+ a0 a1) (-1+ n)))) (fibintern 0 1 n))

We now want to approximate |(fib n)| by a closed form. For that purpose, let ξ, η be the solutions of x2 - x - 1 = 0, and define

Φn : = $\displaystyle {\frac{{\xi^n - \eta^n}}{{\xi^{-1} - \eta^{-1}}}}$.

Obviously, Φ satisfies the defining properties of F, and this is the expression we are after.

To make matters more complicated, though, we may 'hard-fit' a double exponential onto the Fibonacci sequence by picking out a few values. Let us assume we know the base of the two exponentials: (define x (/ (+ 1 (sqrt 5)) 2)) (define y (/ (- 1 (sqrt 5)) 2))

Picking out the values of |(fib m)| and |(fib n)|, we solve the linear equation system: (define (ab m n) (let ((x^m (expt x m)) (x^n (expt x n)) (y^m (expt y m)) (y^n (expt y n)) (fibm (fib m)) (fibn (fib n))) (list (/ (- (* fibm y^n) (* fibn y^m)) (- (* x^m y^n) (* x^n y^m))) (/ (- (* fibm x^n) (* fibn x^m)) (- (* y^m x^n) (* y^n x^m)))))) Yielding a list of two coefficients, that of |x| and |y| respectively. These two coefficients turn out to be both $\sqrt{{5}}$.

A first guess would be to fit a simple exponential to the sequence. This is done by this routine, whose performance is acceptable, especially for large n. (define (fiba n) (/ (expt x n) (sqrt 5)))

A perfect fit can be attained if we care to compute both exponentials. The result is correct to a few ulp even for small n. (define (fibb n) (/ (- (expt x n) (expt y n)) (sqrt 5)))

This simple code will compare the double-exponential fit to the original sequence and confirm our predictions. (define (errf n) (/ (- (fib n) (fiba n)) (fib n)))

Written with LATEXand SchemeWEB.