Algorithme d'Euclide et suite de Fibonacci

I) Objectif

   La suite ( F n ) de Fibonacci est définie par:   F 0 = F 1 = 1 et n N , F n + 2 = F n + 1 + F n .
   Nous allons montrer que le pire des cas, c'est à dire le cas où il faut faire le plus d'itérations pour l'algorithme d'Euclide est lorsque a et b sont deux termes consécutifs de cette suite de Fibonacci.

  Nous noterons N(a, b) le nombre d'itérations de la boucle while de la fonction pgcd(a, b). Ce nombre N(a, b) est aussi le nombre d'itérations de l'algorithme d'Euclide “réel”.  Par exemple N(637, 490) = 3.

  Précisément, pour k 2 , nous allons prouver que le plus petit (en un sens à préciser) couple d'entiers ( a , b ) tel que N ( a , b ) = k est ( a , b ) = ( F k + 1 , F k ) .

def pgcd(a, b):
    """ Calcul itératif du pgcd par l'algorithme d'Euclide"""
    while b > 0:
        a, b = b, a % b
    return a

II) Préparatifs

Nous avons besoin pour commencer de définir un ordre sur N 2 .

Etant donnés deux couples ( a , b ) et ( a ' , b ' ) d'entiers naturels alors:
    •     ( a , b ) ( a ' , b ' ) b < b '     ou     ( ( b = b ' ) et ( a a ' ) )
    ••     ( a , b ) < ( a ' , b ' ) ( a , b ) ( a ' , b ' )     et    ( a , b ) ( a ' , b ' )
    •••     ( a , b ) ( a ' , b ' ) ⇔   ( a ' , b ' ) ( a , b )     et    ( a , b ) > ( a ' , b ' ) ⇔   ( a ' , b ' ) < ( a , b ) .

Par exemple:

Q1) Comparer pour cet ordre les couples (0,3) , (1,1) , (1, 2), (2,1) , (2,2).

Q2) Soit A = ( a , b ) un couple de N 2 .
Représenter dans le plan l'ensemble des points M = ( a ' , b ' ) de N 2 tels que ( a , b ) ( a ' , b ' )

Q3) Justifier que tous les couples de N 2 sont comparables, c'est à dire que:
      ( a , b ) , ( a ' , b ' ) N 2    ( a , b ) ( a ' , b ' ) [ ( a , b ) < ( a ' , b ' ) ou ( a , b ) > ( a ' , b ' ) ]

Q4) Montrer que pour cet ordre, tout couple ( a , b ) N 2 a un successeur (lequel ?), mais pas forcément un prédécesseur. Préciser les couples n'ayant pas de prédécesseur.

Définition: Soient A, B ∈ N 2 . Alors:
    B est le prédécesseur de A ⇔ B < A et  ∀ M ∈ N 2 \ {A, B},  M < B ou M > A.
    B est le successeur de A ⇔ A < B et  ∀ M ∈ N 2 \ {A, B},  M < A ou M > B.

On rappelle que N ( a , b ) est le nombre d'itérations de la boucle while de la fonction   pgcd ( a , b ) .

  Etant donné k N * , on note  (s'il existe) pgcd_pire(k) le plus petit (pour l'ordre défini ci-dessus) couple ( A k , B k ) de N×N (avec A k B k > 0 ) pour lequel N ( A k , B k ) = k .
  On souhaite calculer ce couple expérimentalement puis théoriquement et vérifier puis démontrer que   ( A k , B k ) = ( F k + 1 , F k ) pour k 2 .

Q5) Montrer que: a , b N * , N ( a , b ) = N ( b + r , b )    avec r le reste de la division de a par b .

Q6) Pause...

Q7) En déduire que: k N * si ( A k , B k ) existe, alors B k A k < 2 B k .

Q8) Prouver que tant qu'elle est définie, la suite ( ( A k , B k ) ) est croissante pour l'ordre défini.

III) Algorithmes

Q9) Ecrire une fonction N_pgcd(a, b) calculant N(a, b) . Vérifier que  N_pgcd(1001,55) = 2 et N_pgcd(89,55) = 9.

Q10) Ecrire une fonction pgcd_pire(n) affichant, pour k variant de 1 à n, le plus petit couple ( a , b ) d'entiers avec a b > 0 pour lequel N ( a , b ) = k .  

   D'après Q7), il suffit de calculer N ( a , b ) pour les couple d'entiers ( a , b ) avec   0 < b a < 2 b classés dans l'ordre ( (1,1) , (2,2) , (3,2), (3,3) , (4,3) , (5,3) , ...).

fonction pgcd_pire(n):
    (a, b) = (1, 1)
    pour k variant de 1 à n:
        tant que N(a,b) < k:
            (a,b) = successeur((a,b))
        afficher (k, (a,b))

Par exemple, pgcd_pire(5) doit renvoyer:

pgcd_pire(1) = (1,1)
pgcd_pire(2) = (3,2)
pgcd_pire(3) = (5,3)
pgcd_pire(4) = (8,5)
pgcd_pire(5) = (13,8)
pgcd_pire(6) = (21,13)

  On constate expérimentalement que les cas les plus coûteux en nombre d'itérations se trouvent lorsque a et b sont deux termes consécutifs de la suite de Fibonacci ( F n ) = ( 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , .. )   et que ( A k , B k ) = pgcd_pire ( k ) = ( F k + 1 , F k ) pour k 2 .

IV) Preuves

Notons a n et b n les valeurs des paramètres a et b après la n ième itération de la boucle while de l'algorithme d'Euclide.
On a: { a 0 = a b 0 = b et { a n + 1 = b n b n + 1 = a n % b n pour n N , tant que b n > 0 .
On note N = N ( a , b ) . On a donc b N = 0 et pgcd ( a , b ) = a N = b N - 1 > 0 .

Q11) Démontrer que pour k 2 et n N , alors:    { a n = F k + 1 b n = F k { a n + 1 = F k b n + 1 = F k - 1 .

Q12 ) Prouver par récurrence pour k 2 que N ( F k + 1 , F k ) = k .

Q13) Démontrer que   b n + 1 + b n a n   pour n N * .

Q14) Montrer que   { a N - 1 F 2 b N - 1 F 1 , puis que { a N - 2 F 3 b N - 2 F 2 , puis par récurrence que { a N - n F n + 1 b N - n F n pour n { 1 , ... , N } et N 2 .

Q15) En déduire que a F N + 1 et   b F N , puis le résultat annoncé: ( A k , B k ) = pgcd_pire ( k ) = ( F k + 1 , F k ) pour k 2 .

V) Une majoration plus fine du coût de l'algorithme d'Euclide

On pose ϕ = 1 + 5 2 (φ est le nombre d'or).

Q16) Démontrer par récurrence que pour n ≥ 2,   F n > ϕ n - 1

Q17) En déduire que : b ϕ n - 1 N ( a , b ) n , puis que N ( a , b ) 2 + [ ln ( b ) ln ( ϕ ) ]

Q18) Justifier que cette majoration est meilleure que celle   N ( a , b ) 2 [ ln ( b ) ln ( 2 ) ] + 2 obtenue dans le cours / TD Euclide - Terminaison, correction et complexité.

© 2014 - Eric Obermeyer      Powered by      Corrigé