Next: , Previous: , Up: Division Algorithms   [Index]


15.2.4 ブロックBarrett除算

大きな数で割る時には, ブロックBarrett除算アルゴリズムを使います。 ここで,割る数,割られる数のサイズによって精度を決め,割る数の逆数をこの精度で求めます。 商リムのブロックは,割られる数にこの逆数をブロック単位で乗じることで生成されていきます。

我々の実装したブロックアルゴリズムは,素のBarrettアルゴリズムより小さい逆数を使いますので,サイズは ceil(n/2)リム程度になります。