algorithm - クレイジーな大きな整数の除算のための最速のアルゴリズムは何ですか?

Question

バイト配列の数字として表される数値を、標準以外のバイト数で分割する必要があります。おそらく5バイトまたは1 GB以上です。除算は、数値に変換せずに、バイト配列として表された数値で行う必要があります。

Answer 1

分割統治法による除算は、非常に大きな整数の教科書の方法よりもはるかに高速になります。

GMPは最先端の大数ライブラリです。ほぼすべてについて、特定のオペランド サイズに合わせて調整されたさまざまなアルゴリズムの実装がいくつかあります。

これはGMPの「除算アルゴリズム」のドキュメントです。アルゴリズムの説明は少し簡潔ですが、少なくとも、もっと知りたいときにグーグルに何かを与える.

Brent と Zimmermann の Modern Computer Arithmeticは、大数演算の理論と実装に関する優れた本です。知られていることを知りたい場合は、おそらく読む価値があります。

Answer 2

小学校の長割りに似た標準の長割りアルゴリズムは、Knuth 4.3.1 で説明されているアルゴリズム Dです。クヌースは、彼の本のそのセクションで除算について広範な議論を行っています。この結果、アルゴリズム D よりも高速な方法がありますが、それらはそれほど高速ではなく、アルゴリズム D よりもはるかに複雑です。

可能な限り高速なアルゴリズムを取得することに決めた場合は、SRT アルゴリズムとして知られているものに頼ることができます。

これ以上のすべては、Wikipedia Division Algorithmの方法でカバーされています。