アナトリー・カラツバはソ連・ロシアの数学者で、解析的整数論と計算数学を研究し、ステクロフ数学研究所およびモスクワ大学で活動した。
1960年、モスクワ大学の学生であったときに、n桁の数の乗算にはn^2に比例する演算が必要だというアンドレイ・コルモゴロフの予想を覆す分割統治アルゴリズムを考案した。約n^1.585回の演算で乗算を行うこの手法はカラツバ法と呼ばれ、二乗時間より速い最初の乗算アルゴリズムである。
Anatoly Karatsuba
大きな数の乗算を高速化するカラツバ法を考案したソ連・ロシアの数学者(1937~2008年)。
アナトリー・カラツバはソ連・ロシアの数学者で、解析的整数論と計算数学を研究し、ステクロフ数学研究所およびモスクワ大学で活動した。
1960年、モスクワ大学の学生であったときに、n桁の数の乗算にはn^2に比例する演算が必要だというアンドレイ・コルモゴロフの予想を覆す分割統治アルゴリズムを考案した。約n^1.585回の演算で乗算を行うこの手法はカラツバ法と呼ばれ、二乗時間より速い最初の乗算アルゴリズムである。
この説明は、AIPOSTの記事と広く知られた事実をもとにまとめたものです。誤りがあれば訂正依頼でお知らせください。
1950年代、アンドレイ・コルモゴロフ氏は2つのnビット整数の乗算には2乗の時間が必要だと予想しましたが、23歳の教え子アナトリー・カラツバ氏は1週間以内により高速なアルゴリズムを見つけました。
記事を読む事典の説明は、AIPOSTの記事と広く知られた事実をもとにまとめています。誤りは訂正依頼でお知らせいただければ、確認して修正します。新しい記事に登場した名前は、記事の公開後に事典に加わります。