アナトリー・カラツバ

Anatoly Karatsuba

大きな数の乗算を高速化するカラツバ法を考案したソ連・ロシアの数学者(1937~2008年)。

記事1本最終言及

アナトリー・カラツバはソ連・ロシアの数学者で、解析的整数論と計算数学を研究し、ステクロフ数学研究所およびモスクワ大学で活動した。

1960年、モスクワ大学の学生であったときに、n桁の数の乗算にはn^2に比例する演算が必要だというアンドレイ・コルモゴロフの予想を覆す分割統治アルゴリズムを考案した。約n^1.585回の演算で乗算を行うこの手法はカラツバ法と呼ばれ、二乗時間より速い最初の乗算アルゴリズムである。

この説明は、AIPOSTの記事と広く知られた事実をもとにまとめたものです。誤りがあれば訂正依頼でお知らせください。

この項目を扱った記事

  • OpenAIのAIが指数時間仮説を反証、P=NPではないが理論の土台が揺らぐAIニュース ·

    1950年代、アンドレイ・コルモゴロフ氏は2つのnビット整数の乗算には2乗の時間が必要だと予想しましたが、23歳の教え子アナトリー・カラツバ氏は1週間以内により高速なアルゴリズムを見つけました。

    記事を読む

説明の誤りや、見つからない項目はありますか?

事典の説明は、AIPOSTの記事と広く知られた事実をもとにまとめています。誤りは訂正依頼でお知らせいただければ、確認して修正します。新しい記事に登場した名前は、記事の公開後に事典に加わります。