大きな数字の部分

Question

学校の方法以外の大きな整数（1000桁以上）を分割する方法はありますか？

Answer 1

ウィキペディアのリストmultiple division algorithms。 Mが漸近的O(n log n 2^(log*n))として良いかもしれない使用乗算アルゴリズムの複雑さは、ここでSchoolbook long divisionM(n)としてO(n^2)ようとNewton's methodリストされComputational complexity of mathematical operations参照してください。最高のアルゴリズムの漸近的には必ずしも「小」の入力のための最速ではないことをone of the multiplication algorithmsの議論から

注：実際には

Schönhage-Strassenのアルゴリズムは、このようなカラツバやToom-などの古い方法をアウトパフォームし始め2 ^（2^15）から2 ^（2^17）（10進数は10,000〜40,000）を超える数の乗数を調理します。 GNU Multi-Precision Libraryは、アーキテクチャーに応じて、少なくとも1728〜7808の64ビットワード（111,000〜500,000の10進数）の値に使用します。 Schönhage-Strassenには74,000桁以上の10進数を使用するJava実装があります。