Fibonacci en Θ(log n) — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 13)

Fibonacci en

Θ (lo g n)

Diviser pour régner · niveau 2

Énoncé

Avec $M = (0111)$ , on admet que $M^{n} = (f (n - 1) f (n) f (n) f (n + 1))$ pour $n \geq 1$ , où $f (0) = 0$ , $f (1) = 1$ et $f (n) = f (n - 1) + f (n - 2)$ . Écrire une fonction récursive qui calcule $M^{n}$ en $Θ (lo g n)$ produits de matrices $2 \times 2$ de long, puis une fonction qui retourne $f (n)$ . Vérifier $f (90) = 2880067194370816120$ . Jusqu'à quelle valeur de $n$ le résultat tient-il dans un long ?

Corrigé

On calcule $M^{n}$ par exponentiation rapide : $M^{n} = (M^{⌊ n /2 ⌋})^{2}$ si $n$ est pair, et $(M^{⌊ n /2 ⌋})^{2} \times M$ sinon.


static long[][] produit(long[][] A, long[][] B) {
    return new long[][] {
        {A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1]},
        {A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1]}};
}
static long[][] puissance(long[][] M, int n) {   // M^n, n >= 0
    if (n == 0) return new long[][] {{1, 0}, {0, 1}};
    long[][] R = puissance(M, n / 2);            // M^(n/2)
    R = produit(R, R);                           // M^(2(n/2))
    return n % 2 == 0 ? R : produit(R, M);
}
static long fib(int n) {
    return puissance(new long[][] {{0, 1}, {1, 1}}, n)[0][1];
}


13.7 : f(10) = 55, f(90) = 2880067194370816120, f(92) = 7540113804746346429

Chaque appel divise $n$ par deux et fait au plus deux produits de matrices $2 \times 2$ (huit multiplications chacun) : $Θ (lo g n)$ opérations. Le plus grand terme représentable est $f (92)$ : $f (93) \approx 1, 2 \cdot 1 0^{19}$ dépasse $2^{63} - 1 \approx 9, 2 \cdot 1 0^{18}$ . Au-delà, il faut BigInteger.

Fibonacci en Θ(logn)

Énoncé

Corrigé

Fibonacci en $Θ (lo g n)$