翻訳と辞書 Words near each other ・ カラッチ ・ カラット ・ カラット∞原石ガール ・ カラット・サラーフ・アッディーン ・ カラット探偵事務所の事件簿 ・ カラッファ・ディ・カタンザーロ ・ カラッファ・ディ・カタンツァーロ ・ カラッファ・デル・ビアンコ ・ カラッリョ ・ カラツキヌメモン ・ カラツバ法 ・ カラテ ・ カラテオドリ ・ カラテオドリの存在定理 ・ カラテオドリの定理 ・ カラテオドリの定理 (凸包) ・ カラテオドリの定理 (等角写像) ・ カラテオドリの拡張定理 ・ カラテオドリの条件 ・ カラテオドリ計量 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク カラツバ法 ： ウィキペディア日本語版 カラツバ法[からつばほう] カラツバ法（カラツバほう）とは、主に多倍長乗算のにおいて、乗算の回数を4分の3にするアルゴリズムである。 加減算の回数は増加するが、乗算コストはそれより遥かに大きいため、結果として演算コストそのものもほぼ4分の3となる。 発見者のAnatolii Alexeevitch Karatsuba（）の名前を取ってKaratsuba法(Karatsuba-algorithm)、あるいは単にKaratsubaとも呼ばれる。 従来の乗算は$O(n^2)$だったが、Karatsuba法の再帰的適用により、$O(n^)$（$\backslash log\_23$≒1.585）まで計算コストが抑えられる。 == アルゴリズム == 単純な例として、被乗数$X$と乗数$Y$の積$Z$を求める($Z\; =\; X\; \backslash times\; Y$)。 まず、被乗数$X$と乗数$Y$をそれぞれ上位・下位の2つに分割する。 分割の基数を$b$（例えば3桁ずつに分割するなら$b:=1000$）とすると、 :$X\; :=\; x\_1\; \backslash cdot\; b\; +\; x\_0$ :$Y\; :=\; y\_1\; \backslash cdot\; b\; +\; y\_0$ :$Z\; :=\; z\_2\; \backslash cdot\; b^2\; +\; z\_1\; \backslash cdot\; b\; +\; z\_0$ この乗算をKaratsuba以前の方法（Long multiplication）で行うと、乗算を4回行うことになる。 :$z\_2\; :=\; x\_1\; \backslash times\; y\_1$ :$z\_0\; :=\; x\_0\; \backslash times\; y\_0$ :$z\_1\; :=\; x\_1\; \backslash times\; y\_0\; +\; x\_0\; \backslash times\; y\_1$ Karatsubaの方法では、乗算を3回で済ませられる。 :$z\_1\; :=\; z\_2\; +\; z\_0\; -\; (x\_1\; -\; x\_0)\; \backslash times\; (y\_1\; -\; y\_0)$ 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「カラツバ法」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.