Les nouvelles technologies pour l’enseignement des mathématiques
Intégration des TICE dans l’enseignement des mathématiques

MathémaTICE, première revue en ligne destinée à promouvoir les TICE à travers l’enseignement des mathématiques.

activité interdisciplinaire informatique+latin+maths+histoire
L’abaque de Neper, un artéfact quatre fois centenaire pour enseigner le binaire

En SNT, une activité sur l’abaque binaire de Neper a été menée durant toute une année scolaire de 2nde

Article mis en ligne le 3 juin 2021
dernière modification le 24 septembre 2022

par Alain Busser

Dans cet article, est décrit un artéfact (voir cet article pour une définition de ce mot) de la numération binaire de position, créé et décrit par John Neper au début du XVIIe siècle, et qui a fait l’objet, durant l’année scolaire 2020-2021, d’une activité menée en latin et en SNT, en classe de 2nde, et dont le fruit le plus succulent est constitué des vidéos de cet article. On excusera donc à ces élèves de 2nde un certain flou langagier : il a été décidé de ne pas intervenir outre mesure dans la production de ces vidéos d’élèves.

Licence Creative Commons
Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International.

John Neper, baron de Merchiston, est surtout célèbre pour avoir inventé les logarithmes :

La vie de Neper
racontée par des élèves de Seconde 4

Ce qui est moins connu, c’est qu’il a aussi inventé un procédé basé sur la numération décimale pour accélérer la multiplication : ses bâtons, abordés dans la vidéo précédente et déjà présentés dans cette revue. Et ce qui est encore moins connu, c’est que son livre rhabdologiæ a été augmenté d’une annexe, présentant un abaque permettant le calcul binaire. Cet abaque a aussi déjà été présenté dans cette revue. Mais une classe exceptionnellement riche en élèves latinistes a permis d’étudier le texte de Neper :

l’annexe de Neper, à propos de son abaque une tentative de traduction en français
Le texte original de Neper, en latin
essai de traduction française du livre de Neper

Puis des exercices sur le chapitre VIII (théorie) ont été donnés en devoir maison. Ils sont décrits en bas de cet article [1]. Ensuite les élèves ont produit les capsules vidéo du présent article.

Chapitre VIII : le binaire

Le tournage du film a été interrompu par la mise en isolement de toute la classe. Aussi les élèves ont-ils fabriqué leur propre abaque [2] pour montrer comment convertir (sur l’abaque) le nombre onze en binaire :

La numération binaire
conversion vers l’écriture binaire sur un abaque de Neper

étude de l’algorithme de conversion binaire

On peut également jouer à ce jeu pour se familiariser avec la manipulation. Il s’agit de groupements-échanges mais en version binaire. Lors de la semaine des mathématiques, la version réseau de Petri de cet algorithme a été testée par des élèves de CM1. L’algorithme de conversion binaire jouit des propriétés suivantes :

  • L’algorithme se termine : pour le prouver on choisit un variant (un entier positif qui décroît strictement à chaque itération). Par exemple la différence entre le nombre de jetons et le poids de Hamming [3] du nombre à convertir. Comme à chaque étape du calcul, on enlève deux jetons d’une case et on n’en rajoute qu’un dans la case de gauche, le variant décroît strictement. Il atteint donc la valeur 0 au bout d’un temps fini, ce qui prouve la terminaison de l’algorithme.
  • L’algorithme effectue bien une conversion binaire : la somme des produits nombre de jetons dans la case × valeur de la case est invariante au cours de l’exécution de l’algorithme. En effet à chaque étape de l’algorithme
    • on enlève 2 jetons de la case de valeur 2k, ce qui fait baisser la quantité de la valeur 2×2k = 2k+1
    • mais juste après, on rajoute un jeton dans la case de gauche, qui vaut 2k+1 d’après l’axiome 1 de Neper, et la quantité augmente donc à nouveau de 2k+1 : au final la quantité n’a pas bougé. Or
      • au début toutes les cases sont vides sauf celle de valeur 1 et la quantité invariante est alors égale au nombre à convertir.
      • à la fin aucune case ne contient plus d’un jeton (sinon l’algorithme ne serait pas terminé) et l’écriture finale est binaire : il s’agit de l’écriture binaire du nombre de jetons qui étaient initialement dans la case de valeur 1.
  • Étude de la complexité de l’algorithme : pour passer de la case de valeur 2k à la case de valeur 2k+1, le nombre de groupements-échange est de l’ordre de la moitié du nombre de jetons présents dans la case de valeur 2k. Le nombre d’étapes de l’algorithme est donc majoré par n(1/2+1/4+1/8+1/16+...)=n (nombre à convertir) : l’algorithme est de complexité linéaire.

Modélisation de l’algorithme en Python

L’algorithme est parallélisable : par exemple un élève peut très bien effectuer les groupements-échange entre les cases 8 et 16 alors qu’un autre élève continue à faire des groupements-échange entre les cases 1 et 2. Mais ici on ne le fait pas : on attend d’avoir totalement terminé entre les cases 2k et 2k+1 avant de commencer à vider la case 2k+1. Alors si on appelle a le nombre de jetons dans la case 2k et b le nombre de jetons dans la case 2k+1 (de sorte qu’initialement b est nul), la quantité a+2b est invariante (à chaque groupement-échange, b augmente d’une unité tandis que a diminue de 2 unités) et donc à la fin, 2b ou 2b+1 vaut le nombre initial de jetons dans la case 2k : l’ensemble des groupements-échange entre les cases de valeur 2k et 2k+1 se résume à une division euclidienne par 2 (le quotient est la valeur finale de b et le reste est la valeur finale de a). On obtient donc l’écriture binaire d’un entier par une succession de divisons euclidiennes par 2. Ce qu’on peut écrire

  1. def binaire(n):
  2.         s = ''
  3.         while n>0:
  4.                 s = str(n%2)+s
  5.                 n //= 2
  6.         return s

Télécharger

Chapitre IX : la multiplication

Ici l’imprévu du tournage a été la semaine des mathématiques : les jetons ont été empruntés pour des activités sur les réseaux de Petri et des pièces de monnaie ont été utilisées à la place. Les élèves ont tenu à ajouter au début la description du fonctionnement de l’abaque :

présentation et multiplications sur l’abaque
Explications sur l’abaque de Neper et multiplication binaire sur l’abaque

modélisation Python

Commençons par des utilitaires (conversion entre entier et liste de 0 et de 1) :

  1. def binaire(entier):
  2.     liste = []
  3.     while entier>0:
  4.         liste.append(entier%2)
  5.         entier //= 2
  6.     return liste
  7.  
  8. def entier(liste):
  9.     assert all(x<2 for x in liste)
  10.     return sum(liste[x]*2**x for x in range(len(liste)))

Télécharger

Ensuite, les fonctions de groupement-échange (axiome 1 de Neper) :

  1. def axiome1a(liste,i):
  2.     if liste[i]>1:
  3.         liste[i] -= 2
  4.         if len(liste)>i+1:
  5.             liste[i+1] += 1
  6.         else:
  7.             liste.append(1)
  8.  
  9. def axiome1b(liste,i):
  10.     if i>0 and liste[i]>0:
  11.         liste[i] -= 1
  12.         liste[i-1] += 2

Télécharger

permettent de simplifier l’écriture binaire d’un nombre (qu’elle soit vraiment binaire) :

  1. def simplifier(liste):
  2.     while any(x>1 for x in liste):
  3.         i = [i for i in range(len(liste)) if liste[i]>1][0]
  4.         axiome1a(liste,i)
  5.     return liste

Télécharger

La fonction ci-dessus donne les coordonnées du premier jeton posé sur l’abaque (à faire glisser jusqu’à la marge pour effectuer la multiplication). Avec les fonctions précédentes il devient aisé de simuler le glissement des jetons vers la marge :

  1. def multiplier(a,b):
  2.     x = binaire(a)
  3.     y = binaire(b)
  4.     n = len(x)+len(y)
  5.     abaque = [[0 for j in range(n)] for i in range(n)]
  6.     for i in range(len(x)):
  7.         if x[i]==1:
  8.             for j in range(len(y)):
  9.                 if y[j]==1:
  10.                     abaque[i][j] = 1
  11.     while any(1 in abaque[i] for i in range(1,len(x))):
  12.         i,j = position_jeton(abaque)
  13.         abaque[i-1][j+1] += 1
  14.         abaque[i][j] -= 1
  15.         for i in range(len(abaque)):
  16.             print(abaque[i])
  17.         print('')
  18.     return entier(simplifier(abaque[0]))

Télécharger

autre modélisation Python

On peut également modéliser l’algorithme sans faire appel à des matrices. Pour cela, on se ramène à une seule dimension (au lieu de 2 chez Neper), en regroupant les glissades de jetons par ligne. Par exemple, les lignes suivantes représentent le même nombre :

  • On lit, en haut, le nombre 13 (8+4+1) mais à la hauteur 8 donc c’est 13×8=104
  • à la ligne 4, c’est le nombre 26 (16+8+2) à multiplier par 4 : là encore c’est 26×4=104
  • à la ligne 2 on lit l’écriture binaire de 52 (32+16+4) dont le double est 104
  • et en bas on lit directement l’écriture binaire 64+32+8=104

L’algorithme de multiplication de Neper revient donc à décaler le multiplicande tant que possible et, lorsque le chiffre correspondant du multiplicateur est 1, on additionne le multiplicande décalé à la somme partielle. Plutôt que créer un pointeur sur les chiffres du multiplicateur, on propose d’utiliser l’algorithme de conversion binaire : on regarde le chiffre des unités (en effectuant un et logique avec 1) pour connaître la valeur de ce chiffre, puis on effectue la division par 2 qui amène le chiffre suivant (lequel devient alors le chiffre des unités). Les multiplications et divisions par 2 sont des décalages et on obtient alors l’algorithme suivant :

  1. def produit(a,b):
  2.     s = 0
  3.     while b:
  4.         if b&1:
  5.             s += a
  6.         b >>= 1
  7.         a <<= 1
  8.     return s

Télécharger

À la ligne 6 on décale le multiplicateur b vers la droite (division par 2) et à la ligne 7 on décale le multiplicande vers la gauche (multiplication par 2). À la ligne 4 on regarde le chiffre des unités de b (un et logique efface tous les autres chiffres) et si ce chiffre est 1, on additionne (ligne 5) le multiplicateur décalé à la somme partielle s (initialisée à 0 ligne 2) et on fait le tout (ligne 3) tant qu’il reste au moins un chiffre non nul dans l’écriture de b.

On peut traduire cet algorithme de manière plus arithmétique :

  1. def produit(a,b):
  2.     s = 0
  3.     while b>0:
  4.         print(a*b+s)
  5.         if b%2 == 1:
  6.             s += a
  7.         b = b//2
  8.         a = a+a
  9.     return s

Télécharger

On reconnaît alors un algorithme antique de multiplication. Avec cette modélisation de l’algorithme, on peut prouver ses propriétés :

  • Comme, à chaque passage dans la boucle, la variable b est divisée par 2, elle décroît strictement jusqu’à atteindre la valeur 0 en un temps fini (qu’on peut même estimer : c’est le nombre de chiffres du multiplicateur ; l’algorithme est donc de complexité logarithmique)
  • La quantité a×b+s est invariante au cours de l’exécution de l’algorithme :
    • Si b est pair, s ne bouge pas, a est doublé et b est exactement divisé par 2. a×b+s devient alors 2a×b/2+s=a×b+s et ne bouge pas.
    • Si b est impair, s devient s+a et b devient non pas b/2 mais (b-1)/2. Alors a×b+s devient 2a×(b-1)/2+s+a=a×(b-1)+s+a=a×b-a+s+a=a×b+s ne bouge pas non plus.

Comme au début, a est le multiplicande, b est le multiplicateur et s est nul, donc la quantité invariante est initialisée au produit. Or à la fin, b est devenu nul et donc la quantité invariante est devenue a×0+s=s. La valeur finale de s est le produit, et il s’agit bien d’un algorithme de multiplication.

Ces propriétés ont d’ailleurs été prouvées par why3.

Chapitre X : division euclidienne

On constate une difficulté de verbalisation : « là on voit que on peut pas ». En fait ce qu’on voit qu’on ne peut pas faire, c’est une soustraction. Ce point sera détaillé plus bas :

Divisions euclidiennes
Plusieurs divisions euclidiennes sont menées sur l’abaque de Neper

Il est probablement difficile, en voyant la vidéo, de comprendre comment effectuer la division euclidienne sur l’abaque de Neper. Mais les élèves qui ont fait la vidéo, eux, l’ont compris : l’abaque de Neper est un bon exemple d’enseignement kinesthésique, qui devrait intéresser au plus haut point les spécialistes de la praxéologie.

verbalisation de l’algorithme

Voici une animation sur les étapes importantes de la division euclidienne en binaire.

Quelle est donc la chose que « on voit que on peut pas » ? Prenons l’exemple (choisi par Neper) de la division de 250 par 13 :

Le départ de la division consiste à reproduire le motif 1101 (le nombre 13) le plus haut possible, en empruntant des jetons au dividende, par des mouvements en diagonale (qui ne changent pas leur valeur) :

Du coup les 3 jetons 1101 ne représentent plus le nombre 13 mais 16 fois plus (puisqu’ils sont en hauteur) soit 208. Et 208 est le plus grand multiple de 13 par une puissance de 2 qui entre dans 250 :

Maintenant, puisqu’on ne change pas la valeur des jetons en les déplaçant en diagonale, le problème est exactement le même que si on appliquait à ce 208 déguisé en 13, une symétrie par rapport à la diagonale principale (symétrie qui revient à glisser les jetons en diagonale, perpendiculairement à la diagonale principale) :

Mais là encore, les jetons gardent leur valeur si on les décale tous en diagonale vers le dividende :

Ainsi, la chose que « on voit que on peut pas » est une soustraction. L’algorithme utilisé par Neper pour effectuer une division euclidienne est donc juste une suite de soustractions (de produits par 13 de puissances de 2, au dividende/reste). Ce qui revient à la division connue, mais en version binaire :

  11111010 | 1101
           |-----
 -1101     | 10011
  ----     |
    10101  |
   - 1101  |
     ----  |
     10000 |
   - 1101  |
      ---- |
        11 | 

En effet comme nous sommes en binaire, chaque multiplication du diviseur par un chiffre du quotient donne, ou bien le diviseur, ou bien zéro. Et il ne reste que des soustractions à effectuer.

modélisation en Python

Traduit en Python, cet algorithme donne

  1. def division(dividende,diviseur):
  2.     if diviseur>dividende:
  3.         return 0,dividende
  4.     reste = dividende
  5.     quotient = 0
  6.     while reste>=diviseur:
  7.         copie = diviseur
  8.         p = 1
  9.         while copie<=reste:
  10.             copie *= 2
  11.             p *= 2
  12.         # un produit de trop
  13.         copie //= 2
  14.         p //= 2
  15.         reste -= copie
  16.         quotient += p
  17.         assert quotient*diviseur+reste == dividende
  18.     assert 0<=reste<dividende
  19.     return quotient,reste

Télécharger

modélisation en whyML

Et, grâce à la complicité de Jean-Christophe Filliâtre, la version whyML (pour tester sur why3) :

  1. module Division
  2.  
  3.   use int.Int
  4.   use int.ComputerDivision
  5.   use ref.Refint
  6.  
  7.   let division (a b: int) : (q: int, r: int)
  8.     requires { 0 <= a && 0 < b }
  9.     ensures  { q * b + r = a && 0 <= r < b }
  10.   =
  11.     let ref r = a in
  12.     let ref q = 0 in
  13.     while r >= b do
  14.       invariant { q * b + r = a && 0 <= r }
  15.       variant   { r }
  16.       let ref c = b in
  17.       let ref p = 1 in
  18.       while c <= r do
  19.         invariant { 0 < c <= 2*r }
  20.         invariant { c > r -> exists c'. c = 2 * c' }
  21.         invariant { c > r -> exists p'. p = 2 * p' }
  22.         invariant { p * b = c }
  23.         variant   { r - c }
  24.         c *= 2;
  25.         p *= 2
  26.       done;
  27.       c := div c 2;
  28.       p := div p 2;
  29.       r -= c;
  30.       q += p
  31.     done;
  32.     (q, r)
  33.  
  34. end

Télécharger

Why3 prouve que cet algorithme termine et effectue bien une division euclidienne.

étude de l’algorithme

  • L’algorithme se termine : à chaque étape, on enlève des jetons (après d’éventuels groupements-échanges) dans la marge de droite. Le reste de la division euclidienne diminue donc strictement à chaque étape. Or le reste est un entier positif et ne peut décroître indéfiniment, ce qui prouve que l’algorithme termine au bout d’un nombre fini d’étapes. Le reste est un variant de l’algorithme.
  • L’algorithme effectue bien une division euclidienne. Pour le prouver on utilise un invariant qui est a = b×q+r (a est le dividende, b est le diviseur, r est le nombre qui reste dans la marge et q est le quotient en cours de calcul, qui se lit verticalement dans n’importe quelle colonne non vide de l’abaque).
    • Au début q=0 et r=a, l’égalité s’écrit alors a=b×0+a et est vraie.
    • si avant une étape du calcul, on a déjà a = b×q+r, après l’étape de calcul, un chiffre binaire 2k a été ajouté à q qui devient q+2k et le produit de b par le même 2k a été soustrait à r qui devient donc r-b×2k. Le second membre de l’invariant est donc devenu b×(q+2k)+r-b×2k=bq+b×2k+r-b×2k=bq+r.
    • Par conséquent, l’invariant qui était déjà vrai au début de l’algorithme, et que l’algorithme a conservé, est resté vrai à la fin de l’algorithme : il s’agit bien d’une division euclidienne et l’algorithme est correct
  • Étude de la complexité de l’algorithme : le nombre de soustractions est majoré par le nombre de chiffres binaires du quotient, lui-même majoré par le nombre de chiffres binaires du dividende. Et pour chaque soustraction, le nombre de groupements-échange nécessaires est majoré lui aussi par le nombre de chiffres binaires du dividende : l’algorithme est de complexité log(n)² où n est le nombre de chiffres binaires du dividende.

Chapitre XI : Racine carrée entière

Pour Neper, la racine carrée d’un entier x n’est pas le nombre entier r tel que r²≤x<(r+1)² mais deux entiers : r et un reste y tel que x=r²+y et 0≤y<2x+1. Par exemple la racine carrée de 50 est formée du nombre 7 (dont le carré vaut presque 50) et du reste 1. Les élèves de 2nde ayant quelques difficultés à gérer ce reste, ont préféré extraire la racine de 49 :

extraction de racine carrée
Extraction de la racine carrée de 49 sur l’abaque binaire de Neper

Gnomons

Dans cette présentation, d’autres élèves ont compris l’importance des cases sur la diagonale, lorsqu’on calcule un carré :

En fait, le carré se constitue en ajoutant des sous-carrés, en forme de gnomons (figures hexagonales obtenues en soustrayant un parallélogramme à un autre parallélogramme). Et la case du gnomon qui touche la diagonale est une sorte de pivot.

Les gnomons de Neper

Voici une animation montrant les étapes de l’extraction d’une racine carrée sur l’abaque de Neper. L’idée de l’algorithme est de construire progressivement, bit par bit, la racine entière, c’est-à-dire le plus grand nombre entier r tel que r²≤x. Neper propose de propager le calcul vers le sud-est par vagues successives, en forme de gnomon (géométrie). Par exemple pour extraire la racine carrée de 450 (on voit que la racine est 21 et le reste, à droite, est 9) :

Ces gnomons ont des valeurs (somme des valeurs des jetons qui sont dessus), de droite à gauche :

  • le plus grand gnomon est bleu, de valeur 1+4×2+16×2=1+8+32 = 41 (on remarque que le nombre représenté en binaire sur chaque branche du gnomon est 16+4+1=21 et 21×2-1=41)
  • le second gnomon est cyan, de valeur nulle puisqu’il n’y a aucun jeton dessus. Mais ce 0 est à multiplier par 4 puisque le gnomon cyan est décalé d’une case en diagonale, par rapport à l’origine (corollaire 2 de Neper)
  • le troisième gnomon est vert et sa valeur intrinsèque est 1+4×2=9 (on remarque que le nombre représenté en binaire sur chaque branche du gnomon est 4+1=5 et 5×2-1=9). Mais le gnomon est décalé de deux cases par rapport à l’origine et sa valeur sur l’abaque est donc 9×4×4=9×16=144
  • le quatrième gnomon (jaune) est vide et donc vaut 0×64=0
  • enfin le jeton rouge est dans une case unique, que Neper appelle gnomon de tête et qui vaut 1×256=256

La valeur totale des jetons sur l’abaque est donc 256+0+144+0+41=441=21².

Voici des gnomons à découper dans le papier et à disposer sur l’abaque de Neper pour accélérer le calcul d’une racine carrée :

l’abaque, à la même échelle que les gnomons une grille donnant les gnomons vides de taille 1 à 6 et les gnomons de taille 1 à 4 les gnomons de taille 5
abaque de Neper aux mêmes dimensions que les gnomons
gnomons vides ou de taille inférieure à 5
gnomons de taille 5

Chaque gnomon est caractérisé par le nombre binaire qui est inscrit à la fois en bas (horizontalement de gauche à droite) et à droite (verticalement de haut en bas). Or

  • si le chiffre des unités est 0, tout le gnomon est vide
  • sinon ce chiffre est commun aux deux écritures binaires.

La valeur intrinsèque du gnomon est le double des valeurs des deux branches, à l’exception du chiffre des unités qui n’apparaît qu’une fois. Si le nombre binaire représenté sur chaque branche est n alors la valeur intrinsèque du gnomon est 2n-1 et sa valeur sur l’abaque est (2n-1)×4kk est le décalage diagonal du gnomon.

modélisation Python de l’algorithme

En calculant d’abord les demi-gnomons n puis les gnomons 2n-1 (voir ci-dessus) on obtient cet algorithme :

  1. def racine(reste):
  2.     if reste<1:
  3.         return 0,0
  4.     largeur = 1
  5.     poids = 1
  6.     while poids<reste:
  7.         largeur += 1
  8.         poids *= 4
  9.     radix = 0
  10.     for i in range(largeur):
  11.         demi_gnomon = 2*radix+1
  12.         gnomon = 2*demi_gnomon-1
  13.         if gnomon*poids<=reste:
  14.             reste -= gnomon*poids
  15.             radix = demi_gnomon
  16.         else:
  17.             radix *= 2
  18.         poids //= 4
  19.     return radix,reste

Télécharger

La première partie est un calcul du nombre de chiffres (largeur) binaires de la racine. En effet Neper commence par le poids fort (ordre de grandeur de la racine). Ce nombre n’est autre que le logarithme entier en base 4, du nombre dont on veut la racine carrée.

Dans la seconde partie, on boucle sur les chiffres binaires de la racine carrée. À chaque étape, on rajoute à la racine carrée en cours de calcul, un 0 ou un 1, selon que le gnomon est vide ou pas. Cela donne la moitié inférieure du gnomon, et on en déduit la valeur du gnomon entier (s’il n’est pas vide) comme on l’a vu précédemment. Le cas échéant, on soustrait cette valeur au reste, ce qui fait décroître ce dernier. Puis on divise par 4 le poids, qui aura donc la valeur 1/4 à la fin de l’algorithme.

Étude de l’algorithme

  • L’algorithme se termine : La première partie se termine au bout d’un temps fini (on peut prendre pour variant, le quotient du nombre par le poids : le poids est multiplié par 4 à chaque étape donc le quotient décroît strictement). La seconde partie se termine également au bout d’un temps fini, comme toute boucle for qui se respecte (un variant intéressant est la position du gnomon qui se propage vers le coin inférieur droit de l’abaque).
  • L’algorithme calcule bien une racine carrée entière : On a besoin de deux invariants, à savoir 4pr²+y=x et 4pr²≤x<4p(r+1)².
    • On commence par le premier invariant 4pr²+y=x :
      • Au début on a r=0 (on n’a pas encore commencé le calcul de la racine carrée) et y=x (on n’a encore rien soustrait au reste). L’égalité s’écrit donc 4p×0²+y=y soit y=y et est donc vraie.
      • Si avant une étape du calcul, on a 4pr²+y=x alors, après cette étape, p est devenu p/4, et
        • ou bien le test réussit et le gnomon (4r+1)p est soustrait à y qui devient y-(4r+1)p=y-4rp-p alors que r devient le demi-gnomon 2r+1. Le premier membre de l’égalité devient alors 4p/4(2r+1)²+y-4rp-p=p(4r²+4r+1)-4rp-p+y=4r²p+4rp+p-4rp-p+y=4r²p+y=x par hypothèse de récurrence.
        • ou bien le test échoue et y est inchangé (on ne peut pas faire la soustraction, on ne la fait pas) alors que r devient 2r. Dans ce cas, le premier membre de l’égalité devient 4p/4(2r)²+y=p×4r²+y=x. On a bien un invariant.
      • Donc à la fin (lorsque p=1/4) on a 4×1/4×r²+y=x soit r²+y=x cqfd.
    • Pour le second invariant 4pr²≤x<4p(r+1)² on n’a que la seconde moitié x<4p(r+1)² à prouver, la première moitié 4pr²≤x découlant de l’invariant précédent.
      • au début on a r=0 donc il s’agit de comparer x avec 4p(0+1)²=4p : x<4p d’après un invariant de la fin du while.
      • Si avant une étape on a x<4p(r+1)², alors après cette étape p est devenu p/4, et
        • ou bien le test réussit, et r devient 2r+1 donc le second membre devient 4p/4(2r+1+1)²=p(2r+2)²=p×4(r+1)² et donc ne change pas : l’inégalité reste vraie ;
        • ou bien le test échoue ce qui signifie que (4r+1)p>y (4r+1 est la valeur intrinsèque du gnomon) soit, d’après l’invariant précédent, (4r+1)p>x-4r²p. Comme le test a échoué r est devenu 2r et r+1 est devenu 2r+1 donc le second membre est devenu 4p/4(2r+1)²=p(4r²+4r+1)=4r²p+p(4r+1) lequel, d’après ce qui précède, est supérieur à 4r²p+x-4r²p=x cqfd.
      • L’invariant reste vrai jusqu’à la fin de l’algorithme, et à ce moment on a p=1/4 et l’invariant s’écrit r²≤x<(r+1)² : r est bien la racine carrée entière de x
  • Complexité de l’algorithme : la première partie de l’algorithme consiste à glisser un jeton vers la diagonale et peut être vue comme une opération élémentaire sur l’abaque de Neper. Dans la version Python on calcule les termes d’une suite géométrique jusqu’à ce qu’elle dépasse x et le nombre d’étapes dépend donc logarithmiquement de x. Dans la seconde partie, le nombre de passages dans la boucle est le nombre de chiffres binaires de la racine carré et dépend donc aussi logarithmiquement de x. Mais à chaque passage dans la boucle on effectue une comparaison et une soustraction qui peut nécessiter autant de groupements-échange que de chiffres binaires dans le reste. Ce nombre dépendant aussi logarithmiquement de x, la complexité de l’algorithme de Neper est donc en log(x)².

algorithme de Von Neumann

En 1945, dans un rapport devenu célèbre, Von Neumann décrit l’architecture d’un ordinateur, et il prévoit notamment un circuit spécialisé dans la calcul des racines carrées. Si on ne s’occupe pas du reste, cet algorithme s’écrit ainsi en langage C :

  1. int isqrt4(unsigned x) {
  2.      unsigned m, y, b;
  3.      m = 0x40000000;  // position premier bit
  4.      y = 0;                      // la racine
  5.      while(m != 0) {      // on boucle 16 fois.
  6.         b = y | m;           // valeur du gnomon
  7.         y = y >> 1;         // division par 2 (plus 1 ? voire)
  8.         if (x >= b) {        // plus 1 si on peut
  9.            x = x - b;         // soustraction du gnomon
  10.            y = y | m;        // plus 1 finalement
  11.         }
  12.         m = m >> 2;       // division par 4
  13.      }
  14.      return y;
  15.   }

Télécharger

L’instruction y = y>>1 signifie qu’on décale y d’un chiffre binaire vers la droite, donc qu’on le divise par 2. Mais si on tient compte du décalage du poids m, le mouvement relatif peut être vu comme un doublement. La variable m désigne la position du gnomon sur la diagonale (le poids dans l’algorithme précédent) et est donc décalé de 2 chiffres binaires à chaque étape, vers la droite, ce qui revient à une division par 4. Relativement à ce mouvement, le fait d’avoir décalé d’un seul chiffre vers la droite la variable y fait qu’elle s’éloigne du poids vers la gauche et c’est comme si elle avait doublé. On a vu précédemment que r (ici c’est y) devenait ou bien 2r (c’est fait) ou bien 2r+1 selon les cas. Si la comparaison réussit, il faut donc encore ajouter un 1 à la fin de la racine, ou plutôt remplacer le 0 final (on a déjà doublé cette variable) par un 1. C’est-à-dire positionner à 1 le dernier chiffre et cela se fait par un ou inclusif, chiffre par chiffre, avec m.

On a vu précédemment que le demi-gnomon est 2r+1 et que le gnomon est donc 2(2r+1)-1=4r+1. Ce qui ici se fait en positionnant (ou inclusif bit par bit avec m) à 1 le chiffre le plus à droite du gnomon. Lequel chiffre est deux positions plus loin (m>>2) ce qui correspond à une division par 4 [4]. L’algorithme proposé par Von Neumann en 1945 est donc exactement le même que Neper décrivait dans les années 1610.

Cet algorithme a été prouvé ici. D’après le livre Hacker’s delight, de nos jours, l’algorithme de Newton-Raphson est presque toujours utilisé pour calculer les racines carrées. Mais c’est pour des flottants et non des entiers.

Voici la version Python de l’algorithme donné en C ci-dessus :

  1. def racine(x):
  2.     if x<1:
  3.         return 0,0
  4.     largeur = 1
  5.     poids = 1
  6.     while poids<x:
  7.         largeur += 1
  8.         poids *= 4
  9.     radix = 0
  10.     while poids >0:
  11.         gnomon = radix + poids
  12.         radix //= 2
  13.         if gnomon<=x:
  14.             x -= gnomon
  15.             radix = radix + poids
  16.         poids //= 4
  17.     return radix

Télécharger

Gnomons traditionnels

On sait depuis longtemps (probablement au moins les babyloniens) que les carrés peuvent être calculés en additionnant des gnomons. Mais ce ne sont pas les mêmes gnomons que ceux de Neper :

  • les gnomons de Neper ont leur angle en haut à gauche (poids maximum) alors que les gnomons traditionnels ont leur angle en bas à droite (le plus petit gnomon étant 1).
  • la valeur d’un gnomon de Neper est donnée par le système binaire alors que celle d’un gnomon traditionnel est donnée par le système unaire.

Cependant, les gnomons traditionnels permettent de donner un autre algorithme basé sur la recherche de seuil : on calcule les carrés des entiers jusqu’à ce que le carré dépasse x ce qui donne le successeur de sa racine entière. Cet algorithme a également été prouvé avec why3. En voici la version Python :

  1. def racine(x):
  2.     a,b,c = 0,1,0
  3.     while c<=x:
  4.         a += 1
  5.         c += b
  6.         b += 2
  7.     return a-1

Télécharger

On peut poser moultes questions à partir de ce script :

  • que mettre après return (sur un script incomplet) pour que la fonction renvoie effectivement la racine carrée entière de x ?
  • Quel variant permet-il de prouver que l’algorithme se termine ?
  • Quels invariants permettent-ils de prouver que l’algorithme calcule bien la racine carrée d’un entier positif x ?
  • Étudier la complexité de l’algorithme (et la comparer avec celle de l’algorithme de Neper/Von Neumann)

Compléments

Voici des évaluations partagées sur DocEval sur l’abaque de Neper :

questions préliminaires sur les axiomes de Neper (référence à l’ancêtre du jeu d’échecs) questions sur la manipulation de l’abaque
évaluation sur la théorie de Neper
évaluation sur les calculs sur l’abaque de Neper

résultat

Pour l’évaluation sur les mouvements de l’éléphant et du porteur de flèches, la plupart des élèves ont rapidement répondu juste aux questions, probablement parce qu’ayant déjà eu deux devoirs maison (dont l’un consistant à calculer les valeurs des cases), ils ont utilisé le fait que la valeur d’une case ne dépend que de la position de la case et non du trajet effectué pour y arriver [5]. Mais plusieurs élèves, non seulement n’ont pas pensé à utiliser ce raccourci, mais n’ont même pas remarqué avant la fin de l’évaluation cette propriété (corollaire 7 de Neper) et disent avoir multiplié au lieu de diviser par 2, quand ils allaient vers la droite. Ceci peut évoquer un problème de latéralisation, mais aussi un manque de connexion entre le cours et ses applications aux évaluations. Les résultats faux étaient en général des puissances de 2, même si l’exposant est assez difficile à relier avec la position de l’éléphant. Le diagramme en bâtons des résultats montre que les erreurs sont beaucoup moins fréquentes lorsque le trajet ne va qu’« en avant » (ni vers la droite ni vers le bas pour l’éléphant) :

Pour l’évaluation sur le fonctionnement de l’abaque, les échecs sont concentrés sur les deux dernières questions :

Les erreurs sont essentiellement des confusions entre opérandes et résultat :

  • écriture du diviseur ou du quotient à la place du dividende
  • écriture de la racine carrée à la place du nombre dont on a extrait la racine.

Les élèves reconnaissent avoir lu trop superficiellement l’énoncé.

Le théorème de Zeckendorf donne une autre représentation binaire des entiers naturels. Comment utiliser l’abaque de Neper en remplaçant les puissances de 2 par des nombres de Fibonacci ? Ce problème est, à l’heure actuelle, un problème ouvert.

Conclusion

Voici une vidéo de préparation sur l’extraction de racine carrée (celle de 32) :

extraction de racine carrée - rush
Extraction (réussie) de la racine carrée entière de 32. La compréhension de l’algorithme vient de la manipulation.

La spontanéité (c’est un rush) de la vidéo montre bien le passage progressif de la manipulation (pour cerner le problème) à la verbalisation (entre membres de l’équipe, pour formaliser les découvertes et les phases de l’algorithme) puis la phase abstraction (le ton triomphal à la fin, avec 5²+7=32).

L’abaque de Neper est donc un exemple flagrant de ce que permet, pour l’apprentissage (ici, du binaire et de l’algorithmique) la manipulation d’un artéfact, mais aussi d’une occasion de découvrir la science de la déduction.