« Dites Monsieur, comment il calculait ses logarithmes John Neper ? »

« Euh, intéressante question, je vais y réfléchir, promis ! »
lundi 29 octobre 2012
par  Alain BUSSER

La question, posée par plusieurs étudiants de BTS (donc déjà titulaires d’un Bac STL), a mené à un TP en guise de réponse, fait en Terminale (donc dans une autre classe). Un algorithme pour les logarithmes !

En effet, si on peut considérer les tables de logarithmes comme moyen de faciliter le calcul de produits, c’est que l’effort d’effectuer les produits a été fait préalablement par les concepteurs de tables. La question de savoir comment ils ont fourni cet effort se pose alors assez naturellement...

Avant Neper

Un algorithme de multiplication par tables peut être étudié dès le collège (faire la table est facile avec un tableur). Il remonterait au moins aux Babyloniens [1]. Le principe est simple : si on développe (x+y)2-(x-y)2, on trouve 4xy, donc avec une table de la fonction x2/4, on a juste une addition (x+y), une soustraction (x-y), deux lectures de tables et une soustraction à effectuer. Par exemple, pour multiplier 0,8 par 0,7, on les additionne et les soustrait respectivement, obtenant ainsi 1,5 et 0,1, dont on lit les images dans la table :

Ensuite, il suffit de soustraire 0,0025 à 0,5625 pour avoir le produit 0,56.

Au temps où les ordinateurs mettaient nettement plus de temps à effectuer des multiplications que des additions, cet algorithme permettait de rapidement effectuer des multiplications sans occuper trop de mémoire, la table des carrés des entiers allant de 0 à 20 occupant 21 emplacements mémoire, alors que la table de Pythagore au complet (pour les deux facteurs allant de 0 à 10 en occupe 121 ce qui est nettement plus.

Henry Briggs était féru d’astronomie, et avait déjà, comme la plupart de ses contemporains, l’habitude d’effectuer des multiplications à l’aide de tables trigonométriques, avec l’algorithme dit « de la prosthaphérèse ». Par exemple, voici comment on peut effectuer 0,8×0,7 avec une table de cosinus à 30 minutes près (elle aussi, gracieusement fournie en bas de l’article) :

  1. On cherche de quel angle 0,8 est le cosinus :
  2. On cherche de quel angle 0,7 est le cosinus :
  3. On additionne ces angles (37°+45°30’=82°30’), et on les soustrait (45°30’-37°=8°30’) ;
  4. On cherche enfin les cosinus de la somme et de la différence :
  5. On additionne les deux cosinus obtenus, et on divise le résultat par 2 : 0,13053+0,98902=1,11955 et 1,11955÷2=0,559775 ; ce qui permet de dire que 8×7 font environ 55,9775 : Pas mal en termes de précision !

Algorithme

La technique utilisée par John Neper pour calculer ses logarithmes consistait essentiellement à mettre côte à côte deux suites, l’une arithmétique, l’autre géométrique (de raison très proche de 1) et de les ajuster l’une à l’autre. L’algorithme de Neper, proche de celui exposé ci-dessous, permet de calculer toute une table d’un coup.

Henry Briggs, ayant passé pas mal de temps à effectuer des multiplications avec ses propres tables de trigonométrie, était à même d’apprécier l’utilité des tables de logarithmes de Neper, et fit tout ce qu’il put pour rencontrer ce dernier, avec qui il a collaboré à l’édition de la première table de logarithmes décimaux, en utilisant un algorithme permettant de calculer un seul logarithme à la fois (au besoin), et que voici :

Algorithme de Briggs

Entrée : Un réel x strictement positif

Variable : Un entier n

  • Tant que x est éloigné de 1 (à 0,001 près par exemple), faire
    • incrémenter le compteur n ;
    • remplacer x par sa racine carrée
  • Comme le logarithme népérien d’un nombre x proche de 1 est proche de x-1, on prend x-1 comme valeur approchée du logarithme ; n vaut alors le nombre de fois qu’on doit doubler x-1 pour avoir le logarithme du nombre de départ.
  • Faire n fois :
    • Multiplier le logarithme par 2

Sortie : Le nombre obtenu est le logarithme népérien de x.

Cet algorithme est donc très intéressant parce qu’il synthétise à peu près tout le programme du lycée : Test de positivité (à moins qu’on soit prêt à prendre le risque de calculer la racine carrée d’un nombre négatif), boucle à nombre prédéterminé d’itérations (la deuxième boucle, puisque n est connu) et boucle à condition de sortie (la première boucle, dont le but est essentiellement de calculer le nombre n). Par contre, cet algorithme n’est pas classique parce que, contrairement aux habitudes du lycée, on n’entre pas de valeur de x dont on veut calculer le logarithme, mais on définit algorithmiquement une fonction dont on cherche essentiellement à voir si sa représentation graphique est proche de celle du logarithme de la machine. Sur l’aspect fonctionnel des algorithmes, voir cette discussion. Pour rapidement tester l’algorithme en représentant graphiquement la fonction ainsi définie,

trois outils seront utilisés :

  1. CaRMetal avec ses possibilités graphiques (le mouvement d’un point laisse, par sa trace, une représentation graphique « en direct », ce qui permet de voir la manière dont le temps de calcul dépend de x ; et CaRMetal résiste bien aux valeurs négatives) ;
  2. Xcas parce que dans ce logiciel, on ne peut définir un algorithme que comme une fonction ! Xcas sait représenter graphiquement la fonction dès qu’elle est définie, et sa programmation peut se faire en Français, ce qui facilite le passage de l’algorithme au programme.
  3. Enfin, le choix du tableur est évident lorsqu’on définit une fonction, et sitôt qu’on a trouvé comment programmer en Basic Libre Office, le reste de l’activité est immédiat avec ses copies de cellules et ses graphiques à partir du nuage de points (sans compter la possibilité de faire des statistiques sur les données).

CaRMetal

L’algorithme se traduit assez aisément en JavaScript [2] :

Ensuite il suffit de lancer le programme (en cliquant sur le feu vert) après y avoir ajouté des instructions comme

Println(ln(2));

ou

a=ln(2);
b=Math.log(2);
Println((a-b)/b*100);

Mais comme on a défini une fonction, autant la représenter graphiquement, en ajoutant à la figure un point pilote appelé Px sur l’axe des abscisses, et un point M dont la trace est active, et dont les coordonnées sont fixées par le script :

Ensuite, pour éviter d’avoir à relancer trop souvent le script, il suffit d’automatiser son lancement avec le gestionnaire de scripts, de telle manière que chaque mouvement de Px relance le script :

Le tracé de la représentation graphique de la fonction (en rouge) est remarquablement proche de celui (en vert) de la représentation graphique du logarithme népérien :

L’énoncé du TP est téléchargeable en bas de l’article (au format pdf). On remarquera comment l’usage de LaTeX a permis d’évoquer une suite récurrente sans vraiment en parler.


Le TP dure une heure en ne comptant pas le III (seuls 2 élèves ont réussi la représentation graphique au bout de l’heure) et une heure et demie si on veut que tout le monde finisse. Il vaut donc mieux donner le I et le tableau du II en devoir maison avant le TP, et laisser les élèves passer du temps sur le III (recopier le JavaScript est très rapide) ; le II/3) prend pas mal de temps...

Les élèves ne recopient presque jamais les points-virgules, sans doute parce qu’ils ne les voient pas !

Deux élèves ayant, par mégarde, ajouté un zéro à 0.0001, on eu un logarithme plus précis ; ce qui a été intéressant à discuter en classe pendant le TP. L’erreur d’approximation sur le logarithme de 2 est environ trente fois le seuil de la première boucle.

Xcas

Avec Xcas, l’écriture de l’algorithme coïncide avec la définition d’une fonction appelée Neper :

Ensuite pour calculer une valeur approchée de ln(2) il suffit d’entrer Neper(2) et d’appuyer sur « entrée » pour voir le résultat. Mais le logarithme d’un nombre entier est alors donné sous forme exacte, alors il faut préciser que c’est à une valeur approchée qu’on s’intéresse :

Maintenant que la fonction est définie, Xcas peut la représenter graphiquement :

Par contre, vouloir calculer la dérivée est un peu exagéré...

tableur

Comme le tableur « Calc » de Libre Office ne possède pas de fonction appelée Neper, on peut définir celle-ci en Basic. Pour cela, on clique sur « Gestion des outils » et là, on choisit (parmi 4 langages de programmation !) le langage « Basic Libre Office ». Puis on traduit en Basic, avec une belle coloration syntaxique, l’algorithme de Briggs :

Après ça, on peut utiliser cette nouvelle fonction dans le tableur, en écrivant des formules telles que =Neper(2) pour calculer des logarithmes de façon non conventionnelle...

Par exemple, pour faire une table de logarithmes « à la Neper », on peut mettre le nombre 0,1 dans la cellule A2, le nombre 0,2 dans la cellule A3, sélectionner ensemble les deux cellules et copier vers le bas jusqu’à 2 par exemple, puis dans la cellule B2, écrire la formule =Neper(A2) qu’il suffit de copier vers le bas pour avoir une table de logarithmes !

Ensuite, dans la cellule C2, on peut écrire une formule comme =Ln(A2) puis la copier vers le bas pour comparer les deux logarithmes népériens ; et, en mettant en D2 la formule =(C2-D2)/D2, on peut afficher les erreurs d’approximation, qui sont assez faibles :

mais également assez fluctuantes :

Scilab

Scilab aussi sait représenter graphiquement une fonction définie algorithmiquement ; l’algorithme est plutôt court à rédiger :

Surprise (voir onglet suivant) : Même avec un nombre négatif, l’algorithme converge :

Pour représenter graphiquement la fonction il faut utiliser fplot2d (et non plot2d) :

Le résultat est presque immédiat :

Et Scilab peut exporter la figure à un format vectoriel comme eps ou pdf qui permet d’obtenir un rapport de TP très professionnel...

Prolongements

Question troublante : À quel moment exactement, a-t-on utilisé le fait que x est positif ?

Réponse : Jamais ! En fait, si x=0, la suite un+1=√(un) ne tend pas vers 1 ; dans tous les autres cas (y compris si x est négatif !) la suite converge vers 1, et donc l’algorithme converge aussi : L’algorithme de Briggs-Neper permet de calculer le logarithme de tout complexe non nul, et pas seulement des réels positifs. Vérification expérimentale avec Ruby :

Tout d’abord le calcul de ln(2) avec Briggs :

Ensuite, pour s’amuser, on remplace juste 2 par -2 :

Surprise : L’algorithme calcule un nombre qui peut être appelé logarithme de -2 ! Et d’ailleurs le module de nombres complexes de Ruby est doté d’un (autre) algorithme de calcul de logarithmes de nombres complexes :

On peut assez facilement vérifier de façon formelle que ce nombre est ln(2)+πi : En effet l’exponentielle de ce nombre est eln(2)e=2×(-1)=-2 cqfd !


Ce TP expliquant comment Briggs calculait des logarithmes à partir de racines carrées, est idéalement complété par un TP expliquant ... comment calculer des racines carrées ; l’algorithme de Heron convient...

Comment calcule-t-on les logarithmes aujourd’hui ?

Une méthode qui semble courante est de se ramener par des multiplications ou divisions successives par e, à une valeur de x située entre e-1 et e par exemple, et de remplacer sur cet intervalle, le logarithme par un développement limité ou une fraction de Padé (approximation du logarithme par un quotient de polynômes, minimisant la norme de la différence sur l’intervalle, en général la norme L). On peut considérer que l’algorithme de Briggs utilise un développement limité à l’ordre 1...

L’algorithme CORDIC, inventé pour les fonctions trigonométriques, peut s’adapter aux logarithmes. Le résultat est d’ailleurs très similaire à l’algorithme de Briggs.

Et l’exponentielle ?

Euler savait que la suite (1+x/n)n tend vers ex mais la convergence est trop lente pour que le résultat soit pratique. En développant le terme général de la suite avec la formule du binôme, Euler a découvert la fameuse série avec les factorielles, qui converge avec vitesse et précision sur un intervalle comme [-1 ;1] ; ensuite on peut se ramener à cet intervalle par multiplication ou division par e.

Et la version hyperbolique de l’algorithme CORDIC permet de calculer rapidement les sinus et cosinus hyperboliques, dont la somme est l’exponentielle.


[1Selon ce livre avec la version Python

[2D’autant qu’ici, la boucle à nombre prédéterminé d’exécutions, qui ne se rédige pas très simplement en JavaScript, a été remplacée par une boucle « tant que ».


Documents joints

tables
tables
une table de carrés et une table de cosinus pour faire des multiplications
énoncé du TP
énoncé du TP
TP d’une heure en Terminale STI2D

Commentaires

Logo de Marc JAMBON
dimanche 23 décembre 2012 à 17h46 - par  Marc JAMBON

En définitive, ce qui est proposé, c’est la méthode de Briggs et non celle de Neper, elle calcule effectivement une valeur approchée du logaritme népérien [et non décimal].
En entrée, je suppose qu’on se donne un rationnel x strictement positif plutôt qu’un réel [qui demanderait une calcul supplémentaire par une suite d’approximations], pratiquement, un nombre décimal strictement positif.

Pour rendre la méthode viable, il y aurait lieu aussi de connaitre un majorant de n qui dépend surement de x. On trouvera surement que plus x est éloigné de 1 plus n est grand.
Si l’objectif ultime est d’obtenir une table de logarithmes décimaux, il convient de disposer de ln(10) aussi précis que possible et de diviser par ce coefficient le logarithme népérien.
Pratiquement on devrait ainsi pouvoir se contenter des logarithmes népériens puis décimaux de nombres décimaux x vérifiant 1 < x ≤ 10. Selon mes calculs personnels, n = 12 pour x = 10 en vue d’avoir un nombre < 1,001. 12 est un majorant de n pour 1 < x ≤ 10.

Si on utilise une division de x par des puissances de e, encore doit-on disposer d’une méthode précise pour calculer une valeur approchée de e. Si on dispose, à cet effet, de la série exponentielle, la mise en place d’une table d’exponentielles dans un intervalle borné entourant 0 et ensuite lecture de cette table à l’envers ne serait-elle pas plus efficace ( ? ? ?).

Pour compléter, il conviendrait aussi d’avoir un majorant de l’erreur commise, la question est effectivement posée dans le TP joint, mais on n’a pas la réponse.
Il y a cinq sources d’erreur pour les logarithmes décimaux : les approximations sur les racines carrées, l’approximation qui consiste à remplacer par ln(x**(1 /2**n)) par (x**(1 /2**n)) – 1, c’est la plus facile à maitriser [avec les formules qu’on connaît aujourd’hui !], amplification des erreurs commises en multipliant n fois par 2 et très probablement arrondis décimaux au cours de ces multiplications, l’imprécision sur ln(10) et l’erreur commise en divisant par ce nombre. Je soupçonne qu’on sera très loin des 5 décimales des vielles tables de Bouvart et Ratinet [qui existent peut-être encore dans les musées ou dans des bibliothèques poussiéreuses] .

Encore une question, John Neper ayant vécu entre 1550 et 1617, de quelles tables disposait Christophe Colomb pour traverser l’Atlantique en 1492 ? De même Magellan ?

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 21 juin 2017, 14h-18h, 146 route de Grand-Coude, Saint-Joseph


Brèves

Décès de Roger Mohr

mardi 27 juin

On sait bien que Nicolas Bourbaki n’était pas le nom d’une personne mais le pseudonyme d’un groupe. L’équivalent en informatique théorique est Claude Livercy, auteur de la théorie des programmes. Roger Mohr était un des membres de Claude Livercy.

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

mardi 18 juillet 2017

Publication

759 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

275 aujourd'hui
371 hier
2063073 depuis le début
5 visiteurs actuellement connectés