mercredi 17 juin 2015

PGCD et Algorithmes.

La calculatrice HP-50G dispose bien sûr de plusieurs fonctions natives pour effectuer des calculs "autour du" PGCD de deux nombres entiers (ou de deux polynômes). La plus simple est la fonction GCD qui calcule tout simplement le PGCD de deux nombres entiers placés dans les niveaux 1 et 2 du stack.
Il existe aussi IEGCD qui prends deux entiers a et b en argument dans le stack et qui renvoie trois entiers relatifs: le pgcd puis deux entiers relatifs u et v tels que a.u + b.v = pgcd(a,b) (Bézout n'est pas loin).
Référez vous au manuel avancé pour savoir dans quel menu trouver ces fonctions sinon utiliser la fonction de recherche dans le catalogue en faisant RS CAT (touche SYMP) puis ALPHA G pour faire apparaître les fonctions commençant par G, ensuite faire défiler jusqu'à GCD puis appuyer sur F1 dans le soft menu pour afficher HELP pour avoir l'aide sur la fonction ou faites OK toujours dans le soft menu pour vous servir de la fonction.

Il peut être aussi intéressant parfois de réécrire quelques petits programmes surtout que l'arithmétique et l'algorithme d'Euclide sont au programme de Terminale S Spé Maths.
Je vais donc reprendre l'algorithme des soustractions successives présenté précédemment dans un article sur la HP-35S puis présenter l'algorithme d'Euclide qui est bien sûr bien plus rapide pour des grands nombres (doux euphémisme comme vous pourrez le voir plus loin en calculant le temps d'exécution des programmes).

Vous trouverez donc ci-dessous le programme qui calcule le PGCD de deux nombres entiers positifs X et Y en utilisant l'algorithme des soustractions que voici:

Tant que ( Y > 0 )
{
    Si ( X > Y ) Alors ( X = X - Y ) Sinon ( Y = Y - X) 
}
Retourne X

Le programme correspondant est alors le suivant: il prends bien sûr les deux nombres X et Y sur les niveaux 1 et 2 du stack puis calcule leur PGCD.

<< 
  WHILE DUP 0 >
  REPEAT
    IF DUP2 - 0 >
    THEN SWAP OVER -
    ELSE OVER -
    END 
  END DROP
>>

Vous trouverez ensuite ci-dessous le programme qui calcule le PGCD de deux nombres entiers positifs X et Y en utilisant l'algorithme d'Euclide (étudié en Spé Maths en Terminale S) que voici:

Tant que ( Y ≠ 0 )
{
    R = X Modulo Y 
    X = Y
    Y = R
}
Retourne X

Note: Modulo signifie "reste de la division euclidienne de X par Y".

Le programme correspondant est le suivant: il prends toujours deux nombres sur les niveaux 1 et 2 du stack puis calcule leur PGCD avec l'algorithme d'Euclide.

<< 
  WHILE OVER MOD DUP 0 
  REPEAT
    SWAP
  END DROP
>>

Voici trois exemples à tester: le PGCD de 789456 et 3211 est 1, le PGCD de 2001 et 78 est 3, le PGCD de 205655 et 1215 est 5.

Si vous voulez vous amuser à mesurer les temps d'exécution des deux programmes précédents et de celui de la HP-50G à travers sa fonction GCD, essayez le petit programme suivant:

<< 
  TICKS ROT ROT PGCD1
  SWAP TICKS SWAP - B⟶R
  8192 /
  "Durée" ⟶TAG
>>

Appelez chacun des deux programmes précédents PGCD1 pour Euclide et PGCD2 pour les soustractions successives.
Pour l'utiliser entrez les deux nombres dans le stack sur les niveaux 1 et 2, puis lancez plusieurs fois ce programme que vous aurez enregistré sous le nom TPGCD par exemple.
En sortie vous trouverez sur le stack le PGCD puis le temps écoulé pour le calcul ;-)

Pour utiliser le programme natif de la calculatrice, c'est la même chose, c'est très simple:

<< 
  TICKS ROT ROT GCD
  SWAP TICKS SWAP - B⟶R
  8192 /
  "Durée" ⟶TAG
>>

Essayez par exemple avec 789456 et 3211, vous trouverez 0.02sec, 0.45sec et 20,13 sec respectivement pour la fonction native, l'algorithme d'Euclide et celui des soustractions.

Liens intéressants:
Algorithmes des soustractions successives et d'Euclide.

Je ferai un autre article très prochainement avec le théorème (identité) de Bézout et le test de primalité (nombres premiers).

A bientôt !!

Aucun commentaire:

Enregistrer un commentaire