回答編集履歴
1
並列化についても追記
answer
CHANGED
|
@@ -1,4 +1,4 @@
|
|
|
1
|
-
乗算に関しては、[Karatsuba法](https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%A9%E3%83%84%E3%83%90%E6%B3%95)では半分の桁の掛け算を、4つではなく3つに減らすことができるので、「両方の桁数の積」より速く計算することができます（n桁×n桁の掛け算ででO(n^1.59)程度）。さらに桁数が増えれば、高速フーリエ変換を使ったアルゴリズムがあって、O(n log n)より少し大きいぐらいのオーダーで処理できます。
|
|
1
|
+
乗算に関しては、[Karatsuba法](https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%A9%E3%83%84%E3%83%90%E6%B3%95)では半分の桁の掛け算を、4つではなく3つに減らすことができるので、「両方の桁数の積」より速く計算することができます（n桁×n桁の掛け算ででO(n^1.59)程度）し、3つの乗算のうち2つは並列実行できます。さらに桁数が増えれば、高速フーリエ変換を使ったアルゴリズムがあって、O(n log n)より少し大きいぐらいのオーダーで処理できます。
|
|
2
2
|
|
|
3
3
|
これに対して、除算の場合、「分けて計算する」という方法が使えないので、O(n^2)のオーダーから減らすことができません（「割る数の桁数に比例した処理」を「割られる数の桁数に比例した回数」だけ繰り返すことになります）。上の桁が決まらないと下の桁の計算に入れないので、並列実行にも向きません。
|
|
4
4
|
|