回答編集履歴
1
並列化についても追記
test
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
|
|
|
4
4
|
|