Réduction de Barrett

Regardons le cas ${\displaystyle n=101}$ en utilisant des entiers de 16 bits.

La plus petite valeur de ${\displaystyle k}$ qui a du sens est ${\displaystyle k=7}$ car si ${\displaystyle 2^{k}<n}$ alors la réduction ne sera valide que pour des valeurs qui sont déjà minimales ! Pour une valeur de sept, ${\displaystyle m=\lfloor 2^{k}/n\rfloor =\lfloor 128/101\rfloor =1}$. Pour une valeur de huit ${\displaystyle m=\lfloor 256/101\rfloor =2}$. Ainsi ${\displaystyle k=8}$ ne donne aucun avantage car l'approximation de ${\displaystyle 1/101}$, dans ce cas ${\displaystyle 2/256}$, est exactement la même que ${\displaystyle 1/128}$. Pour ${\displaystyle k=9}$, on obtient ${\displaystyle m=512/101=5}$, qui donne une meilleure approximation.

Maintenant, considérons les intervalles de validité pour ${\displaystyle k=7}$ et ${\displaystyle k=9}$.

Dans le premier cas, ${\displaystyle e=1/n-m/2^{k}=1/101-1/128=27/12928}$ donc ${\displaystyle a<1/e}$ implique ${\displaystyle a<478.81}$. Puisque ${\displaystyle a}$ est un entier, la valeur maximum effective est 478. (En pratique la fonction donne le bon résultat jusque 504.)

Si on prend ${\displaystyle k=9}$ alors ${\displaystyle e=1/101-5/512=7/51712}$ et donc la valeur maximum de ${\displaystyle a}$ est 7387. (En pratique la fonction donne le bon résultat jusque 7473.)

La valeur suivante de ${\displaystyle k}$ qui donne une meilleure approximation est 13, donnant ${\displaystyle 81/8192}$. Cependant, notons que la valeur intermédiaire ${\displaystyle ax}$ dans les calculs va dépasser la capacité d'un entier 16 bits non-signé lorsque ${\displaystyle 810\leq a}$, ainsi ${\displaystyle k=7}$ fonctionne mieux dans cette situation.

Soit ${\displaystyle k_{0}}$ le plus petit entier tel que ${\displaystyle 2^{k_{0}}>n}$. Prenons ${\displaystyle k_{0}+1}$ comme valeur raisonnable pour ${\displaystyle k}$ dans les équations précédentes. Comme dans les fragments de code ci-dessus, soit

• ${\displaystyle q=\left\lfloor {\frac {ma}{2^{k}}}\right\rfloor }$ et
• ${\displaystyle r=a-qn}$.

Grâce à la fonction partie entière, ${\displaystyle q}$ est un entier et ${\displaystyle r\equiv a{\pmod {n}}}$. Aussi, si ${\displaystyle a<2^{k}}$ alors ${\displaystyle r<2n}$. Dans ce cas, en écrivant le fragment de code en expression :

${\displaystyle a\,{\bmod {\,}}n={\begin{cases}r&{\text{si }}r<n\\r-n&{\text{sinon}}\end{cases}}}$

La preuve que ${\displaystyle r<2n}$ est alors immédiate :

Si ${\displaystyle a<2^{k}}$, alors

${\displaystyle {\frac {a}{2^{k}}}\cdot (2^{k}\mod n)<n}$

Puisque ${\displaystyle n\cdot {\frac {ma\mod 2^{k}}{2^{k}}}<n}$ indépendamment de ${\displaystyle a}$, on obtient :

${\displaystyle {\frac {a\cdot (2^{k}\mod n)}{2^{k}}}+n\cdot {\frac {ma\mod 2^{k}}{2^{k}}}<2n}$

${\displaystyle a-\left(a-{\frac {a\cdot (2^{k}\mod n)}{2^{k}}}\right)+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n}$

${\displaystyle a-{\frac {a}{2^{k}}}\cdot \left(2^{k}-(2^{k}\mod n)\right)+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n}$

${\displaystyle a-{\frac {na}{2^{k}}}\cdot \left({\frac {2^{k}-(2^{k}\mod n)}{n}}\right)+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n}$

${\displaystyle a-{\frac {na}{2^{k}}}\cdot \left\lfloor {\frac {2^{k}}{n}}\right\rfloor \ +{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n}$

${\displaystyle a-{\frac {nma}{2^{k}}}+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n}$

${\displaystyle a-\left({\frac {ma-(ma\mod 2^{k})}{2^{k}}}\right)\cdot n<2n}$

${\displaystyle a-\left\lfloor {\frac {ma}{2^{k}}}\right\rfloor \cdot n<2n}$

${\displaystyle a-qn<2n}$

${\displaystyle r<2n}$