整数乗算の新手法「o(n log n)」論文、専門家も理解に苦戦 Hacker Newsで議論
姉妹サイトの新着
整数の掛け算にかかる時間の上限としてこれまで知られていたのは O(n log n) で、これは高速フーリエ変換(FFT)を使えば達成できるものだった。今回Hacker Newsで話題になったのは、それよりも厳密に小さい o(n log n) で済むと主張する新しい論文。スレでは、この分野の世界的権威でさえ2週間かけて論文の一部しか検証できていないという指摘から、数学の最先端がAI抜きでは追えなくなっているのではという議論に発展した。一方で「O と o は何が違うのか」という基本的な質問にも多くのレスがつき、技術的な解説で盛り上がった。
新たに提案された o(n log n) 整数乗算アルゴリズム [pdf]
出典: web.maths.unsw.edu.au / 元記事はこちら
＞o(n log n)の結果について、Leanなどで形式的な証明があるといいのだが、見た限りまだ存在しないようだ。
その結果は@platypiiと私でLean(Mathlibの TM2 マシン上)で完全に形式化済みです。指数部分の改善も継続中で、現在は 1-2^-14.38 まで来ています: https://github.com/platypii/integer-mult-bounds-lean
コントリビューション歓迎です!
その結果は@platypiiと私でLean(Mathlibの TM2 マシン上)で完全に形式化済みです。指数部分の改善も継続中で、現在は 1-2^-14.38 まで来ています: https://github.com/platypii/integer-mult-bounds-lean
コントリビューション歓迎です!
＞＞2
私は数学の形式化をクラウドソーシングするサイトの運営を手伝っています。この結果のLean版もありますよ: https://prove2.me/campaigns/integer-multiplication-kappa
私は数学の形式化をクラウドソーシングするサイトの運営を手伝っています。この結果のLean版もありますよ: https://prove2.me/campaigns/integer-multiplication-kappa
ここで注意したいのは、タイトルでは「O(n log n)」と書かれているが、重要なのは「o(n log n)」であって、ただの「O(n log n)」ではないということ。前者は後者の真部分集合に過ぎない。nビットの整数2つをO(n log n)時間で掛け合わせる方法は、FFTを使えば既に分かっていた。
＞＞6
詳しくない人のために聞きたいんだけど、Oとoってどう違うの?
詳しくない人のために聞きたいんだけど、Oとoってどう違うの?
＞＞32
もともとクヌースが定義したものです: https://dl.acm.org/doi/10.1145/1008328.1008329
もともとクヌースが定義したものです: https://dl.acm.org/doi/10.1145/1008328.1008329
＞＞32
f(n) = O(g(n)) は、nが大きくなっても f(n)/g(n) が一定値を超えて大きくならないという意味。
f(n) = o(g(n)) は、nが大きくなるにつれて f(n)/g(n) が0に近づいていくという意味。
f(n) = O(g(n)) は、nが大きくなっても f(n)/g(n) が一定値を超えて大きくならないという意味。
f(n) = o(g(n)) は、nが大きくなるにつれて f(n)/g(n) が0に近づいていくという意味。
この分野は初心者なんだけど、これって実際どう役立つの? 時間複雑度が低くてもほとんどの場面ではStrassenよりGEMMを使うし。何でも聞いてくれ、まだ何も分かってないから:)
面白いのは、AIが書く論文はどうも人間向けには書かれていないらしいということ。専門家でさえ理解に苦労している。でも別のAIなら理解できる。つまりAIは基本的に他のAIのために論文を書いているわけだ。
＞＞9
こういうやり方の強化学習では、AIは文字通り「自分自身に向けて、最も効率よく解にたどり着けるように書く」ことを学習させられている。文章をある程度自然に保つための追加のファインチューニングもされているとは思うけど、それでもね。
こういうやり方の強化学習では、AIは文字通り「自分自身に向けて、最も効率よく解にたどり着けるように書く」ことを学習させられている。文章をある程度自然に保つための追加のファインチューニングもされているとは思うけど、それでもね。
問題は、自分のCPUの整数乗算命令をそのまま使うべきか、それともCで自分で書くべきかということ。ハードウェアの方がまだ勝つと思う。でも将来のCPUのALU設計には影響するんだろうか?
＞＞14
いいえ。ここで数学者が扱っている整数は、計算を考えること自体が意味をなさないレベルで巨大なものです。
いいえ。ここで数学者が扱っている整数は、計算を考えること自体が意味をなさないレベルで巨大なものです。
＞詳細の大部分は確認していないが、主張されているo(n log n)という評価は妥当だと思う。
その一文を読んだ時点で読むのをやめた。なんでこれがHNでこんなに上位に来てるんだ? 実質何も言ってないじゃないか。
その一文を読んだ時点で読むのをやめた。なんでこれがHNでこんなに上位に来てるんだ? 実質何も言ってないじゃないか。
＞＞16
それは、ほぼ自律的に生成されたこうした数学・科学のブレークスルーを、トップクラスの専門家が個人としてどれくらい早く理解・検証できるかを示す興味深いケーススタディだからだよ。今回の場合、整数乗算アルゴリズムの世界的権威が2週間かけても、生成された論文のごく一部しか理解できていない。
それは、ほぼ自律的に生成されたこうした数学・科学のブレークスルーを、トップクラスの専門家が個人としてどれくらい早く理解・検証できるかを示す興味深いケーススタディだからだよ。今回の場合、整数乗算アルゴリズムの世界的権威が2週間かけても、生成された論文のごく一部しか理解できていない。
＞エグゼクティブサマリー(長いバージョン)
＞結論として、主張されている結果は妥当だと思う。ただ実際には論文を読んでいない。
＞結論として、主張されている結果は妥当だと思う。ただ実際には論文を読んでいない。
筆者はAIについての考え方に同意しているからZvi Mowshowitzを読んでいると言っている。誰か手短な要約か、雰囲気をつかめる良い記事を知らない?
いいドメインだな、UNSW! web.maths.unsw.edu.au、モバイルだとアドレスバーを丸々埋めてる。
＞＞3
AIが書いたコードベースでも同じことが起きてる。AIが書いたコードを自分で読むんじゃなくて、AIに説明してもらうわけだ。かといって、それが健全な状態とも言えないけど…
AIが書いたコードベースでも同じことが起きてる。AIが書いたコードを自分で読むんじゃなくて、AIに説明してもらうわけだ。かといって、それが健全な状態とも言えないけど…
＞＞3
なんでダメなんだ? その分野の数学者が論文を理解できなくても、手元の道具なら理解できるなら、使えばいいじゃないか。それのどこが「不健全」なんだ? 今の世界の現実というだけに見えるけど。
なんでダメなんだ? その分野の数学者が論文を理解できなくても、手元の道具なら理解できるなら、使えばいいじゃないか。それのどこが「不健全」なんだ? 今の世界の現実というだけに見えるけど。
＞＞24
面白い見方だな?? 数学や他の純粋科学は人間の理解のためにあるものだ。人間の理解のためのものを人間が理解できなくなっても、それでいいと言ってるのか? それって「世界中の食べ物が全部食べられなくなったけど、ミキサーなら摂取できるからそれでいい」と言っているようなものだぞ。
面白い見方だな?? 数学や他の純粋科学は人間の理解のためにあるものだ。人間の理解のためのものを人間が理解できなくなっても、それでいいと言ってるのか? それって「世界中の食べ物が全部食べられなくなったけど、ミキサーなら摂取できるからそれでいい」と言っているようなものだぞ。
＞＞24
＞なんでダメなんだ? その分野の数学者が論文を理解できなくても、手元の道具なら理解できるなら(…)
それ、どうやって分かるんだ?
＞なんでダメなんだ? その分野の数学者が論文を理解できなくても、手元の道具なら理解できるなら(…)
それ、どうやって分かるんだ?
＞＞24
なぜなら、その「道具」自体も論文を理解していないから。分かっている事実はこうだ:
1. これらの道具はかなりの割合で間違える
2. ある複雑さを超えると崩れ始める上限がある
AIにAIの論文をチェックさせるのは、ひどいアイデアだ。
なぜなら、その「道具」自体も論文を理解していないから。分かっている事実はこうだ:
1. これらの道具はかなりの割合で間違える
2. ある複雑さを超えると崩れ始める上限がある
AIにAIの論文をチェックさせるのは、ひどいアイデアだ。
＞＞3
＞これは健全な状態とは思えない
まさに時代の空気を言い当てたね、友よ。
＞これは健全な状態とは思えない
まさに時代の空気を言い当てたね、友よ。
＞＞3
これは誰も予想していなかった難問だな。機械が人間の知性を超えて数学や物理学を押し進める時代が来るだろう。でも、まさにその理由によって、それが正しいかどうかを私たちは知ることができなくなる!
これは誰も予想していなかった難問だな。機械が人間の知性を超えて数学や物理学を押し進める時代が来るだろう。でも、まさにその理由によって、それが正しいかどうかを私たちは知ることができなくなる!
＞＞28
数学が突然、生物学になる。
数学が突然、生物学になる。
＞＞4
モデルは間違えるのか? それとも、すごく汚いコードベースを完全に理解しようとするのを単に諦めているだけなのか?
モデルは間違えるのか? それとも、すごく汚いコードベースを完全に理解しようとするのを単に諦めているだけなのか?
＞＞6
おおまかに言うと、O(n log n) は「ある k について k(n log n) より速く増えない」という意味で、o(n log n) は「任意の k について k(n log n) より厳密に遅く増える」という意味です。
おおまかに言うと、O(n log n) は「ある k について k(n log n) より速く増えない」という意味で、o(n log n) は「任意の k について k(n log n) より厳密に遅く増える」という意味です。
＞＞6
ありがとう、直した。(ああ、コピペのせいか。)
ありがとう、直した。(ああ、コピペのせいか。)
他サイトの新着
＞＞8
数学の天才である必要はない。論文をAIにアップロードして「5歳児に説明するように教えて」と頼めばいい。あとは質問を重ねるごとに、想定させる年齢や専門レベルを上げていけばいい。
数学の天才である必要はない。論文をAIにアップロードして「5歳児に説明するように教えて」と頼めばいい。あとは質問を重ねるごとに、想定させる年齢や専門レベルを上げていけばいい。
＞＞34
そのアルゴリズムはすぐには収束しないよ。前処理(つまり、見習い程度の魔法くらいは必要)があると助かる。
そのアルゴリズムはすぐには収束しないよ。前処理(つまり、見習い程度の魔法くらいは必要)があると助かる。
＞＞22
その博士号を「詐称している」存在が、ここ数ヶ月で史上の誰よりも実証可能な進歩を数学にもたらしたと想像してみてほしい。それを踏まえると、その議論の結論も少し変わってくると思う。
その博士号を「詐称している」存在が、ここ数ヶ月で史上の誰よりも実証可能な進歩を数学にもたらしたと想像してみてほしい。それを踏まえると、その議論の結論も少し変わってくると思う。
＞＞45
あるいは、その「詐称者」がLeanのあるコンポーネントの健全性バグを見つけて、それを突いただけかもしれない。人間がその証明を理解できない以上、本当のところは誰にも分からない。
あるいは、その「詐称者」がLeanのあるコンポーネントの健全性バグを見つけて、それを突いただけかもしれない。人間がその証明を理解できない以上、本当のところは誰にも分からない。
＞＞45
もっと現実的に言えば、その「詐称者」は大量の出力を作り出していて、その中から正しいものだけが選ばれて公表されている(あと、特に興味深い間違った答えがいくつか混じっているだけ)というのが実際のところだろう。
もっと現実的に言えば、その「詐称者」は大量の出力を作り出していて、その中から正しいものだけが選ばれて公表されている(あと、特に興味深い間違った答えがいくつか混じっているだけ)というのが実際のところだろう。
＞＞45
OpenAIが、これまでの人間の誰よりも数学を前進させたなんて本気で思ってるのか? いやいや。ガロアは20歳で死ぬ前に現代代数学を築き上げたんだぞ。AIエージェントがこれまでやったことなんて、一瞬の花火みたいなものだ。
OpenAIが、これまでの人間の誰よりも数学を前進させたなんて本気で思ってるのか? いやいや。ガロアは20歳で死ぬ前に現代代数学を築き上げたんだぞ。AIエージェントがこれまでやったことなんて、一瞬の花火みたいなものだ。
＞＞32
Big O は基本的に係数を無視する。O(2n+1) = O(2n) = O(n)、o(2n+1) > o(2n) > o(n)。どちらも上限を定義するものだけど、Big Oは「この関数はおおよそ___に比例する」、little oは「この関数は決して_____を超えない」というように読み替えられる。
Big O は基本的に係数を無視する。O(2n+1) = O(2n) = O(n)、o(2n+1) > o(2n) > o(n)。どちらも上限を定義するものだけど、Big Oは「この関数はおおよそ___に比例する」、little oは「この関数は決して_____を超えない」というように読み替えられる。
＞＞63
俺が知ってる定義とは違うな…(CLRSのアルゴリズムの教科書より)。Big Oは「<=」みたいなもので、little oは「<」みたいなものだ。https://dl.acm.org/doi/10.1145/1008328.1008329
俺が知ってる定義とは違うな…(CLRSのアルゴリズムの教科書より)。Big Oは「<=」みたいなもので、little oは「<」みたいなものだ。https://dl.acm.org/doi/10.1145/1008328.1008329
＞＞32
fがO(g)かつo(h)であれば、lim f/g → C(定数)、かつ lim f/h → 0 になる。
fがO(g)かつo(h)であれば、lim f/g → C(定数)、かつ lim f/h → 0 になる。
＞＞64
＞lim f/g → C(定数)
これは正確ではない。O(g)は極限が存在することを要求しない。
＞lim f/g → C(定数)
これは正確ではない。O(g)は極限が存在することを要求しない。
＞＞64
笑った! big Oとlittle oの違いを聞いてる人に対して、それは絶対に分かりやすい説明の仕方じゃないよ。ジョークだったなら、まんまと一本取られたかもしれない。
笑った! big Oとlittle oの違いを聞いてる人に対して、それは絶対に分かりやすい説明の仕方じゃないよ。ジョークだったなら、まんまと一本取られたかもしれない。
この話題の背景と論点
整数の掛け算は昔からFFTを使えばO(n log n)の時間で計算できることが分かっていたが、スレの指摘にあるように今回の論文はそれよりも厳密に小さい上界(o(n log n))を主張している点が核心で、単なる表記の揺れではない。繰り返し出てくるBig OとLittle oの違いを問う質問は、この前提を共有していない読者が多かったことの表れだ。もう一つの論点は、専門家が2週間かけても論文の一部しか検証できていないという状況で、これは証明の自動検証(Lean形式化など)の重要性が増していることを示唆する。AIが生成した結果をAIに検証させる構図への懸念も語られているが、記事内のレスだけでは論文自体がAI生成かどうかは確定していない。
※本記事は海外掲示板 Hacker News のスレッド「The recently proposed o(n log n) integer multiplication algorithm [pdf]」から抜粋し、編集部で日本語に意訳したものです。訳文の責任は当サイトにあります。
この記事のリアクション
まだコメントはありません。