OpenAI Math Digest
メニュー
AI生成の解説

このサイトの解説には、誤りや不正確な説明が含まれる可能性があります。重要な主張・証明は原論文でご確認ください。

COMICS · CATALOGUE 109

n log n未満の整数乗算

Integer multiplication below n log n

n log n未満の整数乗算を、計算モデル、既存の高速乗算、再帰とデータ移動の観点から紹介します。 カタログ内の全原稿・全結果を網羅するものではありません。

日本語の漫画2枚
1枚目:作り直し版タップして拡大できます 拡大して読む ↗画像を直接開く ↗
カタログ109「n log n未満の整数乗算」を紹介する日本語の8コマ漫画
2枚目:これまでの掲載版タップして拡大できます 拡大して読む ↗画像を直接開く ↗
カタログ109「n log n未満の整数乗算」を紹介する日本語の8コマ漫画

岩井の補足

これも意外な結果. 競技プログラミングなどn log nのアルゴリズムって山ほどあるんで, 整数の掛け算の計算量がn log nを下回るとは人間は思わないと思う. 実際Harvey–van der Hoevenがn log nを示した後は, 終わった問題だと思われていたはずである. AIじゃないとこの先入観は消せないと思う. ちなみに実用上はn log nでいいらしい. 定数項があまりにも大きいためである.

漫画の拡大表示

拡大した画像は、上下左右にスクロールして読めます。