Suite de Fibonacci

La suite de Fibonacci est définie par la récurrence suivante à deux termes :

F0 = 0 , F1 = 1
Fn = Fn-1 + Fn-2 , pour n > 1.

D'où une fonction C qui calcule le nème terme de la suite :

long fibonacci (int n) {
  int i;
  long a = 0, b = 1, c;
  
  for (i = 2 ; i <= n; i++) {
    c = a + b;
    a = b;
    b = c;
  }
  return b;
}
Cette fonction permet de construire la table des nombres de Fibonacci représentables sur 32 chiffres binaires :

n Fn
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
n Fn
11 89
12 144
13 233
14 377
15 610
16 987
17 1597
18 2584
19 4181
20 6765
n Fn
21 10946
22 17711
23 28657
24 46368
25 75025
26 121393
27 196418
28 317811
29 514229
30 832040
n Fn
31 1346269
32 2178309
33 3524578
34 5702887
35 9227465
36 14930352
37 24157817
38 39088169
39 63245986
40 102334155
n Fn
41 165580141
42 267914296
43 433494437
44 701408733
45 1134903170
46 1836311903
47 2971215073

La théorie classique des récurrences linéaires montre qu'on a :

Phi est le nombre d'or, qui vaut approximativement 1.618 ; le module de son conjugué vaut approximativement 0.618, et donc son influence dans la formule ci-dessus est rapidement négligeable. En particulier le rapport entre deux termes consécutifs de la suite de Fibonacci tend vers le nombre d'or.