The goal
Le but
The page Euclid’s Algorithm, in Mathematics for Kids, shows some JavaScript code. In this lesson, you write it yourself, with everything you have learned.
La page L’algorithme d’Euclide, dans les mathématiques pour les jeunes, montre du code JavaScript. Dans cette leçon, tu l’écris toi-même, avec tout ce que tu as appris.
Reminder: the greatest common divisor (GCD) of two numbers is the biggest whole number that divides both. The common divisors of 12 and 18 are 1, 2, 3 and 6, so the GCD of 12 and 18 is 6.
Un rappel : le plus grand commun diviseur (PGCD) de deux nombres est le plus grand nombre entier qui les divise tous les deux. Les diviseurs communs de 12 et 18 sont 1, 2, 3 et 6 : le PGCD de 12 et 18 est donc 6.
Step 1: search
Étape 1 : chercher
The first idea is to try numbers. The GCD cannot be bigger than the smaller of the two numbers: so start from there, and go down one by one. The first number that divides both a and b is the GCD. Since 1 divides every number, the search always ends.
La première idée est d’essayer des nombres. Le PGCD ne peut pas être plus grand que le plus petit des deux nombres : on part donc de là, et on descend un par un. Le premier nombre qui divise à la fois a et b est le PGCD. Comme 1 divise tous les nombres, la recherche finit toujours.
Write a function slowGcd(a, b) that returns the GCD of a and b this way.
Écris une fonction pgcdLent(a, b) qui renvoie le PGCD de a et de b de cette façon.
Step 2: Euclid’s idea
Étape 2 : l’idée d’Euclide
About 2,300 years ago, Euclid noticed that the GCD of a and b is also the GCD of b and of the remainder a % b. The numbers shrink very quickly. When the remainder reaches 0, the other number is the GCD.
Il y a environ 2300 ans, Euclide a remarqué que le PGCD de a et b est aussi le PGCD de b et du reste a % b. Les nombres rapetissent très vite. Quand le reste arrive à 0, l’autre nombre est le PGCD.
| a | b | a % b |
|---|---|---|
| 252 | 105 | 42 |
| 105 | 42 | 21 |
| 42 | 21 | 0 |
| 21 | 0 |
Each row passes b and the remainder to the next one. With variables, one row is: let r = a % b; a = b; b = r;, the swap of lesson 2 with a remainder in it.
Chaque ligne passe b et le reste à la suivante. Avec des variables, une ligne s’écrit : let r = a % b; a = b; b = r;, l’échange de la leçon 2, avec un reste dedans.
Write a function gcd(a, b) that repeats this step as long as b is not 0, then returns a.
Écris une fonction pgcd(a, b) qui répète cette étape tant que b n’est pas 0, puis renvoie a.
The race
La course
Both methods find the same GCD, but not at the same speed. This program counts how many turns each loop makes for two big numbers. Run it, then try other numbers.
Les deux méthodes trouvent le même PGCD, mais pas à la même vitesse. Ce programme compte combien de tours fait chaque boucle pour deux grands nombres. Exécute-le, puis essaie d’autres nombres.
More than twelve million turns against a handful: that is why we still use Euclid’s algorithm today, in computers, for example to simplify fractions or in the cryptography that protects online banking.
Plus de douze millions de tours contre une poignée : voilà ce qui fait qu’on utilise encore l’algorithme d’Euclide aujourd’hui, dans les ordinateurs, par exemple pour simplifier des fractions ou dans la cryptographie qui protège les banques en ligne.
Step 3: the code of the Euclid page
Étape 3 : le code de la page d’Euclide
The Euclid page also shows every division. Its function, euclidSteps(a, b), returns an object with two properties: gcd, the GCD, and steps, the array of the steps. Each step is an object { x, y, q, r } where x = q × y + r.
La page d’Euclide montre aussi chaque division. Sa fonction, euclidSteps(a, b), renvoie un objet avec deux propriétés : gcd, le PGCD, et steps, le tableau des étapes. Chaque étape est un objet { x, y, q, r } où x = q × y + r. Les noms sont en anglais, comme sur la page : gcd pour PGCD, steps pour étapes.
euclidSteps(252, 105)
→ { gcd: 21, steps: [{ x: 252, y: 105, q: 2, r: 42 },
{ x: 105, y: 42, q: 2, r: 21 },
{ x: 42, y: 21, q: 2, r: 0 }] }
Write euclidSteps(a, b). Start by putting the bigger number in x and the smaller in y: euclidSteps(105, 252) must give the same answer as euclidSteps(252, 105).
Écris euclidSteps(a, b). Commence par mettre le plus grand nombre dans x et le plus petit dans y : euclidSteps(105, 252) doit donner la même réponse que euclidSteps(252, 105).
Step 4: simplify a fraction
Étape 4 : simplifier une fraction
To simplify a fraction, divide its numerator and its denominator by their GCD: 12/18 becomes 2/3, because the GCD of 12 and 18 is 6.
Pour simplifier une fraction, on divise son numérateur et son dénominateur par leur PGCD : 12/18 devient 2/3, parce que le PGCD de 12 et 18 est 6.
Write a function simplify(n, d) that returns the simplified fraction as an array [numerator, denominator]. For example, simplify(12, 18) is [2, 3]. Copy your gcd function into the editor to use it.
Écris une fonction simplifie(n, d) qui renvoie la fraction simplifiée, dans un tableau [numérateur, dénominateur]. Par exemple, simplifie(12, 18) vaut [2, 3]. Recopie ta fonction pgcd dans l’éditeur pour t’en servir.
Well done!
Bravo!
You have written Euclid’s algorithm, the oldest algorithm still in use. Compare your code with the one on the Euclid page. Here are a few ideas to go further, in the sandbox below:
Tu as écrit l’algorithme d’Euclide, le plus vieil algorithme encore utilisé. Compare ton code avec celui de la page d’Euclide. Voici quelques idées pour aller plus loin, dans le bac à sable ci-dessous :
- Write
isPrime(n), which says whethernhas exactly two divisors. - The least common multiple:
lcm(a, b)isa * b / gcd(a, b). - Print the first 20 Fibonacci numbers: 1, 1, 2, 3, 5, 8… each one is the sum of the two before.
- Écris
estPremier(n), qui dit sina exactement deux diviseurs. - Le plus petit commun multiple :
ppcm(a, b)vauta * b / pgcd(a, b). - Affiche les 20 premiers nombres de Fibonacci : 1, 1, 2, 3, 5, 8… chacun est la somme des deux précédents.