「カラツバ法」の版間の差分
削除された内容 追加された内容
その後で「加減算の回数」とあるのでこちらも単に「乗算の回数」でいいでしょう |
編集の要約なし |
||
1行目:
'''カラツバ法'''（カラツバほう）とは、主に[[多倍長乗算]]の{{仮リンク|乗算アルゴリズム|en|Multiplication algorithm}}において、[[乗算]]の回数を4分の3にする[[アルゴリズム]]である。
加減算の回数は増加するが、乗算コストはそれより遙かに大きいため、結果として演算コストそのものもほぼ4分の3となる。
発見者の[[:ru:
従来の乗算は<math>O(n^2)</math>だったが、Karatsuba法の再帰的適用により、<math>O(n^{\log_23})</math>（<math>\log_23</math>≒1.585）まで計算コストが抑えられる。
13行目:
:<math>Z := z_2 \cdot b^2 + z_1 \cdot b + z_0</math>
この乗算をKaratsuba以前の方法（[[:en:Multiplication algorithm#Long multiplication|Long multiplication]]）で行うと、乗算を4回行うことになる。
:<math>z_2 := x_1 \times y_1</math>
:<math>z_0 := x_0 \times y_0</math>
28行目:
:<math>z_1:=z_2+z_0-(x_1-x_0)(y_1-y_0)=1216+13890-(-431)(8)=18554</math>
:<math>Z=1216 b^2 + 18554 b + 13890 = 1,216,000,000 + 18,554,000 + 13,890 = 1,234,567,890</math>
== 関連項目 ==
* [[:en:Toom–Cook multiplication]]（カラツバ法はToom-3の特別な場合である）
* [[:en:Schönhage–Strassen algorithm]]（[[高速フーリエ変換]]を使う方法で、カラツバ法やToom-3より高速なアルゴリズムである）
{{DEFAULTSORT:からつはほう}}
| |||