バレットの還元アルゴリズム
16 ビット整数のシステム上で n = 101 {\displaystyle n=101} としたときを考える。
アルゴリズムが意味をなすためには、少なくとも k {\displaystyle k} は 7 {\displaystyle 7} 以上である必要がある。さもなくば、剰余を必要としない小さい値に対してしか還元が正しく動作しなくなってしまう。 k = 7 {\displaystyle k=7} のときは、 m = ⌊ 2 k / n ⌋ = ⌊ 128 / 101 ⌋ = 1 {\displaystyle m=\lfloor 2^{k}/n\rfloor =\lfloor 128/101\rfloor =1} であり、 k = 8 {\displaystyle k=8} のときは m = ⌊ 256 / 101 ⌋ = 2 {\displaystyle m=\lfloor 256/101\rfloor =2} である。後者においては 1 / 101 {\displaystyle 1/101} を 2 / 256 {\displaystyle 2/256} で近似することになるので、前者における 1 / 128 {\displaystyle 1/128} による近似と全く等価になる。 k = 9 {\displaystyle k=9} とすれば m = ⌊ 512 / 101 ⌋ = 5 {\displaystyle m=\lfloor 512/101\rfloor =5} となり、よりよい近似を得る。