pourquoi ça marche: racine carrée

Soit $x$ un réel positif, il existe une et une seule suite d'entiers $(m_n)_{n\in \N}$ telle que pour tout $n\in \N$, $$\left(\frac{m_n}{10^n} \right)^2 \leq x < \left(\frac{m_n+1}{10^n} \right)^2 \tag{1}$$. Il existe également une seule suite d'entiers $(k_n)_{n \in \N}$ telle que $k_0=m_0$ et pour tout $n\geq 1$, $m_{n+1}=k_{n+1}+10m_n$ et $k_n\in \{0,1,2,...,9\}$.
Les entiers $(k_n)_{n \in \N^*}$ sont appelés chiffres de la racine carrée de $x$ en base 10.

On a les inégalités suivantes pour tout $n\in \N$: $$m_n^2 \leq \left(m_n+\frac{k_{n+1}}{10} \right)^2 \leq 10^{2n}x < \left (m_n+\frac{1+k_{n+1}}{10} \right)^2 \leq(m_n+1)^2 \tag{2}$$ et en développant:

$$m_n^2 \leq m_n^2 +\frac{2m_nk_{n+1}}{10} + \frac{k_{n+1}^2}{100} \leq 10^{2n}x < m_n^2 +\frac{2m_n(k_{n+1}+1)}{10} + \frac{(k_{n+1}+1)^2}{100} \tag{3}\leq (m_n+1)^2 $$. Autrement dit $k_{n+1}$ est le plus grand entier tel que $\displaystyle{\frac{2m_nk_{n+1}}{10} + \frac{k_{n+1}^2}{100} \leq 10^{2n}x-m_n^2}$, avec $m_n=\sum_{i=0}^n 10^{n-i} k_i$.

C'est cet entier $k_{n+1}$ qui est déterminé par la $n+2$-ième étape de l'algorithme (je dis $n+2$ car on commence à $0$).


Posons également $r_n:= 10^{2n} -m_n$. Alors $100r_n-20m_n k_{n+1}-k_{n+1}^2= r_{n+1}$ et en réécrivant ce qui précède, l'algo consiste à trouver pour tout $n$ le plus grand entier $k_{n+1}$ tel que $\displaystyle{\frac{2m_nk_{n+1}}{10} + \frac{k_{n+1}^2}{100} \leq r_n}$.