Revenir
Revenir

Algorithme et programmation

La fonction logarithme népérien est définie en classe de terminale comme la fonction réciproque de la...

Sommaire

Activité CAPYTALE : algorithmes de calcul du logarithmeIntroduction
Premier algorithme de BriggsLogarithme décimalPremier algorithme de BriggsUn algorithme historique
Second algorithme de BriggsÉtude d'une suite convergente vers ln(a)Implémentation de l'algorithme
Algorithme CORDIC

Second algorithme de Briggs

Étude d'une suite convergente vers ln(a)

Le second algorithme – qui porte parfois lui aussi le nom de Briggs – permet d’approcher le logarithme népérien d’un réel strictement positif.
Soit 
aaa
un réel strictement positif. Pour approcher
ln⁡(a)\ln(a)ln(a)
, on utilise la suite 
(un)(u_n)(un​)
définie par 
u0=au_0=au0​=a
et, pour tout entier naturel
nnn
,
un+1=unu_{n+1}=\sqrt{u_n}un+1​=un​​
. 
On a alors 
lim⁡n→+∞2n×(un−1)=ln⁡(a)\displaystyle\lim_{n\to + \infty}2^n\times (u_n-1)=\ln(a)n→+∞lim​2n×(un​−1)=ln(a)
.
L'exercice ci-dessous propose une démonstration de ce résultat.
Exercice
Soit
a>0a>0a>0
. On considère la suite
(un)(u_n)(un​)
 définie par

Algorithme CORDIC

L’algorithme CORDIC (Coordinate Rotation Digital Computing) est un algorithme inventé en 1959 et utilisé dans les calculatrices. Cet algorithme est adapté pour calculer les valeurs des fonctions trigonométriques. Pour celui-ci, certaines valeurs particulières du logarithme sont stockées dans la mémoire de la machine : il s’agit des valeurs approchés de
ln⁡(10)\ln(10)ln(10)
,
ln⁡(2)\ln(2)ln(2)
,
ln⁡(1,1)\ln(1,1)ln(1,1)
,
ln⁡(1,01)\ln(1,01)ln(1,01)
,
ln⁡(1,001)\ln(1,001)ln(1,001)
,
ln⁡(1,0001)\ln(1,0001)ln(1,0001)
… 
Ces dernières sont toutes de la forme
ln⁡(1+10−k)\ln(1+10^{-k})ln(1+10−k)
, où 
kkk
est un entier naturel.
On prend un réel
xxx
 entre 1 et 10.
    • Puisque la suite 
(2n)(2^n)(2n)
tend vers

Activité CAPYTALE : algorithmes de calcul du logarithme

Introduction

La fonction logarithme népérien est définie en classe de terminale comme la fonction réciproque de la fonction exponentielle. Considérons un réel strictement positif
aaa
.
ln⁡(a)\ln(a)ln(a)
 est alors l’unique solution de l’équation
ex=a\text e^x=aex=a
sur
R\mathbb{R}R
. 
Pourtant, historiquement, c’est bien le logarithme qui apparaît le premier.
C’est ainsi qu’en 1624, le mathématicien Henry Briggs publie dans l'ouvrageArithmetica logarithmicaune table de logarithme avec une précision de 14 décimales, et le tout sans calculatrice, bien entendu. L’algorithme utilisé par Briggs (et par Neper) n’utilise que les quatre opérations de base (addition, soustraction, multiplication et division), ainsi que l’extraction d'une racine carrée. Cette extraction emploie elle-même l’algorithme de Héron, un algorithme très efficace pour ce calcul.

Premier algorithme de Briggs

Logarithme décimal

Pour tout réel strictement positif
aaa
, on appelle logarithme en base
101010
de 
aaa
le réel noté 
log⁡(a)\log(a)log(a)
et défini par
log⁡(a)=ln⁡(a)ln⁡(10)\log(a)=\dfrac{\ln(a)}{\ln(10)}log(a)=ln(10)ln(a)​
.
Ainsi, si l’on connaît une méthode pour calculer le logarithme népérien d’un réel strictement positif, il est possible d’en déduire son logarithme décimal, et inversement – on a en effet
ln⁡(a)=log⁡(a)log⁡(e)\ln(a)=\dfrac{\log(a)}{\log(e)}ln(a)=log(e)log(a)​
.
Exercice
1.Montrer que le logarithme décimal possède des propriétés de calcul similaires à celles du logarithme népérien, à savoir que, pour tous réels strictement positifs 
aaa
et 
bbb
et pour tout entier relatif
nnn
, on a
log⁡(ab)=log⁡(a)+log⁡(b)\log(ab)=\log(a)+\log(b)log(ab)=log(a)+log(b)
,
log⁡(a)=12log⁡(a)\log(\sqrt{a})=\dfrac{1}{2}\log(a)log(a​)=21​log(a)
 et
log⁡(an)=n×log⁡(a)\log(a^n)=n \times \log(a)log(an)=n×log(a)
.
2.Exprimer 
log⁡(ab)\log(\sqrt{ab})log(ab​)
 en fonction de
log⁡(a)\log(a)log(a)
 et
log⁡(b)\log(b)log(b)
.
3.Soit 
nnn
un entier relatif. Que vaut
log⁡(10n)\log(10^n)log(10n)
 ?
4.Montrer que la fonction logarithme décimal est strictement croissante sur 
]0 ;+∞[.]0~;+\infty[.]0 ;+∞[.

Premier algorithme de Briggs

L’algorithme suivant – qui porte parfois le nom de Briggs – permet de calculer le logarithme décimal de tout réel compris entre 1 et 10… Ce qui est amplement suffisant pour calculer le logarithme de n’importe quel nombre.
En effet, pour tout réel positif
xxx
, il existe un réel 
aaa
compris entre 1 et 10 et un entier relatif 
nnn
tel que
x=a×10nx=a \times 10^nx=a×10n
 (il s’agit de l’écriture scientifique étendue à tous les réels, et pas seulement aux nombres décimaux). 
Ainsi, on a
log⁡(x)=log⁡(a×10n)=log⁡(a)+log⁡(10n)=log⁡(a)+n\log(x)=\log(a \times 10^n)=\log(a)+\log(10^n)=\log(a)+nlog(x)=log(a×10n)=log(a)+log(10n)=log(a)+n
.
Le principe de cet algorithme ressemble beaucoup à celui de l’algorithme de dichotomie, utilisé pour trouver une valeur approchée d’une solution d’une équation. 
On souhaite calculer le logarithme décimal d'un réel 
aaa
compris entre 1 et 10 avec une précision de 
10−p10^{-p}10−p
On initialise nos valeurs
ggg
 vaut 1 (
ggg
représente la borne inférieure de l’intervalle).
ddd
 vaut 10 (
ddd
représente la borne supérieure de l’intervalle, 
aaa
sera toujours dans l’intervalle
[g;d][g;d][g;d]
).
log⁡_g\log\_glog_g
 vaut 0.
log⁡_d\log\_dlog_d
 vaut 1.
Tant que l’écart entre\(\log\_g\) et\(\log\_d\) est supérieur à \(10^{−p}\)
    • On calcule la moyenne géométrique 
mmm
de 
ggg
et 
ddd
: elle vaut 
gd\sqrt{gd}gd​
.
    • On calcule la moyenne arithmétique
log⁡_m\log\_mlog_m
 de
log⁡_g\log\_glog_g
 et
log⁡_d\log\_dlog_d
, qui correspond au logarithme de 
mmm
.
    • Si 
aaa
est supérieur à
mmm
, cela signifie que 
aaa
est entre 
mmm
et
ddd
 et donc que
log⁡_a\log\_alog_a
est entre
log⁡_m\log\_mlog_m
et
log⁡_d\log\_dlog_d
 par croissance de la fonction 
log⁡\loglog
sur 
]0;+∞[]0;+\infty[]0;+∞[
.On remplace donc la valeur de 
ggg
par celle de 
mmm
.On remplace la valeur de 
log⁡_g\log\_glog_g
 par celle de 
log⁡_m\log\_mlog_m
.
    • Sinon, 
aaa
est inférieur ou égal à
mmm
, cela signifie que 
aaa
est entre 
ggg
et 
mmm
et donc que 
log⁡_a\log\_alog_a
est entre 
log⁡_g\log\_glog_g
et 
log⁡_m\log\_mlog_m
.On remplace donc la valeur de 
ddd
par celle de 
mmm
.On remplace la valeur de
log⁡_d\log\_dlog_d
 par celle de 
log⁡_m\log\_mlog_m
Une fois la boucle terminée, on renvoie la valeur de\(\log\_g\).
Exercice
En reprenant le principe de l'algorithme énoncé ci-dessus, compléter le programme ci-dessous permettant de calculer le logarithme décimal d'un réel 
aaa
compris entre 1 et 10 avec une précision de
10−p10^{-p}10−p
.
À l'aide de cette fonction, donner une valeur de 
log⁡(5)\log(5)log(5)
à
10−1010^{-10}10−10
 près.
from math import sqrt
def briggs(a, p):
    '''
    a : un réel compris entre 1 et 10 dont on souhaite calculer le logarithme décimal
    p : un entier qui indique la précision souhaitée (10 ** (-p) près )
    '''
    g = ...
    d = ...
    log_g = ...
    log_d = ...
    while log_d - log_g > 10**(-p):
        m = 
        log_m = ...
        if a > m :
            ... = m
            ... = log_m
        else :
            ... = m
            ... = log_m
    return round(log_g,p)

Un algorithme historique

Un exemple détaillé de fonctionnement du premier algorithme de Briggs est notamment donné par Euler dans sonIntroduction à l’analyse infinitésimale.

u0=au_0=au0​=a
 et, pour tout entier naturel
nnn
, 
un+1=unu_{n+1}=\sqrt{u_n}un+1​=un​​
.
1.Pour tout entier naturel
nnn
, on pose 
wn=ln⁡(un)w_n=\ln(u_n)wn​=ln(un​)
.
    a.Montrer que la suite 
(wn)(w_n)(wn​)
est géométrique et exprimer
wnw_nwn​
 en fonction de 
nnn
pour tout entier naturel
nnn
.
    b.Exprimer 
unu_nun​
en fonction de 
nnn
pour tout entier naturel 
nnn
.
    c.En déduire
lim⁡n→+∞un\displaystyle\lim_{n\to+\infty}u_nn→+∞lim​un​
.
2.On rappelle qu’une fonction 
fff
est dérivable en 
aaa
si le quotient
f(x)−f(a)x−a\dfrac{f(x)-f(a)}{x-a}x−af(x)−f(a)​
 admet une limite finie quand 
xxx
tend vers
aaa
.
    a.Que vaut
ln⁡′(1)\ln^{\prime}(1)ln′(1)
 ?
    b.En déduire la valeur de
lim⁡x→1ln⁡(x)x−1\displaystyle\lim_{x\to 1}\dfrac{\ln(x)}{x-1}x→1lim​x−1ln(x)​
.
    c.En déduire la valeur de
lim⁡n→+∞2n(un−1)\displaystyle\lim_{n \to +\infty}2^n(u_n-1)n→+∞lim​2n(un​−1)
. Indication : multiplier et diviser cette quantité par
ln⁡(un)\ln(u_n)ln(un​)
.

Implémentation de l'algorithme

Compléter la fonction suivante pour qu'elle renvoie une valeur approchée de
ln⁡(a)\ln(a)ln(a)
.
Pour cela, cette fonction calculera le terme de rang 
nnn
de lasuite 
(un)(u_n)(un​)
définie par 
u0=au_0=au0​=a
et, pour tout entier naturel
nnn
,
un+1=unu_{n+1}=\sqrt{u_n}un+1​=un​​
,  puis renverra la valeur de
2n×(un−1)2^n \times (u_n-1)2n×(un​−1)
.
from math import sqrt
def briggs2(a, n):
    u = ...
    for i in range(n) :
        u = ...
    return ...

+∞+\infty+∞
, il existe un entier 
n0n_0n0​
tel que  
x×2n0⩽10⩽x×2n0+1x\times 2^{n_0} \leqslant 10 \leqslant x \times 2^{n_0+1}x×2n0​⩽10⩽x×2n0​+1
. Il s'avère que cet entier vaut au maximum 3, mais ce n'est pas important...
    • Puisque la suite
(1,1n)(1,1^n)(1,1n)
 tend vers
+∞+\infty+∞
, il existe un entier
n1n_1n1​
 tel que
x×2n0×1,1n1⩽10⩽x×2n0×1,1n1+1x \times 2^{n_0} \times 1,1^{n_1} \leqslant 10 \leqslant x \times 2^{n_0} \times 1,1^{n_1+1}x×2n0​×1,1n1​⩽10⩽x×2n0​×1,1n1​+1
.
    • Puisque la suite
(1,01n)(1,01^n)(1,01n)
 tend vers
+∞+\infty+∞
, il existe un entier
n2n_2n2​
 tel que
x×2n0×1,1n1×1,01n2⩽10⩽x×2n0×1,1n1×1,01n2+1x \times 2^{n_0} \times 1,1^{n_1} \times 1,01^{n_2} \leqslant 10 \leqslant x \times 2^{n_0} \times 1,1^{n_1} \times 1,01^{n_2+1}x×2n0​×1,1n1​×1,01n2​⩽10⩽x×2n0​×1,1n1​×1,01n2​+1
...
Et ainsi de suite : on établit un
kkk
-uplet d'entiers naturels
(n0,n1,n2,…,nk)(n_0, n_1, n_2, \dots, n_k)(n0​,n1​,n2​,…,nk​)
 et on approche 
xxx
par la valeur
x≃102n0×1,1n1×1,01n2×⋯×(1+10−k)nkx\simeq\dfrac{10}{2^{n_0} \times 1,1^{n_1} \times 1,01^{n_2} \times \dots \times (1+10^{-k})^{n_k}}x≃2n0​×1,1n1​×1,01n2​×⋯×(1+10−k)nk​10​
.
Il s'agit en fait d'appliquer plusieurs fois de suite un algorithme de seuil.
Il en vient que 
ln⁡(x)≃ln⁡(10)−n0ln⁡(2)−n1ln⁡(1,1)−n2ln⁡(1,01)−⋯−nkln⁡(1+10−k)\ln(x) \simeq \ln(10) - n_0 \ln(2)-n_1\ln(1,1)-n_2\ln(1,01)- \dots - n_k \ln(1+10^{-k})ln(x)≃ln(10)−n0​ln(2)−n1​ln(1,1)−n2​ln(1,01)−⋯−nk​ln(1+10−k)
.
Cet algorithme est très efficace puisque la multiplication par
1+10^{-k}
est rapide. L'algorithme CORDIC peut alors être implémenté de la façon suivante.
from math import log
# En Python, le logarithme népérien s'écrit log
def cordic(x , n = 10) :
    '''
    x : un réel entre 1 et 10 dont on veut calculer le logarithme népérien
    n : la plus grande valeur de k pour laquelle ln(1+10^(-k)) est stockée en mémoire
    '''
    log_x = log(10)
    for k in range(n+1) :
        z = 1 + 10 ** (-k)
        while x * z <= 10 :
            x = x * z
            log_x = log_x - log(z) #log(z) est en mémoire, on peut l'utiliser ici
    return log_x
Exercice
L'algorithme ci-dessus, implémenté en Python, permet de calculer une valeur approchée du logarithme d'un réel 
xxx
entre 1 et 10.
Expliquer à quoi servent les instructions des trois dernières lignes.