Médaille
N°1 pour apprendre & réviser du collège au lycée.
Algorithme de Briggs - Python
Fiche méthode

Introduction :

Dans cette fiche, nous allons écrire un programme Python qui va permettre de donner une approximation du logarithme népérien d’un nombre strictement positif.
Pour cela, nous allons nous servir de l’algorithme de Briggs, du nom d’un mathématicien anglais qui vécut aux XVIe et XVIIe siècles, qui se servait de la racine carrée, outil qu’il maîtrisait très bien.

Principe de l’algorithme de Briggs

Une première approximation

Donnons pour commencer l’approximation sur laquelle repose l’algorithme.

bannière à retenir

À retenir

Si xx est suffisamment proche de 11, alors nous avons :

ln(x)x1\ln{(x)}\approx x-1

Nous pouvons comprendre intuitivement cette approximation de manière graphique, en regardant la courbe représentative C\mathscr C de la fonction logarithme népérien et sa tangente T\mathcal T au point d’abscisse 11 :

Alt terminale mathématiques algorithme de Briggs Python

Nous voyons que, au voisinage de 11, C\mathscr C et T\mathcal T se « confondent ».

Nous avons appris en cours que la fonction logarithme népérien est dérivable sur ]0 ;+[]0\ ;\, +\infty[ et que, pour tout x>0x > 0 :

ln(x)=1x\ln^{\prime}(x)=\dfrac 1x

Et nous savons donc déterminer l’équation de T\mathcal T :

y=ln(1)(x1)+ln(1)Soit : y=11(x1)+ln(1)\begin{aligned} y&=\ln^{\prime}(1)(x-1)+\ln{(1)} \ \textcolor{#A9A9A9}{\text{Soit\ :\ }} y&=\dfrac 11(x-1)+\ln{(1)} \end{aligned}

Comme ln(1)=0\ln{(1)}=0, nous obtenons finalement :

T:y=x1\mathcal T:y=x-1

  • Ainsi, quand xx est assez proche de 11 et comme C\mathscr C et T\mathcal T se « confondent » au voisinage de 11, nous avons : ln(x)x1\ln{(x)}\approx x-1.

Approximation de ln(2)\ln{(2)}

Nous allons ici montrer le principe de l’algorithme de Briggs à travers un exemple : nous cherchons à donner une valeur approchée de ln(2)\ln{(2)}.

Pour utiliser l’approximation donnée plus haut, il nous faut, en partant de 22, nous rapprocher de 11 autant que possible.

  • Pour cela, nous nous servons de la racine carrée.

En effet, prenons un nombre strictement positif aa.
En calculant successivement la racine carrée de aa, puis la racine carrée du résultat, et ainsi de suite tant que c’est nécessaire, nous pouvons nous approcher autant que nous le souhaitons de 11.

Pour 22, nous souhaitons, grâce aux racines carrées successives, nous ramener à une valeur VV dont la distance à 11 est inférieure ou égale à 10210^{-2}, c’est-à-dire que nous voulons :

V1102\vert V - 1 \vert \leq 10^{-2}

Le tableau suivant donne les résultats successifs obtenus avec une calculatrice :

Étape Valeur Distance à 11
11 2\sqrt 2 1,41421…1,41421… 0,41421…0,41421…
22 2\sqrt{\sqrt 2} 1,18920…1,18920… 0,18920…0,18920…
33 2\sqrt{\sqrt{\sqrt 2}} 1,09050…1,09050… 0,09050…0,09050…
44 2\sqrt{\sqrt{\sqrt{\sqrt 2}}} 1,04427…1,04427… 0,04427…0,04427…
55 2\sqrt{\sqrt{\sqrt{\sqrt{\sqrt 2}}}} 1,02189…1,02189… 0,02189…0,02189…
66 2\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt 2}}}}} 1,01088…1,01088… 0,01088…0,01088…
77 2\sqrt{\sqrt{\sqrt {\sqrt{\sqrt{\sqrt{\sqrt 2}}}}}} 1,00542…1,00542… 0,00542…0,00542…

Nous voyons que, en 77 étapes (soit en prenant 77 fois la racine carrée du résultat précédent), nous arrivons à la précision demandée, avec une distance à 11 inférieure ou égale à 10210^{-2}.

  • Nous trouvons ainsi VV :

V=2=1,00542…\begin{aligned} V&= \sqrt{\sqrt{\sqrt {\sqrt{\sqrt{\sqrt{\sqrt 2}}}}}} \ &= 1,00542… \end{aligned}

Nous pouvons maintenant considérer que VV est suffisamment proche de 11 pour appliquer l’approximation :

ln(V)V1\ln{(V)}\approx V-1

Or, nous avons vu dans le cours la propriété suivante :

bannière propriete

Propriété

Pour tout a>0a > 0, nous avons :

ln(a)=12ln(a)\ln{(\sqrt{a})}=\dfrac 12 \ln{(a)}

Ainsi, nous avons :

ln(2)=12ln(2)ln(2)=12ln(2)=(12)2ln(2)=122ln(2)ln(2)=12ln(2)=123ln(2)et ainsi de suite\begin{aligned} \ln{(\sqrt 2)}&=\dfrac 12 \ln{(2)} \ \ln\left(\sqrt{\sqrt 2}\right) &= \dfrac 12 \ln{(\sqrt 2)} = \left(\dfrac 12\right)^2\ln{(2)} = \dfrac 1{2^2}\ln{(2)} \ \ln\left(\sqrt{\sqrt{\sqrt 2}}\right) &= \dfrac 12 \ln\left(\sqrt{\sqrt 2}\right)=\dfrac 1{2^3}\ln{(2)} \ &\footnotesize{\textcolor{#A9A9A9}{\text{et ainsi de suite}}} \end{aligned}

Il a fallu 77 étapes pour obtenir VV, nous avons donc :

ln(V)=127ln2V1\ln{(V)}=\dfrac1{2^7}\ln 2 \approx V - 1

Nous en déduisons donc une approximation de ln(2)\ln{(2)} :

ln(2)27(V1)0,69502 [avec la calculatrice]\begin{aligned} \ln{(2)}&\approx 2^7(V-1) \ &\approx 0,69502… \footnotesize{\textcolor{#A9A9A9}{\text{ [avec la calculatrice]}}} \end{aligned}

Utilisons encore notre calculatrice, cette fois en faisant appel directement à la fonction ln\ln :

ln(2)=0,69314\ln{(2)} = 0,69314…

L’approximation est relativement correcte, mais nous pouvons encore l’améliorer, cette fois en déterminant VV avec une précision inférieure ou égale à 10310^{-3} : il faut alors 1010 étapes pour obtenir V=1,00067V=1,00067…

  • Nous obtenons alors :

ln(2)210(V1)0,69338\begin{aligned} \ln{(2)}&\approx 2^{10}(V-1) \ &\approx 0,69338… \end{aligned}

Bien sûr, en réduisant à chaque fois la distance de VV à 11, nous pouvons approcher de manière de plus en plus précise la valeur de ln(2)\ln{(2)}.

Généralisation

Ce que nous avons fait pour ln(2)\ln{(2)}, nous pouvons le faire pour ln(a)\ln{(a)}, pour tout aa strictement positif.

bannière à retenir

À retenir

  • On calcule la racine carrée de aa, puis la racine carrée du résultat, et ainsi de suite jusqu’à obtenir la valeur VV proche de 11 avec la précision voulue.
  • Soit rr le nombre de racines carrées successives qu’il a fallu pour obtenir VV.
  • L’approximation de ln(a)\ln{(a)} par l’algorithme de Briggs est alors donnée par :

ln(a)2r(V1)\ln{(a)}\approx 2^r(V-1)

Algorithme Python

Nous avons maintenant compris le principe de l’algorithme. Eh bien, le gros du travail est fait ! Car le traduire en un programme Python est alors assez simple.

  • Tout d’abord, la racine carrée va être importante, nous l’avons vu ?
  • Nous importons donc la fonction sqrt\purple{\text{sqrt}} du module math\purple{\text{math}}.

 from math import sqrt\text{ from math import sqrt}
  • Puis nous définissons la fonction briggs\purple{\text{briggs}}, qui prend en paramètres :
  • a\purple{\text{a}}, le nombre dont nous voulons donner une valeur approchée du logarithme népérien ;
  • p\purple{\text{p}}, la précision souhaitée.

def briggs(a, p):\text{def briggs(a, p):}
  • Pour éviter que la programme renvoie une erreur si le a\purple{\text{a}} entré est négatif, nous commençons par vérifier que nous cherchons bien le logarithme népérien d’un nombre strictement positif.

if a > 0:\text{if a > 0:}
  • Nous souhaitons garder en mémoire la valeur initiale de a\purple{\text{a}} (pour l’affichage final). Nous créons ainsi une variable V\purple{\text{V}}, que nous initialisons avec la valeur de a\purple{\text{a}}.
  • C’est sur cette variable V\purple{\text{V}} que nous travaillerons avec les racines carrées.

V = a\text{V = a}
  • Nous l’avons expliqué dans la première partie, nous allons avoir besoin de compter le nombre de racines carrées successives auxquelles nous ferons appel.
  • Nous initialisons donc le compteur r\purple{\text{r}} à 0\purple{\text{0}}.

r = 0\text{r = 0}
  • Nous allons calculer la racine carrée de V\purple{\text{V}} tant que la distance de sa valeur à 11 est strictement supérieure à p\purple{\text{p}}.
  • Nous utilisons pour cela une boucle while\purple{\text{while}}.

while abs(V - 1) > p:\text{while abs(V - 1) > p:}
  • Nous calculons donc la racine carrée de V\purple{\text{V}} et assignons à V\purple{\text{V}} sa nouvelle valeur.
  • Et nous indiquons que nous avons calculé une racine carrée, en incrémentant r\purple{\text{r}}.

V = sqrt(V)r = r + 1\begin{aligned} &\text{V = sqrt(V)} \ &\text{r = r + 1} \end{aligned}
  • Au sortir de la boucle, V\purple{\text{V}} contiendra la valeur aussi proche de 11 que l’indiquait p\purple{\text{p}}.
    Et r\purple{\text{r}} contiendra le nombre de fois que la boucle a été parcourue, c’est-à-dire le nombre de racines carrées successives.
  • Nous utilisons donc la formule de la première partie et assignons le résultat à une varialbe l\purple{\text{l}} : il s’agit de l’approximation recherchée.

l = 2 (V - 1)\text{l = 2$\ast\ast$\,r $\ast$ (V - 1)}
  • Nous demandons enfin au programme d’afficher le résultat l\purple{\text{l}}, en rappelant le nombre a\purple{\text{a}} entré en paramètre.

print(ln({}){}.format(a, l))\text{print($^{\backprime\backprime}$ln($\lbrace\rbrace$)$\approx\lbrace\rbrace^{\prime\prime}$.format(a, l))}
  • Nous n’oublions pas de prévoir le cas où a0\purple{\text{a}} \leq 0.
  • Nous demandons alors au programme de répondre simplement que ln\ln n’est pas définie en a\purple{\text{a}}.

else:print(La fonction logarithme neˊpeˊrien n’est pas deˊfinie en, a)\begin{aligned} &\text{else:} \ &\qquad\text{print($^{\backprime\backprime}$La fonction logarithme népérien n'est pas définie en$^{\prime\prime}$, a)} \end{aligned}
bannière à retenir

À retenir

Le programme est terminé :

1from math import sqrt23def briggs(a, p):4if a > 0:5V = a6r = 07¨C11C¨C12Cwhile abs(V - 1) > p:8¨C13C¨C14C¨C15C¨C16CV = sqrt(V)9¨C17C¨C18C¨C19C¨C20Cr = r + 110¨C21C¨C22C¨C23Cl = 2 (V - 1)11¨C24C¨C25C¨C26Cprint(ln({}){}.format(a, l))12¨C27C¨C28Celse:13¨C29C¨C30C¨C31C print(La fonction logarithme neˊpeˊrien¨C32C¨C33C¨C34C¨C35Cn’est pas deˊfinie en, a)\begin{aligned} \textcolor{#A9A9A9}{\text{1}}&\quad\text{from math import sqrt} \ \textcolor{#A9A9A9}{\text{2}}& \ \textcolor{#A9A9A9}{\text{3}}&\quad\text{def briggs(a, p):} \ \textcolor{#A9A9A9}{\text{4}}&\quad\qquad\text{if a > 0:} \ \textcolor{#A9A9A9}{\text{5}}&\quad\qquad\qquad\text{V = a} \ \textcolor{#A9A9A9}{\text{6}}&\quad\qquad\qquad\text{r = 0} \ \textcolor{#A9A9A9}{\text{7}}&\quad\qquad\qquad\text{while abs(V - 1) > p:} \ \textcolor{#A9A9A9}{\text{8}}&\quad\qquad\qquad\qquad\text{V = sqrt(V)} \ \textcolor{#A9A9A9}{\text{9}}&\quad\qquad\qquad\qquad\text{r = r + 1} \ \textcolor{#A9A9A9}{\text{10}}&\quad\qquad\qquad\text{l = 2$\ast\ast\,$r $\ast$ (V - 1)} \ \textcolor{#A9A9A9}{\text{11}}&\quad\qquad\qquad\text{print($^{\backprime\backprime}$ln($\lbrace\rbrace$)$\approx\lbrace\rbrace^{\prime\prime}$.format(a, l))} \ \textcolor{#A9A9A9}{\text{12}}&\quad\qquad \text{else:} \ \textcolor{#A9A9A9}{\text{13}}&\quad\qquad\qquad\text{ print($^{\backprime\backprime}$La fonction logarithme népérien} \ &\quad\qquad\qquad\quad\text{n'est pas définie en$^{\prime\prime}$, a)} \end{aligned}
bannière exemple

Exemple

Vous pouvez maintenant approcher, par exemple, la valeur de ln(2)\ln{(2)} avec une précision de 10510^{-5}, en saisissant la commande :

briggs(2, 0.00001) ou briggs(2, 10(-5))\purple{\text{briggs(2, 0.00001)}} \textcolor{#A9A9A9}{\text{ ou }}\purple{\text{briggs(2, 10$\ast\ast\,$(-5))}}

  • Normalement, vous aurez en retour :

ln(2)0.6931490133574698\purple{\text{ln(2)$\approx$0.6931490133574698}}

Résultat à comparer avec celui que donne la fonction ln\ln de votre calculatrice.