algorithm - 分割統治法を使用した整数乗算アルゴリズム？

Question

宿題として、O（n）未満で機能する分割統治法を使用して、1000桁の数値に整数乗算を実装する必要があります。どのアルゴリズムを調べる必要がありますか？

Answer 1

Schönhage–Strassenアルゴリズムは、既知の最速の乗算アルゴリズムの1つです。O（n log n log log n）時間がかかります。

Fürerのアルゴリズムは、これまでに知られている最速の多数乗算アルゴリズムであり、O（n * log n * 2 ^{O（log * n）}）の時間がかかります。

乗算アルゴリズムがO（n）以下になることはないと思います。それは単に不可能です。

Answer 2

カラツバアルゴリズムを見てください。これには、分割統治法で簡単にモデル化できる再帰ステップが含まれます。