Le mot algorithme provient de la version latinisée

du nom du mathématicien persan Al-Khwarizmi1.

Cependant, les mathématiciens avaient développé
et mis en œuvre des algorithmes bien avant sa naissance.

Al-Khwarizmi
783-850
Algorithmes au cours de l’histoire
Dans l’article Extraction d’une racine dans Et quand deux nombres, s’étant multipliés
l’un l’autre, produisent un certain nombre,
Vol. 14 • été – automne 2019

un carré2, Bernard Hodgson nous a déjà pré-

André Ross le produit est appelé plan, et les nombres
senté un algorithme connu mille ans avant
Professeur retraité
Pythagore et utilisé par les Mésopotamiens qui se sont multipliés l’un l’autre, ses côtés.
de l’Antiquité pour extraire une racine car- (Livres VII, définition 17,)
rée. En fait, dès que l’on cherche à résoudre La procédure pour déterminer le pgcd de
systématiquement une famille de problèmes, deux nombres, telle qu’illustrée ci-dessous,
on est déjà à la recherche d’un algorithme. consiste d’un point de vue géométrique
Algorithme d’Euclide à déterminer la longueur du côté du plus
grand carré à l’aide duquel on peut paver
Un algorithme que le lecteur a probablement entièrement le rectangle dont les longueurs
déjà utilisé est appelé l’algorithme d’Euclide. des côtés sont les nombres dont on cherche
On le retrouve dans le Livre VII des Éléments le pgcd.
2 d’Euclide, qui vécut à Alexandrie environ un
millénaire avant Al-Khwarizmi. Cet algorithme En procédant numériquement, par divisions
permet de trouver le plus grand commun successives de la longueur par la largeur, puis
15 15
diviseur, ou pgcd, de deux nombres. de la largeur par le reste, et ainsi de suite
jusqu’à un reste nul, on obtient
Dans la tradition euclidienne, un nombre 15
entier est une longueur et un produit d’en- 24 = 1 × 1524+ 9
tiers est un rectangle, comme l’indique la 15 = 1 × 9 + 6 9
définition suivante tirée de la traduction de 9 = 1 ×6 + 3
15
Bernard Vitrac des Éléments d’Euclide :15 15 6 =152 × 3 + 0 15
Le pgcd étant le dernier reste non nul de ce
1. Le mot algèbre vient de Al-jabr wa‘l muqabala,
24
processus,153 est donc le plus
15 grand commun
15
titre d’un livre d’Al-Khwarizmi. Cet ouvrage est
le texte fondateur de l’algèbre. diviseur de 24 et 15. On écrit pgcd(15, 24) = 3.
6
DossierHistoire

9 9 9 9
2. Voir Accromath, volume 1, automne-été 2006.
3
15 6 9 6 9
15 15 15 15 15 15

15 15 15
24 15 24

9 6 6
9 9 9 9
3 3
15 6 9 6 9 3 3 9
15 15 15 15
Dans le rectangle de côtés 24 et 15, on inscrit maintenant deux carrés de côté 3.
peut inscrire un15 carré de côté
15 15. Il reste un C’est le plus grand carré à l’aide duquel on
15 24
rectangle de côtés 9 et 15 dans lequel on peut paver le rectangle initial. 3 est donc
peut9 inscrire un
9 carré
6 de côté
9
9.6 Il reste un9 le pgcd de 24 et 15. Lorsque le plus grand
3
rectangle de côtés3 9 et 6, à l’intérieur duquel carré permettant de paver le rectangle est
6 9 6 9 3 3 9
on peut 15inscrire un carré
15 de côté 6, il reste unitaire, les nombres sont premiers entre eux.
un rectangle de cotés 6 et 3 dans lequel on
15 24
6
9
 Algorithmes au cours de l’histoire | André Ross • Professeur retraité

Il est à noter qu’en utilisant l’algorithme

d’Euclide, on peut déterminer le pgcd de Diophante d’Alexandrie
deux nombres sans connaître leur factorisa- On ignore tout de la vie du mathématicien grec Diophante,
tion en nombres premiers. La factorisation dont on ne connaît que les écrits. On pense qu’il vivait vers le
des nombres 15 et 24 est simple à obtenir, 3e siècle de notre ère, sans pouvoir apporter plus de précisions. Son
15 = 3 × 5 et 24 = 3 ×23, ouvrage le plus célèbre est un traité de 13 livres, les Arithmétiques.
Six volumes de cet ouvrage, rédigés en grec, ont été retrouvés
d’où on peut conclure immédiatement que en Italie au 15e siècle par Regiomontanus (Johann Müller (1436-
pgcd(15, 24) = 3. Cependant, pour de très 1476)). Quatre autres livres, traduits en arabe, ont été découverts
grands nombres, il est plus simple et net- en Iran en 1968. Les experts ne s’entendent pas à leur sujet :
tement plus rapide d’appliquer l’algorithme s’agit-il de la traduction du texte original de Diophante, ou plutôt
d’Euclide, même à l’aide d’un ordinateur. d’un commentaire sur les Arithmétiques, peut-être écrit par Hypathie
Algorithme d’Euclide et (env. 355-415)?
équations diophantiennes Les Arithmétiques sont une collection de 189 problèmes accom-
Rappelons qu’une équation diophantienne pagnés de leur solution conduisant à des équations dont les
est une équation polynomiale à une ou solutions sont entières ou fractionnaires.
plusieurs inconnues dont les solutions sont

Vol. 14 • été – automne 2019

cherchées parmi les nombres entiers, les
Claude-Gaspard Bachet
coefficients étant eux-mêmes des entiers.
On a recours à l’algorithme d’Euclide pour
de Méziriac (1581-1638)
résoudre certaines équations diophantiennes Claude-Gaspard Bachet de Méziriac est
de la forme un mathématicien, poète et traducteur
ax + by = c. français. Le théorème qui porte son nom
a été présenté pour la première fois dans
À quelles conditions une telle équation
la deuxième édition de son ouvrage « Pro-
admet-elle une solution entière ?
blèmes plaisans et délectables qui se font
En ayant recours à la géométrie analytique par les nombres », parue en 1624.
moderne, on peut visualiser le problème comme
suit. L’ensemble des solutions de l’équation
ax + by = c est représenté par une droite. Si Théorème de Bézout 3
aucun point de la droite n’a de coordon-
Deux entiers a et b sont premiers entre eux Lemme
nées entières, l’équation n’a aucune solution.
si et seulement s’il existe deux entiers x et y d’Euclide
Mais, si la droite passe par
Aucu tels que Si un nombre pre-
ne so au moins un point de coor-
lutio
n ax + by = 1. mier p divise le
Infi
données entières, elle a alors produit de deux
nité
de une infinité de solutions À propos de ces théorèmes, si la constante, d nombres entiers b
solu et c, alors p divise b
tion
s puisque a, b et c sont des ou 1 selon le cas, n’est pas le pgcd des coeffi-
ou c.
entiers. cients, on ne peut rien conclure. Par ailleurs, (Éléments,
pour déterminer une première solution (x0; y0) proposition VII.30)
Deux théorèmes apportent des réponses
d’une équation de la forme
pour certaines de ces équations. Lemme
ax + by = pgcd(a, b),
de Gauss
Théorème de Bachet-Bézout on utilise l’algorithme d’Euclide et à l’aide du Si un nombre entier
lemme de Gauss, on généralise celle-ci en a divise le produit
Soit a et b deux entiers. Si d est le pgcd de a montrant que de deux autres
et b, alors il existe des entiers x et y tels que b a nombres entiers b
ax + by = d = pgcd(a, b). a ⎛ x 0 − k ⎞ + b ⎛ y 0 + k ⎞ = d, et c, et si a est pre-
⎝ d ⎠ ⎝ d⎠ mier avec b, alors a
divise c.
Le second théorème porte sur le cas où les où k est un nombre entier.
deux entiers a et b ont 1 comme seul facteur
commun. Étienne Bézout (1730-1783) Degré 3
Le mathématicien français Étienne Bézout
est passé à la postérité pour le théorème
de Bachet-Bézout en arithmétique. Il est
Degré 2
le premier à donner une démonstration
correcte du théorème suivant selon lequel Degré 4
deux courbes algébriques, respectivement
de degré m et n, se rencontrent en général
en mn points, en comptant les multiplicités. Degré 2
 DossierHistoire

Résolution à l’aide de l’algorithme d’Euclide

Considérons l’équation Cela donne :
510x + 294y = 6. 18
Cette équation admet-elle des solutions ? En appliquant 6 = 60 – 3×(78 – 1×60) = 4×60 – 3×78
l’algorithme d’Euclide, on obtient que : 60
On isole les restes
510 = 1×294 + 216
6 = 4×(216 – 2×78) – 3×78 = 4×216 – 11×78
216 = 510 – 1×294
294 = 1×216 + 78 78
78 = 294 – 1×216
216 = 2×78 + 60 ⇒ 60 = 216 – 2×78 6 = 4×216 – 11×(294 – 1×216) = 15×216 – 11×294
78 = 1×60 + 18 18 = 78 – 1×60 216
60 = 3×18 + 6 6 = 60 – 3×18
18 = 3×6 + 0 6 = 15×(510 – 1×294) – 11×294 = 15×510 – 26×294

Dans la colonne de gauche, le dernier reste non nul Par conséquent, le couple (15; –26) est une solution
est 6, on a donc pgcd(294, 510) = 6. Par conséquent, le de l’équation 510x + 294y = 6. L’ensemble des solu-
Vol. 14 • été – automne 2019

théorème de Bachet-Bézout nous garantit que l’équa- tions entières est formé de tous les couples de la forme
tion admet une solution (x0; y0). On détermine celle-ci (15 – 49k; –26 + 85k), où k est un entier.
en isolant les restes, ce qui est fait dans la colonne de
droite. On substitue ensuite en « remontant la chaîne »
de calculs afin d’exprimer 6 en termes de 294 et de 510.

1 23 Multiplication égyptienne Dans ce système, pour multiplier un nombre

2 46 Dans tous les systèmes de numération, on a par 2, il suffit de doubler le nombre de sym-
4 92 eu recours à des algorithmes pour effectuer boles et d’effectuer les regroupements en
8 184 des opérations. remplaçant tout groupe de 10 symboles
16 368 identiques par le symbole supérieur. En
4 32 Ainsi, pour multiplier 19 par 23, le scribe
utilisant cette écriture des nombres, la
égyptien associe le plus grand des deux
multiplication que nous venons d’effectuer
1 23 nombres à l’unité et double ces nombres4.
s’écrit de la façon ci-bas.
2 46 Il arrête lorsque le nombre de la colonne de
4 92 gauche devient plus grand que le multipli-
8 184 cateur.
16 368 Puisque 19 = 16 + 2 + 1, il additionne les
19 437 nombres de la colonne de droite sur les lignes
non biffées, ce qui donne :
NUMÉRATION HIÉROGLYPHIQUE
Valeur des symboles 19×23 = 23 + 46 + 368 = 437.
Le bâton représente l’unité. On qualifie le système de numération
L’anse de panier, la dizaine. égyptien de système additif de base dix. Il
Le rouleau de papyrus, est additif car c’est par la répétition des On arrête lorsqu’en doublant dans la
la centaine. symboles que l’on écrit un nombre, et de base colonne de gauche, on obtient un nombre
La fleur de lotus, le millier. dix, car un nouveau symbole est utilisé pour plus grand que le multiplicateur (en dou-
Le doigt désignant les chaque puissance de dix. blant les symboles du dernier nombre de
étoiles, dix mille. la colonne de gauche, on obtiendrait deux
Le têtard, cent mille. 4. Il est intéressant de noter que la méthode symboles suivis de plusieurs symboles ,
Le dieu agenouillé égyptienne peut être vue en termes
soutenant le monde, modernes comme revenant à écrire le mul- ce qui est plus grand que le multiplicateur).
un million. tiplicateur en base deux (même si leur sys- Le scribe repère alors dans la colonne
tème de numération n’était pas un système
positionnel comme le nôtre). de gauche les nombres qui additionnés
donnent le multiplicateur, soit
+ + =
 Algorithmes au cours de l’histoire | André Ross • Professeur retraité

Il suffit d’additionner les résultats des lignes Le dividende peut alors s’exprimer comme
dont la somme donne le multiplicateur, ce la somme de certains des nombres de la
qui donne : colonne de gauche plus possiblement un
reste plus petit que le diviseur.
Le scribe fait la somme des nombres des deux
dernières lignes de la colonne de gauche, ce
qui donne un nombre plus petit que le divi-
dende. En effet, elle ne contient qu’un seul
symbole alors que le dividende en a deux.
(En langage moderne, le chiffre des centaines
En écriture moderne, le scribe exprime le Comparaison
est trop petit.)
multiplicateur comme somme de puissances Dividende Somme
de 2, soit : De plus, il peut facilement constater qu’en
additionnant à ce résultat le nombre de la
19 = 16 + 2 + 1.
troisième ligne à partir du bas, il va obtenir
En doublant la valeur du multiplicande et deux symboles suivis de deux symboles

Vol. 14 • été – automne 2019

en retenant, les valeurs correspondant aux . La somme serait donc plus grande que
termes de la décomposition du multiplica- le dividende qui est formé de deux symboles
teur en somme de puissances de 2, il obtient : suivi d’un seul symbole . Cette somme
23×19 = 23×(16 + 2 + 1) serait plus grande que le dividende, ce qui
= 368 + 46 + 23 signifie que le nombre de la troisième ligne
= 437. à partir du bas ne fait pas partie du dévelop-
pement du dividende en somme de multiples
Division égyptienne
du diviseur. Il faut biffer cette ligne dans le
Pour illustrer comment s’effectue une division, tableau. Comparaison
considérons l’opération Dividende Somme
En ajoutant plutôt le nombre de la quatrième
÷ ligne à partir du bas et en comparant le
résultat au dividende, il constate que cette 5
Le scribe associe le diviseur à l’unité et il somme est plus petite que le dividende (elle
double successivement jusqu’à obtenir le ne contient pas le symbole alors que le
plus grand multiple du diviseur inférieur au dividende en a un et le diviseur est plus petit
nombre à diviser. que .)
Il ajoute alors le nombre de la ligne du haut.
En comparant le dividende et la somme
obtenue, le scribe peut facilement constater
que le reste est 3.
En effectuant la somme des nombres conser-
vés dans la colonne de droite, le scribe déter-
mine le quotient. Il a donc obtenu :
219 = 27 × 8 + 3. Dividende Somme
Dans ce tableau, le scribe détecte aisément
De nos jours, on écrirait le quotient
qu’en doublant le nombre de la colonne de
3
gauche il obtiendrait un nombre plus grand 27 ou 27,375.
8 Le reste est ce qui manque
que le dividende. En effet, il obtiendrait alors pour avoir l’égalité, soit
deux symboles suivis de deux symboles
(lecture de droite à gauche) alors que le divi-
dende est formé de deux symboles suivi
d’un seul symbole .
 DossierHistoire

Pour représenter une fraction, le scribe En soustrayant de 46 le carré de 6, on obtient

égyptien inscrivait l’hiéroglyphe au- 10 et on abaisse les deux chiffres suivant du
dessus d’un nombre. Ainsi, pour représenter nombre à extraire.
la fraction 1/12, le scribe doit écrire .
Cette façon de faire a un inconvénient : le 463 856
Le symbole – 36
numérateur des fractions est toujours l’unité 10 3 8
désigne une addition
alors que indique (sauf pour 2/3, pour lequel on disposait
une soustraction. d’un hiéroglyphe particulier). On dispose dans le plateau les réglettes du
Pour indiquer 3/8, le scribe devait donc double du premier chiffre du résultat (ici les
considérer que 3/8 = 1/4 + 1/8 et écrire : réglettes 1 et 2 pour 12) suivies de la réglette

1 1 2 1 121
2 0 20 4 0 4 244
Réglettes de Napier 3 0 30 6 0 9 369
et extraction de racines 4 0 40 8 1 6
Vol. 14 • été – automne 2019

496
La multiplication et la division en numération 5 0 51 0 2 5 625
égyptienne illustrent le fait qu’un algorithme 6 0 61 2 3 6 756
dépend du système de numération utilisé. Il
7 0 71 4 4 9 889
peut aussi dépendre de l’instrument de calcul
utilisé. Napier a développé un algorithme 8 0 8 1 6 6 4 1024
pour extraire une racine carrée à l’aide de ses 9 0 9 1 8 8 1 11 6 1
réglettes5.
L’algorithme de Napier repose sur jaune et on repère le nombre qui précède
1 1
la méthode traditionnelle « à la immédiatement 1 038 dans ceux représentés
2 0 4 main » pour extraire une racine par les lignes du plateau. Sur la huitième
3 0 9 carrée6. Il considère une réglette ligne, on lit 1 024,
6 supplémentaire (en jaune dans les
4 1 6 Le deuxième chiffre de la racine carrée est
5 2 5
illustrations) représentant les car- donc 8.
rés des nombres de 1 à 9. L’algo- 463 856 = 68....
6 3 6 Plus grand carré
inférieur à 47 rithme s’applique à un nombre
7 4 9 s’écrivant avec un nombre pair de On soustrait 1 024 de 1 038, ce qui donne
8 6 4 chiffres, que l’on divise en tranches 14 et on abaisse la tranche des deux chiffres
9 8 1 de deux chiffres (si ce n’est pas le suivants du nombre à extraire, ce qui donne
cas, on ajoute un 0 à la gauche du 1 456.
nombre). Effectuons l’extraction de On double le second chiffre de la racine,
la racine carrée du nombre 463 856. 2 × 8 = 16 que l’on ajoute au nombre 12
Dans ce nombre, la première tranche de deux déjà formé en le multipliant par 10, soit
chiffres est 46. Le plus grand chiffre dont le 12 × 10 + 16 =136.
carré est inférieur à 46 est 6. C’est le premier On dispose dans le plateau les réglettes du
chiffre du résultat : nombre 136, suivis de la réglette jaune et on
463 856 = 6.... 1 3 6 1
1 1361
2 0 20 6 1 2 0 4
5. Les algorithmes pour la multiplication et la 2724
division à l’aide de réglettes ont été présen- 3 0 30 9 1 8 0 9
tés dans l’article «John Napier», Accromath, 4089
Vol. 14, hiver-printemps 2019. 4 0 41 2 2 4 1 6 5456
6. L’algorithme traditionnel pour la racine
carrée fait l’objet du problème « Racines 5 0 51 5 3 0 2 5 6825
cristallines » d’Accromath (vol. 11, été- 6 0 1 3 3
6 8 6 6 8196
automne 2016, p. 32), en lien avec le texte 0
« Glanures mathématico-littéraires (II) » de 7 7 2 1 4 2 4 9 9569
Bernard R. Hodgson.
8 0 8 2 4 4 8 6 4 10944
9 0 9 2 7 5 4 8 1 12321
 Algorithmes au cours de l’histoire | André Ross • Professeur retraité

repère le nombre qui précède immédiate- Pour y voir plus clair

ment 1 456. Sur la première ligne, on a 1 361. On cherche à exprimer le nombre dont on
Le troisième chiffre de la racine est donc 1, veut extraire la racine carrée sous la forme
463 856 = 681.... 463 856 = (a × 102 + b × 10 + c)2 + R,
En soustrayant, 1 361 de 1 456, on obtient car il est clair que la partie entière de cette
95. C’est la dernière tranche de deux chiffres racine carrée s’écrit avec trois chiffres.
du nombre dont on veut extraire la racine, on À chaque étape du calcul, on exprime le
ajoute une virgule décimale et on abaisse 00 nombre comme somme d’un carré parfait et
pour obtenir 9 500. d’un terme résiduel, allant chercher un des
On double le troisième chiffre de la racine, trois chiffres a, b et c à la fois.
2 × 1 = 2 que l’on ajoute au nombre déjà À la première étape, on a donc
formé que l’on multiplie par 10, soit 463 856 = 62×1002 + 103 856
136 × 10 + 2 =1 362. On dispose dans le = (6×102)2 + 103 856.
plateau les

Vol. 14 • été – automne 2019

À l’issue de la seconde étape, on obtient
1 1 3 6 2 1 réglettes du
nombre 1 362, 463 856 = 62×1002 + 103 856
2 0 20 6 1 2 0 4 0 4
suivis de la = (6×102 + 8×10)2 +1 456.
3 0 30 9 1 8 0 6 0 9
réglette jaune. Et à l’issue de la troisième étape, on obtient
4 0 41 2 2 4 0 8 1 6
On remarque enfin
5 0 51 5 3 0 1 0 2 5 que le nombre 463 856 = 62×1002 + 103 856
6 0 61 8 3 6 1 2 3 6 sur la ligne 1 = (6 × 102 + 8 × 10 + 1)2 + 95.
0 72 1 4 2 1 4 4 9 est plus grand
7 La partie entière de la racine carrée de
0 82 4 4 8 1 6 6 4 que 9500. On
8 463 856 est donc 681. Pour trouver la partie
ajoute un 0
9 0 92 7 5 4 1 8 8 1 décimale de cette racine, il s’agit maintenant
après la virgule
de poursuivre les calculs sur la partie résiduelle
décimale,
R = 95. 7
463 856 = 681,0....
Conclusion
et on abaisse à nouveau 00, ce qui donne
Le vocable algorithme est devenu d’usage
950 000. On intercale la réglette de 0 avant
courant avec l’avènement des ordinateurs.
la réglette jaune.
Cependant, des algorithmes ont été développés
On repère le nombre qui précède immédia- très tôt dans l’histoire. Dès que les premiers
tement 950 000, c’est 817 236 sur la ligne 6. systèmes de numération sont apparus,
Le deuxième chiffre après la virgule décimale on a développé des algorithmes pour effec-
est donc 6. Ce qui donne tuer les opérations usuelles : addition,
463 856 = 681 ,06.... soustraction, multiplication, division. En
cherchant à résoudre des problèmes plus
On poursuit ainsi en abaissant 00 à chaque élaborés comme l’extraction de racines ou la
étape jusqu’à ce que l’on obtienne la préci- recherche du pgcd de deux nombres entiers,
sion cherchée. il a fallu développer d’autres algorithmes,
1 3 6 2 0 1
plus poussés et parfois étonnants.
1 136201
2 0 20 6 1 2 0 4 0 0 0 4 272404
3 0 30 9 1 8 0 6 0 0 0 9 408609
4 0 41 2 2 4 0 8 0 0 1 6 544816
5 0 51 5 3 0 1 0 0 0 2 5 681025
6 0 61 8 3 6 1 2 0 0 3 6 817236
7 0 72 1 4 2 1 4 0 0 4 9 953449

8 0 82 4 4 8 1 6 0 0 6 4 1089664

9 0 92 7 5 4 1 8 0 0 8 1 1225881