$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Algorithmes de Briggs

Les algorithmes de Briggs sont des algorithmes pour calculer des valeurs approchées de logarithmes de nombres entiers. Dans ce qui suit, nous allons les décrire pour le logarithme décimal, c'est-à-dire tel que $\log_{10}(10)=1$.

Premier algorithme de Briggs - calcul de $\log_{10}(2)$

L'idée du calcul de $\log_{10}(2)$ par Briggs est très simple. Puisque $1\leq 2\leq 10$, on a $$\log_{10}(1)\leq \log_{10}(2)\leq \log_{10}(10)\implies 0\leq \log_{10}(2)\leq 1.$$ On a donc un encadrement de $\log_{10}(2)$ à l'unité près. Supposons maintenant que l'on connaisse $k_1$ tel que $$10^{k_1}\leq 2^{10}\leq 10^{k_1+1}.$$ Alors, on a $$k_1=k_1 \log_{10}(10)\leq 10\log_{10}(2)\leq (k_1+1)\log_{10}(10)=k_1+1$$ ce qui donne encore $$\frac{k_1}{10}\leq \log_{10}(2)\leq \frac{k_1}{10}+\frac{1}{10}.$$ On a donc un encadrement de $\log_{10}(2)$ à $10^{-1}$ près. Plus généralement, supposons que l'on sache que $$10^{k_n}\leq 2^{10^n}\leq 10^{k_n+1}.$$ Alors on a, avec le même calcul, $$\frac{k_n}{10^n}\leq \log_{10}(2)\leq \frac{k_n}{10^n}+\frac{1}{10^n}.$$ On connait donc $\log_{10}(2)$ à $10^{-n}$ près. Pour obtenir une valeur approchée de $\log_{10}(2)$ à $10^{-n}$ près, il suffit donc de savoir le nombre de chiffres dans l'écriture décimale de $2^{10^n}.$ Pour calculer $2^{10^n}$, Briggs utilise une variante de l'algorithme d'exponentiation rapide, en effectuant les calculs suivants :

  • pour calculer $2^{10}$ : $$2^2=4;\ 2^4=(2^2)^2;\ 2^8=(2^4)^2;\ 2^{10}=2^8\times 2^2.$$
  • pour calculer $2^{100}$ : $$2^{20}=(2^{10})^2;\ 2^{40}=(2^{20})^2;\ 2^{80}=(2^{40})^2;\ 2^{100}=2^{20}\times 2^{80}.$$
  • pour calculer $2^{1000}$ : $$2^{200}=(2^{100})^2;\ 2^{400}=(2^{200})^2;\ 2^{800}=(2^{400})^2;\ 2^{1000}=2^{200}\times 2^{800}.$$
Algorithme de Briggs - Vlacq

L'algorithme de Briggs - Vlacq est à la fois une variante de l'algorithme précédent, et aussi une variante de l'algorithme de dichotomie. Il permet de calculer une valeur approchée du logarithme de tout nombre réel compris entre $1$ et $10$. Nous allons l'illustrer avec le calcul d'une valeur approchée de $\log_{10}(5)$. Pour cela, on définit 4 suites $(a_n)$, $(b_n)$, $(c_n)$ et $(d_n)$ qui vont avoir la signification suivante : $a_n$ et $b_n$ vont constituer un encadrement de $5$ de plus en plus précis, $a_n\leq 5\leq b_n$ pour tout entier $n$, de sorte que $c_n=\log_{10}(a_n)$ et $d_n=\log_{10}(b_n)$ vont constituer un encadrement de $\log_{10}(5)$ de plus en plus précis.

Pour cela, on initialise la construction en posant $a_1=1$, $b_1=10$ et donc $c_1=0$, $d_1=1$. On calcule ensuite $\sqrt{a_1\times b_1}=\sqrt{10}$. On constate que $\sqrt{10}\leq 5$ et on va poser $a_2=\sqrt{a_1b_1}$ et $b_2=b_1$. On a bien $a_2\leq 5\leq b_2$. L'intérêt de cette définition est que, grâce aux propriétés de la fonction logarithme, il est facile de calculer $c_2$ et $d_2$. On a en effet $$c_2=\log_{10}(\sqrt{a_1\times b_1})=\frac{1}{2}(\log(a_1)+\log(b_1))=\frac{c_1+d_1}2 \textrm{ et }d_2=d_1.$$ On itère alors la construction de la même façon. Précisément, on définit les suites au rang $n+1$ par :

  • si $\sqrt{a_n b_n}\leq 5$, alors on pose $$\begin{array}{rclcrcl} a_{n+1}&=&\sqrt{a_nb_n}&\quad&c_{n+1}&=&\frac{c_n+d_n}2\\ b_{n+1}&=&b_n&\quad&d_{n+1}&=&d_n. \end{array}$$
  • si $\sqrt{a_n b_n}> 5$, alors on pose $$\begin{array}{rclcrcl} a_{n+1}&=&a_n&\quad&c_{n+1}&=&c_n\\ b_{n+1}&=&\sqrt{a_nb_n}&\quad&d_{n+1}&=&\frac{c_n+d_n}2. \end{array}$$

Si on veut un encadrement de $\log_{10}(5)$ à $10^{-p}$ près, on s'arrête dès que $d_n-c_n\leq 10^{-p}$. On a donc un algorithme très proche de l'algorithme de dichotomie mais où au lieu de considérer la moyenne arithmétique des deux extrémités de l'intervalle, on considère leur moyenne géométrique.

Avec ces algorithmes, Briggs réalisa un véritable exploit. Dans son livre Arithmetica Logarithmica, publié en 1624, il publie une table des logarithmes de tous les nombres entiers de 1 à 20 000 et de 90 000 à 100 000 avec une précision de 14 chiffres après la virgule! Cette table est complétée quatre ans plus tard par Vlacq par les logarithmes des nombres entiers de 20 000 à 90 000.
Consulter aussi...