HN 日本語サマリー

← 一覧へ戻る
科学・技術

整数乗算境界のκ = 0.00300105が達成されました

Κ = 0.003 for integer multiplication crossed (github.com)

31 pointsby aleph_minus_one18 コメント

要約

このプルリクエストは、整数乗算の計算複雑性に関する理論的な境界を改善するものです。query thinning(クエリの間引き)とhelper retiming(ヘルパーの再タイミング)を組み合わせることで、計算複雑性定数κを0.00300105まで引き上げました。この改善は、以前のバージョンと比較して計算コストを削減し、アルゴリズムの効率を高めることを目的としています。

全文翻訳

条件付き κ = 0.00300105 (+#4440 より 4.105e-5): クエリの間引きとヘルパーの再タイミングを組み合わせる - #4441

検証済みのfresh-helper retimingを、#4440のp17 query-thinned complex controllerの19個のフルネイティブコールすべてに適用します。16個の有料クエリシェア、アイドルコール全体、メインオペレーター、およびより強力なBITサプライヤーはすべて保持されます。結果として得られる著者チェック済みの条件付き境界は

T(n) = O(n (log n)^(1 - 0.00300105)).

これはκを#4440の0.00296より0.00004105 (+1.3868%)、#4416の0.00268647より11.7098%、そしてピン留めされた選択された0.0023より30.4804%引き上げます。

完全な変更された構造
  • 独立した生産フィールドは11,560のままです。
  • 有料コールは72,902 → 69,273に減少し、3,629を節約しました。
  • 生産/有料ランクのマスは260,798 / 259,998になり、800の余剰を維持しています。
  • 各フルネイティブユニットは、正確な117エントランス、42エグジット、395スカラーフレームパッチを使用します。両方の向きで、すべてのメインオペレーター、スカラー順序/係数、ワープコンタクト、および所有センターが保持されます。
  • 正確な間隔は0.0030010541830 < fixed-profile root < 0.0030010541834を与えます。間隔証明は、すべての実数0<C<1をカバーします。宣言されたκは約4.18e-9のヘッドルームを残します。

新しいモーメントには、修理された有料テール制限が必要です: gamma < 97/100; #4440の31/32はこの変更されたプロファイルでは失敗します。テストされた節約0.003001052、パワー1024、カットオフ20^1024、およびターゲットフロア21^1024で、元のすべてのテールと完了テールを支払います。PR4433の一般化された対数メジャー剤(パワー1000)は、十分な均一ランク2^165315500000000を指定します。巨大な単語は、具体化されたものではなく、アルゴリズムのままです。

より強力なBIT構造は変更されていません: 通常の入場0.0034、アトムパワー0.004。9つのすべての外部行、54の現在の述語、および4つの機能ガードが合格します。拡大されたローカルスカラー/ルート定数は、完全な生の非再帰予算に適合します。

結合パッケージREADME、証明、および#4440の監査から開始してください。

ソースと検証境界

要求された20分間のフロンティアチェックで、より強力な#4440が実行中に発見されました。その正確なヘッド40e22a8は監査され、登録されたリプレイはコンポジション前に合格しました。その変更されていない先行者は、実際の公開祖先に含まれています。ヘルパーユニットは、このPRのオリジナルccdae89にピン留めされています。それらのソースファイルは変更されていません。

通常の結合されたCPython 3.12.15登録リプレイは合格しました。新しいイベントレベルの請求書、2エンジンモーメントチェック、シーリング、有料テール、コンパイラ、スカラー/ルート、およびフルコンシューマーチェックを新たに実行する前に、両方の完全なソース検証を実行します。ネイティブ依存関係チェックは、両方の向きと632個の任意の入力列すべてを、2つの保持されたインタープリター、320個の正確なフェーズ/境界レコード、およびミューテーションコントロールでチェックします。公開されたオプションのC++20オプティマイザーは、ヘルパーパッチを正確に再生成します。コミットバイト/ソース履歴のプリフライトチェックは5f9d871で合格しました。

最初にホストされたプランccdae89は、4つの既存の選択ステータナビゲーションテストで停止しました。このブランチは、選択されたκ=0.0023を保持しながら、最小限の2ドキュメントナビゲーション修理を行います。ターゲットとされた6つのナビゲーション/ロケールテストすべてが合格します。結合された50ファイルGitフリーエクスポートリプレイは合格します。最終ヘッドホストプランニングと、fresh-helper-thinned、fresh-helper-boundary、およびquery-thinned-controllersの科学ジョブはすべて合格します(ワークフロー証拠)。全体的なCIは、3つのアーカイブされたソースピンチェックで赤のままです: historical-1042-link、test-suite-locale-reads、およびd8-mixed-target-seeda97c8e。ハッシュ比較は、それらの期待されるソースがすでにアップストリーム2a13eb1と異なっていることを確認します。それらの凍結された入力は、受け入れを強制するために書き直されていません。20:42 UTCの最後のフロンティアチェックでは、より強力な新しいカッパの主張は見つかりませんでした。

これは著者チェック済みの条件付き構造で、レビュー待ちです。オールカラム/ネイティブ、許可された物理的移動と全体ジョブマッチング、所有者消去、有限テンプレート精度、解析分解、固定テープ、プライム、およびリカバリ契約は前提条件のままです。選択されたフロンティアの変更、無条件の定理、実用的なランタイムの主張、グローバルオプティマム、またはフォーマル/独立した人間の受け入れは主張されていません。

クレジット: #4440のクエリ間引き、より強力なBIT、および所有クエリ構造。zxvのネイティブ/コントローラーおよび高次モーメント/対数コンパイラ作業。Jacob Alan Sussmanの混合フロー。#4416の有料完了構造。および保持されたネイティブ、クリフォード、BIT、精度、および外部貢献者。新しいヘルパーリタイミングと結合構造は、@1337isnot1337のために、OpenAI Codexの多大な支援を受けてApache-2.0ライセンスで準備されました。すべての先行通知は保持されます。サブエージェントはありません。