Algorithme et programmation

Premier algorithme de Briggs

Logarithme décimal

Pour tout réel strictement positif

a

, on appelle logarithme en base

10

de

a

le réel noté 

\log(a)

et défini par

\log(a)=\dfrac{\ln(a)}{\ln(10)}

.
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)=\dfrac{\log(a)}{\log(e)}

.

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 

a

et

b

et pour tout entier relatif

n

, on a

\log(ab)=\log(a)+\log(b)

,

\log(\sqrt{a})=\dfrac{1}{2}\log(a)

et

\log(a^n)=n \times \log(a)

.
2.Exprimer 

\log(\sqrt{ab})

 en fonction de

\log(a)

et

\log(b)

.
3.Soit 

n

un entier relatif. Que vaut

\log(10^n)

 ?
4.Montrer que la fonction logarithme décimal est strictement croissante sur 

]0~;+\infty[.

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

x

, il existe un réel 

a

compris entre 1 et 10 et un entier relatif 

n

tel que

x=a \times 10^n

 (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 \times 10^n)=\log(a)+\log(10^n)=\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 

a

compris entre 1 et 10 avec une précision de 

10^{-p}

On initialise nos valeurs

g

 vaut 1 (

g

représente la borne inférieure de l’intervalle).

d

 vaut 10 (

d

représente la borne supérieure de l’intervalle, 

a

sera toujours dans l’intervalle

[g;d]

).

\log\_g

 vaut 0.

\log\_d

 vaut 1.

Tant que l’écart entre\(\log\_g\) et\(\log\_d\) est supérieur à \(10^{−p}\)

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On calcule la moyenne géométrique 

m

de

g

et

d

: elle vaut 

\sqrt{gd}

.

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On calcule la moyenne arithmétique

\log\_m

de

\log\_g

et

\log\_d

, qui correspond au logarithme de 

m

.

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;Si 

a

est supérieur à

m

, cela signifie que 

a

est entre 

m

et

d

 et donc que

\log\_a

est entre

\log\_m

et

\log\_d

 par croissance de la fonction 

\log

sur

]0;+\infty[

.On remplace donc la valeur de 

g

par celle de 

m

.On remplace la valeur de 

\log\_g

 par celle de 

\log\_m

.

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;Sinon, 

a

est inférieur ou égal à

m

, cela signifie que 

a

est entre 

g

et

m

et donc que 

\log\_a

est entre 

\log\_g

et

\log\_m

.On remplace donc la valeur de 

d

par celle de 

m

.On remplace la valeur de

\log\_d

 par celle de 

\log\_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 

a

compris entre 1 et 10 avec une précision de

10^{-p}

.

À l'aide de cette fonction, donner une valeur de 

\log(5)

à

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.

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 

a

un réel strictement positif. Pour approcher

\ln(a)

, on utilise la suite 

(u_n)

définie par 

u_0=a

et, pour tout entier naturel

n

,

u_{n+1}=\sqrt{u_n}

. 
On a alors 

\displaystyle\lim_{n\to + \infty}2^n\times (u_n-1)=\ln(a)

.
L'exercice ci-dessous propose une démonstration de ce résultat.

Exercice

Soit

a>0

. On considère la suite

(u_n)

 définie par

u_0=a

 et, pour tout entier naturel

n

,

u_{n+1}=\sqrt{u_n}

.

1.Pour tout entier naturel

n

, on pose 

w_n=\ln(u_n)

.
    a.Montrer que la suite 

(w_n)

est géométrique et exprimer

w_n

 en fonction de 

n

pour tout entier naturel

n

.
    b.Exprimer 

u_n

en fonction de 

n

pour tout entier naturel 

n

.
    c.En déduire

\displaystyle\lim_{n\to+\infty}u_n

.
2.On rappelle qu’une fonction 

f

est dérivable en 

a

si le quotient

\dfrac{f(x)-f(a)}{x-a}

 admet une limite finie quand 

x

tend vers

a

.
    a.Que vaut

\ln^{\prime}(1)

 ?
    b.En déduire la valeur de

\displaystyle\lim_{x\to 1}\dfrac{\ln(x)}{x-1}

.
    c.En déduire la valeur de

\displaystyle\lim_{n \to +\infty}2^n(u_n-1)

. Indication : multiplier et diviser cette quantité par

\ln(u_n)

.

Implémentation de l'algorithme

Compléter la fonction suivante pour qu'elle renvoie une valeur approchée de

\ln(a)

.

Pour cela, cette fonction calculera le terme de rang 

n

de lasuite 

(u_n)

définie par 

u_0=a

et, pour tout entier naturel

n

,

u_{n+1}=\sqrt{u_n}

,  puis renverra la valeur de

2^n \times (u_n-1)

.

from math import sqrt

def briggs2(a, n):
    u = ...
    for i in range(n) :
        u = ...
    return ...

Algorithme et programmation

Activité CAPYTALE : algorithmes de calcul du logarithme

Introduction

Premier algorithme de Briggs

Logarithme décimal

Premier algorithme de Briggs

Un algorithme historique

Second algorithme de Briggs

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

Implémentation de l'algorithme

Algorithme CORDIC