Exercice 12 - Pgcd

Le plus grand commun diviseur de deux entiers relatifs $a$ et $b$, noté $pgcd(a, b)$, est défini par la relation de récurrence $pgcd(a, b) = pgcd(b, a\ mod\ b)$, avec $pgcd(a, 0) = a$.

1. Ecrire une fonction récursive calculant le $pgcd$ de deux entiers relatifs.
2. Ecrire une fonction itérative retournant le $i$-ème nombre de fibonacci.
3. Ecrire les deux sous-programmes unsigned long pgcd(unsigned long a, unsigned long b) et unsigned long fibonacci(unsigned long l)
4. Tester la fonction $pgcd$ avec des nombres de fibonacci consécutifs. Qu'observez-vous ?
5. Si on s'intéresse au nombre d'appels récursifs nécessaires pour calculer un $pgcd$, quel est le pire des cas ?
6. Quel est la valeur du quotient $$\frac{F_{n+1}}{F_n}$$ ?
7. En déduire que les entrées de la forme $(F_{n+1}, F_n$ forment les pires cas.
8. Combien d'itérations sont nécesaires pour calculer $pgcd(F_{n+1}, F_n)$ ?
9. Prouver que $F_n$ est majoré par une suite géométrique.
10. Prouver que le nombre d'appels récursifs est majoré par un logarithme de base $$\phi = \frac{1 + \sqrt{5}}{2}$$.
11. Quelle est la complexité de $pgcd$, est-ce efficace ?