翻訳と辞書 Words near each other ・ Kanon (ゲーム) ・ Kanon -The snow talks memories- 雪降る街の物語 ・ Kanon×kanon ・ Kanon～水瀬さんち ・ Kanoso↑ ・ Kanoso～思い出を壊す物語～ ・ Kan拡張 ・ Kappa-One登竜門 ・ Kappo仙台闊歩 ・ Kappo仙台闊歩 Men's ・ Karatsuba法 ・ Karen (漫画) ・ Karl Höfner GmbH ・ Kasch環 ・ Kauņa ・ Kawase (企業) ・ Kay (ペンスピナー) ・ Kaya (歌手) ・ Kay稲毛 ・ Kb/in² Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Karatsuba法 ： ミニ英和和英辞書 Karatsuba法[ほう] ===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 法 ： [ほう] 　 1. (n,n-suf) Act (law: the X Act)　 Karatsuba法 （ リダイレクト：カラツバ法 ） ： ウィキペディア日本語版 カラツバ法[からつばほう] カラツバ法（カラツバほう）とは、主に多倍長乗算のにおいて、乗算の回数を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.