L’algorithme d’Euclide est basé sur le fait que le pgcd de a et b est aussi égal au pgcd de b et r, où r est le reste de la division euclidienne de a par b (en supposant que a>b) [1]. Pour l’implémenter, on a donc besoin de deux variables a et b, et chaque passage dans la boucle remplace a par b et b par r. Ces remplacements doivent être parfaitement simultanés sinon le calcul est entaché d’erreur (doit-on remplacer a par l’ancien b ou par le nouveau b ?).
Calcul parallèle
On en arrive donc à la recherche d’un algorithme parallèle : Si deux ordinateurs calculent chacun de son côté, l’un a, l’autre b, à eux deux ils iront deux fois plus vite en moyenne que si un seul d’entre eux faisait tout le travail à lui seul. À condition que ce soit possible !
L’affectation simultanée de deux variables est la spécialité du langage Lua, qui en plus possède un interpréteur en ligne, ça tombe bien ! Donc si on copie-colle le script suivant dans la fenêtre qui est à l’adresse ci-dessus, on peut calculer des pgcd par la méthode d’Euclide :
a=3600
b=3024
while(b>0) do
a,b = b,a % b
end
io.write("Le pgcd des deux nombres est ",a,"\n")En réalité il ne s’agit pas réellement de calcul parallèle mais de calcul matriciel : Lua considère que a,b est un vecteur dont les deux coordonnées sont mises à jour simultanément. Donc le même raccourci est implémentable avec SciLab ou Euler Math Toolbox puisque ces logiciels sont basés sur le calcul matriciel.
Cependant le langage à la mode en calcul parallèle est Scratch, alors autant essayer avec Scratch : Puisqu’il y a deux variables à traiter, on peut les confier à deux lutins [2]. Le plus grand des deux nombres entiers (qui s’appelait a ci-dessus) est confié au lutin « Buffalo » [3] et le plus petit au lutin « Bill », représenté par un pigeon posé sur « Buffalo ». Le remplacement simultané des deux variables « Nombre de Buffalo » et « Nombre de Bill » mène à un calcul faux (le pgcd est égal à 0, quelles que soient les valeurs de a et b). On doit donc créer une variable abritant temporairement le reste de la division euclidienne de a par b, le temps que a soit remplacé par b. La synchronisation des transformations de données se fait par des messages envoyés par la « scène » aux deux lutins. En calcul parallèle, on parle de sémaphore (informatique). Voici le travail du sémaphore :
puis celui du lutin qui divise (Buffalo) :
et enfin celui du lutin qui abrite le plus petit des nombres entiers :
À la fin de l’exécution du programme, le pgcd est affiché en haut à gauche de l’écran. Le programme au format « sb » (scratch) est téléchargeable ci-dessous (clic droit puis « enregistrer sous »).
Ceci dit, le calcul parallèle n’est pas du tout au programme de Seconde, donc une réalisation séquentielle est attendue des élèves qui auront le bonheur d’être interrogés par leur prof de maths sur ce sujet...
Réalisation itérative
Cette réalisation où un seul processus fait séquentiellement le remplacement de a par b et b par le reste de la division euclidienne (avec une troisième variable pour les raisons évoquées ci-dessus) peut très bien être faite sous Scratch, mais je lui préfère personnellement JavaScript, en raison de la rapidité de la mise au point (y compris le débogage) avec les outils de développements existants : En bref, j’ai préféré choisir un outil plutôt qu’un langage.
Avec ce magnifique interpréteur en ligne qui est particulièrement adapté à des TP en Seconde (surtout si on s’en sert hors-ligne, ainsi on n’est pas tributaire d’un bon fonctionnement du réseau), le code produit en quelques minutes, débogage compris [4] est celui-ci :
var a=demander("Quel est le plus grand des deux nombres ?");
var b=demander("Quel est le plus petit des deux nombres ?");
while(b>0){
var t=a%b;
a=b;
b=t;
}
afficher("Le pgcd des deux nombres est ",a);Autre outil particulièrement efficace, l’éditeur de CaRMetal donne quelque chose de plus « pro » avec des fenêtres d’alerte du plus bel effet ; le « CarScript » est légèrement différent du précédent :
a=Input("quel est le plus grand nombre ?");
b=Input("quel est le plus petit nombre ?");
while(b>0){
var t=a%b;
a=b;
b=t;
}
Prompt("Le pgcd des deux nombres est "+a);On voit une différence au niveau de la création de l’affichage : Alors que l’éditeur en ligne affiche une liste de variables dont certaines sont des chaînes de caractères, CaRMetal affiche un seul texte, obtenu en concaténant un vrai texte (chaîne de caractères) et un nombre. Et l’affichage se fait dans une fenêtre ad hoc et pas directement dans l’outil de développement. Cependant les versions diffèrent peu...
On peut même profiter de l’intégration de JavaScript dans le format « web 2.0 » pour créer un fichier html comme celui qui est téléchargeable ci-dessous (« pgcd.html »). Cependant cela nécessite une petite connaissance du langage html et n’est guère réalisable en classe (ou alors en devoir maison ?) sauf si on fournit aux élèves un gabarit où seul le code JavaScript reste à écrire (celui qui a été reproduit dans le tableau du bas de la page « pgcd.html »).
Réalisation récursive
Ceci dit, bien que nous quittions ainsi le programme de Seconde, la définition en tête de l’article « le pgcd de a et b est égal au pgcd de b et r » appelle une écriture récursive de l’algorithme. Surprenant, ça marche ! Bien que des langages soient spécialisés dans la récursivité (on pense à Maxima, pari->[http://pari.math.u-bordeaux.fr/down...] ou l’excellent xlogo mais il y en a plein d’autres), là encore une version JavaScript va être donnée, et là encore c’est plus à cause d’un outil qu’à cause du langage, puisqu’il s’agit d’un CarScript :
function gcd(a,b) {
// Implémentation de l'algorithme d'Euclide pour calculer un pgcd
if ((b % a) == 0){return (a);
} else {return (gcd(a,b-a));
}
}
for(i=1;i<4;i++){
// numérateurs
for(j=1;j<8;j++){
// dénominateurs
if(gcd(i,j) == 1){
// seulement si la fraction est irréductible
for(k=-4;k<4;k++){
// translations (pour éviter les trous)
a=Point("",k+i/j,1/j/j/2);
// centre du cercle
b=Point("",k+i/j,0);
// Point de contact avec l'axe des abscisses
c=Circle("",a,b);
SetRGBColor(c,32*i,2*i*j,16*j);
// La couleur du cercle dépend de sa taille
SetFilled(c,"true");
// On voit mieux si on le remplit
Hide(a);
Hide(b);
a=Point("",k-i/j,1/j/j/2);
b=Point("",k-i/j,0);
c=Circle("",a,b);
SetRGBColor(c,32*i,2*i*j,16*j);
SetFilled(c,"true");
Hide(a);
Hide(b);
}
}
}
}Seules les 9 premières lignes concernent la fonction pgcd elle-même (fonction de deux variables soit dit en passant), le reste concerne une application de cette fonction pgcd, qui est utilisée dans la suite pour mettre des fractions sous forme irréductible : En effet, on montre que tous les cercles centrés sur les points de coordonnées 
et ayant pour rayon 
, où 
est irréductible, sont tangents ou disjoints. Un tel cercle s’appelle un cercle de Ford.
Le CarScript ci-dessus a servi à fabriquer la diapo numéro 5 de ce diaporama CaRMetal
Mercredi 12 septembre 2012, 14h-17h30, salle S23.6 du Parc technologique universitaire (Saint-Denis)
Commentaires