HN 日本語サマリー

← 一覧へ戻る
プログラミング

Apache DataSketches における Kevin J. Lang の失われた OCaml コードのリバースエンジニアリング

Reverse-Engineering Kevin J. Lang's Lost OCaml Code in Apache DataSketches (tisonkun.io)

38 pointsby tison2 コメント

要約

この記事は、Apache DataSketches の CPC スケッチ実装における、故 Kevin J. Lang 氏の失われた OCaml コードをリバースエンジニアリングするプロセスを詳述しています。著者は、AI モデル(Gemini 4 Carbon, Claude Opus 5.5, GPT 6 Astra)を活用し、数値的フォレンジックと敵対的レビューを通じて、失われたルックアップテーブルや数式を再構築しました。この作業は、失われたコードの正確な動作を理解し、それを現代の Rust 実装に統合するために行われました。

全文翻訳

Apache DataSketches における Kevin J. Lang の失われた OCaml コードのリバースエンジニアリング

ScopeDB の通常の機能から始まりました。近似ユニークカウントのための approx_count_distinct の実装です。

HyperLogLog (HLL) は標準的な教科書的な選択肢です。初期の頃、Rust の HLL エコシステムはまだ成熟していなかったため、Cloudflare のオープンソース cardinality-estimator から始めました。しかし、そのクレートは unsafe コードと手動のビットパッキングトリックに大きく依存していたため、監査可能で管理下に置くために、ScopeDB 内に内部コピーをフォークして保守しました。

代替案を評価する中で、Apache DataSketches を見つけました。これは、実績のある HllSketch に加えて、さらにスペース効率の高い設計である CpcSketch を提供していました。当時、Apache DataSketches は Java と C++ の実装のみを提供していましたが、ScopeDB は Rust で書かれています。

結果として、Apache DataSketches コミュニティは公式の Rust ポートに興味を持ちました。昨年末から、私はスケッチアルゴリズムに精通した数名の Rust 開発者とチームを組み、HllSketch から始まる datasketches-rust の初期リリースを構築・出荷しました。その後すぐに、ScopeDB のユニークカウントを datasketches-rust 実装に切り替えました。

[画像: Apache DataSketches Rust Contributors]

Apache DataSketches Rust Contributors

ストリーミングユニークカウントを実装したことがある人なら誰でも HLL の仕組みを知っています。要素は KK バケットにハッシュされ、各バケットはこれまでに見られた最大先行ゼロカウント(通常 4〜6 ビット)のみを保持し、そのバケットの他のすべてのヒットは記録されません。HLL が密モードに入ると、各バケットは固定幅レジスタを維持します。

2017 年の論文 Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm で、Yahoo! Research の科学者 Kevin J. Lang は基本に立ち返ることを提案しました。バケットごとの最大値のみを保持するのではなく、古典的な FM85 クーポンコレクタープロセスの完全な K×64K \times 64 ビット行列を保持します。行 rr が cc 個の先行ゼロを持つハッシュを見たときに、ビット (r,c)(r, c) を 11 に設定します。完全な二次元ヒット行列を保持することで、CPC はストリーミング HIP 推定器とマージ可能な ICON 推定器をペアにして、HLL よりも高い統計的効率を実現できます。シリアライゼーションでは、密度に合わせてレイアウトを調整します。低カーディナリティは PairTable の (row, column) ペアのスパース表現を使用し、中程度および高カーディナリティは、スライディング 8 ビットウィンドウ、長さ制限ハフマンコーディング、および列順列を組み合わせて、スケッチを情報理論的エントロピー限界近くにパックします。DataSketches のドキュメントによると、シリアライズされた CPC は、同等の精度で HLL と比較してストレージを 30% から 40% 削減します。

1 月下旬、私は CpcSketch を datasketches-rust (PR-75) にポートし、ScopeDB をそれに切り替えました。これは 6 か月以上本番環境でスムーズに稼働しています。

[画像: https://github.com/apache/datasketches-rust/pull/75]

https://github.com/apache/datasketches-rust/pull/75

しかし、CpcSketch をアップストリームの C++ および Java 実装からポートする際に、ソースコード内にハードコーディングされたマジックルックアップテーブルがいくつかあることに気づきました。

  1. 23 個の静的なハフマンエンコーディングテーブル
  2. 16 個のスライディングウィンドウ列順列
  3. 23 セットの次数 19 の多項式補正係数
  4. 4 つの実証的な信頼区間分位点テーブル

これらの 4 つの静的テーブルのセットは、compression_data.rs および estimator.rs にあります。以下はその短い抜粋です。

// datasketches/src/cpc/compression_data.rspub static LENGTH_LIMITED_UNARY_ENCODING_TABLE65: [u16; 65] = [    // entropy:    2.0    // avg_length: 2.0249023437500000000; max_length = 12; num_symbols = 65    0x1000, 0x2001, 0x3003, 0x4007, // ...];pub static COLUMN_PERMUTATIONS_FOR_ENCODING: [[u8; 56]; 16] = [    [0, 1, 2, 3, 5, 6, 7, 8, /* ... */ 54, 55, 34, 14, 4],    // ...];pub static ENCODING_TABLES_FOR_HIGH_ENTROPY_BYTE: [[u16; 256]; 22] = [    // entropy:    4.4619200780464778333    // avg_length: 4.5415773046232610355; max_length = 12; num_symbols = 256    [0x9017, 0x5009, 0x7033, 0x3002, /* ... */],    // ...];// datasketches/src/cpc/estimator.rsstatic ICON_POLYNOMIAL_COEFFICIENTS: [f64; ICON_TABLE_SIZE] = [    // log K = 4    0.9895027971889700513, 0.3319496644645180128, 0.1242818722715769986, // ...];static ICON_LOW_SIDE_DATA: [u16; 33] = [    //1,  2,    3,   kappa    6037, 5720, 5328, // 4 1000000    // ...];static ICON_HIGH_SIDE_DATA: [u16; 33] = [ /* ... */ ];static HIP_LOW_SIDE_DATA: [u16; 33] = [ /* ... */ ];static HIP_HIGH_SIDE_DATA: [u16; 33] = [ /* ... */ ];

ルックアップテーブルをポートする際には、常に単体テストで第一原理から値を導出し、静的配列と比較して要素ごとにチェックすることを好みます。例えば kxp_byte_lookup については、テストスイートの中に導出をそのまま残しました。

for byte in 0u8..=255 {
    // expected value
    let expected = KXP_BYTE_TABLE[byte as usize];
    // computed value
    let mut computed = 0.0;
    for col in 0..8 {
        let bit = (byte >> col) & 1;
        if bit == 0 {
            // note the inverted logic
            computed += inv_pow2(col + 1); //note the "+1"
        }
    }
    assert_eq!(expected, computed);
}

しかし、CompressionData および ICON 推定テーブルについては、リポジトリのどこにもジェネレーターソースが存在しなかったため、当時は自分で導出する方法がありませんでした。アップストリームのコメントには、2 つのビルドコマンドだけが残っていました。

~/ocaml-4.03.0/bin/ocamlopt -o generateHuffmanCodes columnProbabilities.ml generateHuffmanCodes.ml./generateHuffmanCodes > raw-encoding-tables.c

Apache DataSketches のすべてのリポジトリを検索しましたが、それらの .ml ファイルは見つかりませんでした。そこで、ジェネレーターソースがどこにあるかを尋ねるために、datasketches-java に ISSUE-720 を開きました。Lee Rhodes は次のように返信しました。

Kevin は彼の数学シミュレーションとモデリングのほとんどを OCaml で行いました。そして彼のコードは彼のコンピュータ上にありましたが、それはもはや存在しません。そして彼の個人的なコードは彼と共に失われました…たとえ彼の古いコンピュータのコピーがあったとしても、それは干し草の中から針を探すようなものかもしれません。

Kevin は 2019 年 4 月に亡くなり、彼の個人マシンに残されたコードは事実上歴史から失われています。

それを聞いて悲しくなりました。Kevin のスケッチアルゴリズムの研究は、Apache DataSketches の多くのコアスケッチの基盤となっています。

それでも、ランタイムデコーダーと詳細なヘッダーコメントがソースファイルにそのまま存在していたため、成果物だけからオフラインジェネレーターをリバースエンジニアリングすることは可能に思えました。Lee に CPC の論文がテーブルがどのように導出されたかを説明しているか尋ねたところ、彼は次のように答えました。

論文は絶対に読むべきです。しかし、ハフマンコーディングの詳細までは教えてくれません。私の記憶が正しければ、彼の論文では、より標準的な圧縮スキームを使用しました。彼は論文を終えた後にコードの作業を終えましたが、その過程で、論文で議論したものよりもはるかに効率的な、修正ハフマンコーディングのアイデアを思いつきました。

これにより、導出は私が午後に自分で理解できる範囲をはるかに超えていました。

CpcSketch は、ルックアップ配列が忠実にコピーされている限り datasketches-rust で問題なく動作したため、一時的にその謎はそのままにしておきました。

次に、私が datasketches-rust の次のリリースを準備しているときに、Gemini 4 Carbon が登場しました。チェックインされたテーブルと 20 桁のヘッダーコメントはすでに厳密な数値オラクルとして機能していたため、候補となるジェネレーターはコード内で即座にテストできました。つまり、すべてのコードワード、順列エントリ、および IEEE-754 精度の浮動小数点診断を再現するか、間違っているかのどちらかでした。これにより、問題は実行可能なチェックと敵対的レビューを中心に構築されたエージェントワークフローに適したものになりました。

数回のイテレーションを経て、私は 3 つのモデルをそのオラクルおよび互いに競合させました。

  1. 初期合成 (Gemini 4 Carbon): 静的配列とソースコメントから開始し、実行可能なプローブを作成し、最初の構築的テストハーネスを構築しました。ハフマンコードワードと列順列をビット単位で再現し、ICON 多項式を同等の精度に適合させました。
  2. 数学的偽造 (Claude Opus 5.5): 初期主張を破るように指示され、制御されたアブレーションを実行して、初期の「左端切り捨て」説明を反証し、f64 のキャンセルを検出するトラップを分離し、多項式適合が識別できなくなる場所をマッピングし、百万回のモンテカルロ統計を再実行しました。
  3. 変異と分析監査 (GPT 6 Astra): テストと導出の両方を監査し、変異テストを使用して 2 つのトートロジー的なアサーションを露呈させ、以前のドラフトのいくつかの数学的な誇張を捉え、漸近指数定数の末尾の桁に一致する閉形式の表現を導出しました。

どのモデルも最初の試みで全てを正しく行うことはなく、いくつかのもっともらしい説明は、コードでの摂動をテストした途端に崩壊しました。そのフィルターを生き残ったものが、再構築されたジェネレーターと導出を単体テストとして datasketches-rust にチェックインする PR-355 となりました。これは、kxp_byte_lookup で採用したアプローチと同じアプローチに従っています。

[画像: https://github.com/apache/datasketches-rust/pull/355]

https://github.com/apache/datasketches-rust/pull/355

この記事の残りの部分では、これらの 4 つのテーブルセットの背後にある数学と数値フォレンジックに焦点を当てます。各構造がどのように機能するか、どの間違った方向が説得力があったか、そして生き残った成果物が 2 つのモデルを区別できない場所について説明します。形式的な導出は末尾の付録にあります。もし誤りを見つけた場合は、コメントを残すか、datasketches-rust に PR を開いてください。

離散コードワードの盲点と 20 桁のフィンガープリント

まず、compression_data.rs にある 23 個のハフマンコーディングテーブルから始めます。

なぜ静的なハフマンテーブルが 23 個もハードコーディングされているのでしょうか? スケッチごとに動的にツリーを構築すると、シリアライザーはツリーヘッダーを圧縮ストリームに書き込む必要が生じ、小さなスケッチで節約された数十バイトが無駄になります。一方、クーポン行列の列 jj がセットされる確率(ビットが 1 になる確率)は、主に充填率 C/KC / K(収集されたクーポン CC を行数 KK で割ったもの)に依存します。有限 KK の補正は、1/K1 / K の次数でしか入ってこない、これは以下の重要な手がかりとなるわずかな違いです。代表的な C/KC / K のチェックポイント全体で最適なテーブルを事前に計算することで、determine_pseudo_phase はテーブル ID を保存することなく、lg_k と num_coupons からのみ正しいテーブルを選択できます。

最初の 22 個のテーブルは 8 ビットスライディングウィンドウバイト(00 から 255255)をエンコードします。8 つの隣接する列の列ごとのビット確率を q0q_0 から q7q_7(これらは独立していると見なされる)とすると、バイト bb の理論的確率は 8 つのベルヌーイ項の積に等しくなります。ビット dd が 11 なら qdq_d、00 なら 1−qd1 - q_d です。

アップストリームデコーダーは 212
=40962^{12} = 4096 エントリのルックアップテーブルを使用しており、コードワード長に 12 ビットのハードキャップがあることがすぐにわかります。バイト確率を Larmore と Hirschberg の 1990 年の Package-Merge アルゴリズム に入力すると、長さ制限付きコード長が得られます。長さとシンボル値でソートされたカノニカルコードワードを割り当て、各コードワードを CPC の LSB ファーストビットストリームのためにビット反転すると、23 テーブルすべてにわたる 5,697 個のコードワードがビット単位で再現されます。

次の質問は、columnProbabilities.ml が列 jj に対して実際に使用したオキュパンシーモデルは何かということです。

  1. 有限 KK 二項モデル: 各アイテムは単一試行確率 pj
    =1/(K⋅2j)p_j = 1 / (K \cdot 2^j) で列 jj にヒットし、NN 回の挿入後、q
    =1−(1−pj)Nq = 1 - (1 - p_j)^N となります。
  2. 無限 KK ポアソン極限: K→∞K \to \infty で固定密度 N/K
    =λN / K = \lambda とすると、オキュパンシーは q
    =1−exp⁡(−λ/2j)q = 1 - \exp(-\lambda / 2^j) に収束します。

整数コードワードだけを比較すると、盲点に突き当たります。6 つの中間レンジテーブル(配列インデックス 16..21)全体で、KK を 2162^{16} から無限大までスイープしても、全く同じ 256 個のコードワードが得られます。ハフマン長は離散的なステップ関数であるため、確率のわずかなシフトはツリーのマージ決定をめったに反転させません。

実際に連続的なフィンガープリントとして機能し、KK を特定するのは、generateHuffmanCodes.ml が各テーブルの上に印刷した 20 桁の浮動小数点コメントです。テーブル 16(最初の中間レンジバイトテーブル)を見てみましょう。

// entropy:    2.1627885076675394949// avg_length: 2.2704182849800043087; max_length = 12; num_symbols = 256

シャノンエントロピー H
=−∑P(b)log⁡2P(b)H = -\sum P(b) \log_2 P(b) と平均コード長 ∑P(b)Lb\sum P(b) L_b は、基になる分布とともに連続的に変化します。C/KC / K のチェックポイントを固定したまま、22 個のバイトテーブルすべてで KK を 2282^{28} から無限大までスイープしました。6 つの中間レンジテーブルにおける最悪ケースのエラーは次のとおりです。

候補パラメータ KK最大エントロピー誤差 max⁡∣ΔH∣\max \lvert \Delta H \rvert最大平均コード長誤差
K
=228K = 2^{28}7.38×10−107.38 \times 10^{-10}7.25×10−107.25 \times 10^{-10}
K
=230K = 2^{30}1.48×10−101.48 \times 10^{-10}1.45×10−101.45 \times 10^{-10}
K
=231K = 2^{31}4.92×10−114.92 \times 10^{-11}4.84×10−114.84 \times 10^{-11}
**K
=232K = 2^{32}**6.22×10−156.22 \times 10^{-15}6.22×10−156.22 \times 10^{-15}
K
=233K = 2^{33}2.46×10−112.46 \times 10^{-11}2.42×10−112.42 \times 10^{-11}
K
=234K = 2^{34}3.69×10−113.69 \times 10^{-11}3.63×10−113.63 \times 10^{-11}
K→∞K \to \infty (Poisson)4.92×10−114.92 \times 10^{-11}4.84×10−114.84 \times 10^{-11}

K
=232K = 2^{32} では、残差が 4 オーダーも低下し、IEEE-754 倍精度浮動小数点演算の丸めノイズレベルになります。

あの表のクリーンな対称性を見てください。K
=231K = 2^{31} は K→∞K \to \infty と全く同じ誤差を生成し、K
=233K = 2^{33} はその半分の誤差になります。これは、第一近似では、有限 KK がポアソン極限から外れる度合いが 1/K1 / K に比例するためです(最初の付録セクションで導出)。真のパラメータが K0
=232K_0 = 2^{32} の場合、2312^{31} と ∞\infty の両方が 1/K1 / K 軸上で 1/2321 / 2^{32} の 1 ステップ離れた位置にあり、一方 2332^{33} は半ステップ離れた位置にあります。適合するように、アップストリーム ICON 推定器のコメントにも、テーブルの最大行数が 2322^{32} スロットであることが示されています。

定常状態テーブル:「左端切り捨て」の幻影

次に、16 個の定常状態テーブルに進みます。これらは、充填率 C/K
=B+phaseC / K = B + \text{phase} でのフェーズ phase
=(2m+1)/32\text{phase} = (2m + 1) / 32 をカバーします。私たちは説得力のある偽のリードに遭遇しました。

列順列テーブル(次に説明)は、定常状態の整数ベースラインが B
=6B = 6 であることを確立します。しかし、新しく復元した K
=232K = 2^{32} と B
=6B = 6 を 16 個の定常状態テーブルに代入すると、12 桁目のエントロピー残差が 6.1×10−126.1 \times 10^{-12} になります。

一見すると、「左端切り捨て」が明白な説明に見えます。C/K≈6C / K \approx 6 の周りでは、クーポン行列の列 1 はまだ 100% 飽和しておらず、その 00 の確率は約 5.3×10−125.3 \times 10^{-12} で、残差のオーダーと一致します。確かに、K
=232K = 2^{32} を固定し、動作点を B
=32B = 32 (C/K
=32+phaseC / K = 32 + \text{phase}) まで外挿すると、エントロピー誤差は 10−1510^{-15} に低下します。すべてが桁数オーダーで一致しているように見えました。

2 つの制御されたアブレーションにより、その仮説はすぐに却下されました。

  1. B
    =6B = 6 を固定したまま、K
    =232K = 2^{32} 二項モデルから K→∞K \to \infty ポアソン極限に切り替えると、16 個の定常状態テーブルすべてで誤差が約 10−14\sim 10^{-14} に低下し、倍精度浮動小数点演算の丸めノイズレベルになります。
  2. K
    =232K = 2^{32} を固定したまま、B
    =6,7,8B = 6, 7, 8 とステップさせると、最大エントロピー誤差は 6.1×10−126.1 \times 10^{-12}、3.1×10−123.1 \times 10^{-12}、および 1.5×10−121.5 \times 10^{-12} となり、BB の +1+1 ステップごとに半分になります。

なぜ毎回半分になるのでしょうか? BB を 11 増やすと、8 ビットスライディングウィンドウが 1 列右にシフトし、ポアソン極限に対する二項補正が 1/(2K⋅2j)∝2−B/K1 / (2K \cdot 2^j) \propto 2^{-B} / K として減衰します。BB を 3232 にすると左端の切り捨てには何も影響しませんでした。単にウィンドウを列 29 の近くに押し出し、ウィンドウ内の有限 KK 補正 2−29/232
=2−612^{-29} / 2^{32} = 2^{-61} を f64 マシンイプシロンより小さくし、深い列で K→∞K \to \infty ポアソン極限を誤って偽装しました。

左端は実際にどの程度の影響を与えることができるでしょうか? ジェネレーターは、ウィンドウの 1 列目(λ\lambda を介して間接的に入る)を考慮して、128 列すべての期待値について λ\lambda を解きますが、シフト恒等式はその大きさをきれいに制限します。無限列ポアソン期待値 f(λ)
f(\lambda) について、λ\lambda を 2 倍にするとシリーズインデックスが 1 つシフトし、単一の先頭項 1−exp⁡(−λ)1 - \exp(-\lambda) が追加されます。コードで評価される 128 列の合計 f128(λ)
=E[C]/Kf

{128}(\lambda) = E[C] / K については、列 128 で打ち切ることで右端のテール項も差し引かれます。

f128(2λ)
=f128(λ)+(1−e−λ)−(1−e−λ/2128)f

{128}(2\lambda) = f

{128}(\lambda) + \left(1 - e^{-\lambda}\right) - \left(1 - e^{-\lambda / 2^{128}}\right)

つまり、BB を 11 増やすと λ\lambda が 2 倍になり、ウィンドウが 1 列右にシフトし、ウィンドウ内の分布は左端と右端の切り捨て項までほぼシフト不変に保たれます。C/K
=6+1/32C / K = 6 + 1/32 (λ≈51.93\lambda \approx 51.93) では、左端項 exp⁡(−λ)\exp(-\lambda) は約 2.8×10−232.8 \times 10^{-23}(λ\lambda への相対効果は約 2×10−23\sim 2 \times 10^{-23})であり、右端項 1−exp⁡(−λ/2128)1 - \exp(-\lambda / 2^{128}) は約 1.53×10−371.53 \times 10^{-37} です。どちらも 10−1210^{-12} の残差よりも 10 倍以上、20 倍以上下回っています。不一致の原因は左端ではなく、有限 KK でした。

これはまた、明確な識別可能性の境界を描き出します。16 個の定常状態テーブルのみでは、テストの 3×10−143 \times 10^{-14} の許容誤差の下で、ポアソン極限(6≤B≤846 \le B \le 84)と K
=232K = 2^{32} 二項モデル(14≤B≤8414 \le B \le 84)の両方が、許容誤差内でエントロピーと平均長のヘッダーすべてに適合します。それらはビット単位で同一ではありません(まだ約 10−14\sim 10^{-14} 異なります)が、倍精度浮動小数点演算と許容誤差内では区別できません。B
=84B = 84 のすぐ右で、128 列の右端項はすでに指数関数的に約 4.61×10−14\sim 4.61 \times 10^{-14} に増加します。B
=85B = 85 になると、テーブル 7 の平均長誤差は 3.11×10−143.11 \times 10^{-14} に達し、許容誤差を超えます。さらに右に進むと、右端の切り捨てが完全に支配的になり、B
=100B = 100 で 7.4×10−107.4 \times 10^{-10} に達します。私たちは「B
=6B = 6 ポアソン極限」モデルを選択しました。なぜなら、それは列順列の正確な動作点と共有しており、任意の B
=32B = 32 を発明しないからです。ただし、静的テーブルだけでは同等の有限 KK シフト区間を排除することはできません。

列順列:フェーズ 19/32 における丸め誤差のトラップ

定常状態レジームでは、スライディングウィンドウの左側の列はほぼすべて 11 で、右側の列はほぼすべて 00 です。したがって、残りの 56 個のウィンドウ外の列は驚きのビット、つまりウィンドウの左側のゼロまたはウィンドウの右側の 1 のみを格納し、列インデックスの差分でエンコードされます。確率の高い驚きの列を先に配置すると、一項(unary)の差分が短くなり、generatePermutationsForSLIDING.ml の 16 個の 56 バイトテーブルがこれを実現します。

まず、そのインデックス付けスキームです。

  • ウィンドウオフセットを ω
    =⌊C/K−2.375⌋\omega = \lfloor C / K - 2.375 \rfloor とします。物理的な 0 ベースの列 col は、カノニカルインデックス canon = (col + 56 - offset) % 64 にマッピングされ、右側列を先頭にし、ω\omega 個の左側列を末尾に配置します。
  • 56 個のカノニカルスロットは、驚きのビットの確率の降順でランク付けされます。
  • 各静的配列は、ソートされた順序でリストするのではなく、encode_perm[canon] = rank を格納します。

そのレイアウトだけで BB が確定します。最初の 6 つのテーブル(フェーズインデックス 0..5)では、3 つの末尾のスロットがウィンドウの左側の列に対応し、上にインターリーブされます。最後の 10 個のテーブルでは、その数は 4 つに増加します。ω\omega はフェーズ 3/8 で B−3B - 3 から B−2B - 2 にステップするため、3 から 4 へのジャンプは B
=6B = 6 を決定します。候補をテストすると直接確認できます。B
=5,6,7B = 5, 6, 7 は、それぞれ 16 個中 6 個、16 個、10 個のテーブルに適合します。バイトテーブルとは異なり、KK を 282^8 から ∞\infty までスイープしても、16 個の順列テーブルすべてがバイト単位で同一のままです。列順列は KK に完全に無感応です。

B
=6B = 6 が確定すると、微妙な数値トラップが p0p_0、つまりウィンドウの左側の列が 00 のままである確率に潜んでいます。もし 1.0 - q を既に計算された 1 ビット確率 qq から怠惰に計算すると、B
=6B = 6 と B
=7B = 7 の両方が 16 個中 15 個のテーブルに適合しますが、フェーズ 19/32 の単一テーブルで 4 つのエントリを欠落させます。そのフェーズ(ω
=4\omega = 4)では、4 つの末尾スロットを見てみましょう。

カノニカルインデックス canon物理列 (1 ベース)驚きの確率ランク
49621.6630×10−171.6630 \times 10^{-17}53
50638.3150×10−188.3150 \times 10^{-18}54
51644.1575×10−184.1575 \times 10^{-18}55
5212.2211×10−172.2211 \times 10^{-17}52

物理列 1 は、列 62 の 1.66×10−171.66 \times 10^{-17} よりも厳密に大きい驚きの確率 p0
=exp⁡(−λ/2)≈2.22×10−17p_0 = \exp(-\lambda / 2) \approx 2.22 \times 10^{-17} を持ちます。降順確率でソートすると、末尾のカノニカルシーケンスは 48, 52, 49, 50, 51 となり、スライス encode_perm[49..=52] に [53, 54, 55, 52] が配置されます。代わりに 1.0 - q を計算すると、スロット 52 が最後の位置になり、[52, 53, 54, 55] となります。

根本原因は浮動小数点数のキャンセルです。2.22×10−172.22 \times 10^{-17} は IEEE-754 f64 で容易に表現可能ですが(アンダーフローにはほど遠い)、q
=1−p0q = 1 - p_0 は 1.01.0 のすぐ下に位置し、隣接する倍精度浮動小数点数は 2−532^{-53} 間隔になります。最近接偶数丸めでは、p0≤2−54≈5.55×10−17p_0 \le 2^{-54} \approx 5.55 \times 10^{-17} の場合、qq は 1.01.0 に丸められ、減算が行われる前に 1.0 - q は 0.00.0 になり、p0p_0 は完全に消去されます。

指数関数を直接評価する(Rust では (-lambda / 2^j).exp() のような)ことで、壊滅的なキャンセルを回避し、B
=6B = 6 で 16 個の順列テーブルすべてをビット単位で再現します。この単一の比較は、B
=7B = 7 と 1.0 - q の両方を同時に排除しますが、厳密に言えば、Kevin のジェネレーターが 1.0 - q を使用しなかったことを証明するだけで、彼が書いた正確な構文を証明するわけではありません。

次数 19 の多項式と指数定数

次に、estimator.rs の ICON カーディナリティ推定器です。クエリ時に 128 列すべてに対してニュートン法を実行する代わりに、Kevin は 2 つの部分からなる近似を設計しました。

  • C≤5.7KC \le 5.7K(lg_k ≥14\ge 14 では 5.6K5.6K に引き締められる)の場合、立方体先行係数で前処理された次数 19 の多項式を評価します。
  • そのスプライスポイントを超えると、漸近指数公式に切り替わります。

N^poly(K,C)
=C(1+(C/K)366.774757)∑m
=019am(K)(C2K)m\hat{N}

{\text{poly}}(K, C) = C \left(1 + \frac{(C/K)^3}{66.774757}\right) \sum

_{m=0}^{19} a

_m(K) \left(\frac{C}{2K}\right)^m
N^exp(K,C)
=0.7940236163830469⋅K⋅2C/K\hat{N}

{\text{exp}}(K, C) = 0.7940236163830469 \cdot K \cdot 2^{C/K}

1+(C/K)3/66.7747571 + (C / K)^3 / 66.774757 を因数分解することで、多項式のターゲット比率を [0.89,1.48]0.89, 1.48 の範囲に保ちます。N/CN / C が 8×8\times 範囲 [0,6]0, 6 で広がるのを防ぎます。変数 x
=C/(2K)x = C / (2K) をスケーリングすると、[0,6K]0, 6K が [0,3]0, 3 にマッピングされ、x19x^{19} が 319≈1.16×1093^{19} \approx 1.16 \times 10^9 となり、619≈6.09×10146^{19} \approx 6.09 \times 10^{14} ではなくなります。

フィッティング区間と識別可能性

ランタイムが 5.6K5.6K または 5.7K5.7K で分岐を切り替える場合、元の 23 個の多項式はどの範囲でフィッティングされたのでしょうか? チェックインされた多項式をランタイムカットオフを超えて評価すると、明確なパターンが現れます。

  • すべての行は、C
    =6KC = 6K まで 5×10−75 \times 10^{-7} 以内の相対誤差を保持し、6K6K をわずかに超えると急速に発散します。6.25K6.25K になると、エラーはすべてで 4×10−64 \times 10^{-6} から 1.3×10−41.3 \times 10^{-4} の範囲に急増します。
  • lg_k
    =4
    = 4 の場合、崖は非常に鋭いです。C
    =2..96C = 2\text{..}96 の範囲で、最大相対誤差は 8.7×10−88.7 \times 10^{-8} (C
    =95C = 95) で、C
    =96C = 96 で 1.3×10−81.3 \times 10^{-8} に低下し、C
    =97C = 97 で 2 オーダー大きい 2.2×10−62.2 \times 10^{-6} に急増します。
  • しかし、より大きな KK では、単一の整数ステップは C/KC / K をほとんど動かさないため、鋭いブレークが滑らかになります。lg_k
    =8
    = 8 では、C
    =6K+1C = 6K + 1 でのエラーはまだ −6.6×10−8
    -6.6 \times 10^{-8} であり、C
    =6KC = 6K よりもわずかに小さいです。

フィッティングが 6K6K でちょうど停止したという信頼性は、エラーの崖だけでなく、以下の係数回帰に依存しています。5.6K5.6K/5.7K5.7K の閾値をわずかに超えてフィッティングを拡張することは、Runge の境界振動に対するバッファーとして直感的に理にかなっていますが、アップストリームの注釈でその意図を確認したわけではありません。

係数の再構築を試みると、小さいスケッチと大きいスケッチの間に鋭い識別可能性の境界が露呈します。

  • lg_k ≤7\le 7(6K≤7686K \le 768 個の整数点)の場合、C
    =1C = 1 から 6K6K までのすべての整数点
    に対する重みなし最小二乗法は、アップストリーム値の 0.07% から 1.4% の範囲で 20 個の係数すべてを回復します。C
    =1C = 1 を削除するか、いずれかの端点を 11 シフトすると、係数の合意が 4×4\times から 59×59\times 悪化します。これは [1,6K]1, 6K の全整数グリッドを強く支持しますが、詳細は未解決のままです。相対誤差重み付けは lg_k
    =4
    = 4 でわずかに近く適合し、元のソルバーの詳細は失われています。
  • lg_k ≥8\ge 8 の場合、全整数グリッドと境界重み付けグリッドの両方で、係数はアップストリームから 14% から 65% オフになります。ただし、予測値は範囲内では 3×10−73 \times 10^{-7} 以内、スプライスポイントを超えると max⁡(2.5×10−6, 1/(80K))\max(2.5 \times 10^{-6},, 1 / (80K)) 以内に追従します。サンプリングからの高次単項式の係数を回復することは、深刻な条件数不良です。1,6K1, 6K 上のスケールなし次数 19 の Vandermonde 行列は、列正規化後でも約 101710^{17}(lg_k
    =4
    = 4 で 1.19×10171.19 \times 10^{17})の L2L_2 条件数を持っていますが、列正規化後でも約 101410^{14} のままです。ユークリッド空間で大きく離れた 2 つの係数ベクトルは、ほぼ同一の曲線を生み出す可能性があります。
指数分岐の背後にある 3 つの定数

指数定数とアップストリームテストの境界は、純粋な経験的チューニングのように見えました。実際には、3 つすべてがポアソンモデル(付録で導出)から直接導かれます。

  1. 先行定数: 無限列ポアソン期待値の Mellin 変換を取り、s
    =0s = 0 における極の残基を計算すると、E[C]/K
    =log⁡2λ+γ/ln⁡2−1/2+P(log⁡2λ)+R(λ)E[C] / K = \log

_2 \lambda + \gamma / \ln 2 - 1/2 + \mathcal{P}(\log

_2 \lambda) + R(\lambda) が得られます。ここで、P\mathcal{P} は 1 周期であり、R(λ)
=∑exp⁡(−2rλ)R(\lambda) = \sum \exp(-2^r \lambda) は指数分岐(λ≥38.5\lambda \ge 38.5)で 2×10−172 \times 10^{-17} 未満になります。P\mathcal{P} と R R を無視すると、λ≈D⋅2C/K\lambda \approx D \cdot 2^{C/K} となり、閉形式 D
=2 e−γ
=0.7940236163832829…D = \sqrt{2},e^{-\gamma} = 0.7940236163832829\dots となります。これは、ハードコーディングされたランタイム定数とは、13 桁目の約 2.36×10−13\sim 2.36 \times 10^{-13} のみで異なります。
2. ppm の周期的なリップル: 振動級数 P\mathcal{P} は単純極が虚軸上にあることから生じます。その基本調波は、相対振幅 a
=2∣Γ(2πi/ln⁡2)∣≈1.0904×10−6a = 2\lvert\Gamma(2\pi i / \ln 2)\rvert \approx 1.0904 \times 10^{-6} の周期的なリップルを追加し、高 KK で観測される正確な精度フロアを設定します。
3. アップストリームテストで 1 / (80 * K) が使用されている理由: Java の IconEstimatorTest は、エラーバウンド max(2e-6, 1.0 / (80 * k)) を使用します。有限 KK 効果により、ポアソン公式はカーディナリティをわずかに過大評価し、C
=5.7KC = 5.7K (λ≈41.3\lambda \approx 41.3) のスプライスポイントで最大相対バイアス 1/(2Kλ)≈1/(82.6K)1 / (2K\lambda) \approx 1 / (82.6K) に達します。82.682.6 を 8080 に丸めると、約 3% のマージンでそのピークをカバーしますが、Kevin が 80 をこのように選択したかどうかは文書化されていません。

末尾の桁を特定する

D D とランタイム定数との間の 2.36×10−132.36 \times 10^{-13} のギャップには、最後のビットまで驚くほど鮮明な数学的説明があります。AA が、A⋅K⋅2C/KA \cdot K \cdot 2^{C/K} が正確なポアソン逆関数に対する1 周期あたりの相対誤差の平均がゼロになるように選択されたと仮定します。付録の周期平均相対誤差の導出により、AA は次を満たす必要があります。

A
=D⟨e(ln⁡2)P(t)⟩≈D(1−a24)
=D(1−∣Γ ⁣(2πiln⁡2)∣2)
=0.79402361638304686…\begin{aligned} A &= \frac{D}{\left\langle e^{(\ln 2)\mathcal{P}(t)} \right\rangle} \approx D \left(1 - \frac{a^2}{4}\right) \ &= D \left(1 - \left\lvert\Gamma!\left(\frac{2\pi i}{\ln 2}\right)\right\rvert^2\right) = 0.79402361638304686\dots \end{aligned}

⟨e(ln⁡2)P(t)⟩\langle e^{(\ln 2)\mathcal{P}(t)} \rangle を修正ベッセル関数 I0(a)I_0(a) の 2 次展開で置き換えると、〜5×10−26\sim 5 \times 10^{-26} のみ省略され、倍精度よりもはるかに小さくなります。f64 に丸めると、この閉形式は 0.7940236163830469 とビット単位で一致します。私たちの単体テストは、本番定数を実行時に直接クエリし、正確な一致を確認します(および周期全体での数値調和積分に対して 2 ULPs 以内で一致します)。それでも、認識論的な注意点は残ります。最適化基準が定数をビット単位で再現することを示しても、Kevin がその正確な基準を書いたことを証明するわけではありません。

百万回のモンテカルロ試行と離散階段効果

残りの部分は、4 つの信頼区間テーブルです。ICON_{LOW,HIGH}_SIDE_DATA および HIP_{LOW,HIGH}_SIDE_DATA。アップストリームのコメントは、これらが真のカーディナリティ N
=1000KN = 1000K での約 10610^6 回のモンテカルロ試行からの経験的分位点を記録していると述べています。各セルは (104K⋅ε)/κ(10^4 \sqrt{K} \cdot \varepsilon) / \kappa を整数に丸めたものを格納します。ここで、ε\varepsilon は正規分布の片側相対誤差分位点 Φ(−κ)\Phi(-\kappa) に対応します。

確率的テーブルはハフマンコードのようにビット単位で再構築することはできません。独立したシミュレーションに対して統計的にチェックする必要があります。すぐに 2 つの実用的な障害が発生します。1 台のマシンで lg_k
= 4..=14 の各行に対して 10610^6 回の試行を実行する方法、および今日の数値が Kevin の元の整数とこれほど密接に一致する理由です。

lg_k
=14
= 14 (K
=16384K = 16384) で個々の挿入を素朴にシミュレートすると、試行あたり 1.6×1071.6 \times 10^7 ステップ(10610^6 回の試行全体で 1.6×10131.6 \times 10^{13} 回のイテレーション)が必要となり、単一のマシンでは現実的ではありません。私たちの高速シミュレーターは、Kevin が論文の付録 B で概説した指数スキップクーポンプロセスに基づいています。64 個の空セルカウンター mjm_j、実行中の HIP アキュムレータ、および処理済み要素数のみを維持します。1 つの重要な注意点があります。HIP 値は、最終的な列数だけからは再構築できません。なぜなら、HIP は発見順序に厳密に依存するからです。K
=16K = 16 での最小の反例として、列 1 をヒットしてから列 2 をヒットすると 2.0323 になりますが、列 2 をヒットしてから列 1 をヒットすると 2.0159 になります。最終的な列数は同じです。各ステップで、合計の新しいセル確率は phit
=∑mj/(K⋅2j)p
_{\text{hit}} = \sum m_j / (K \cdot 2^j) なので、ヒット間の待機ステップは単一の対数を使用して正確な幾何分布に従い、各ヒットで HIP に 1/phit1 / p
_{\text{hit}} を追加し、mj⋅2−jm_j \cdot 2^{-j} に比例して列 jj をサンプリングします。

1 つの微妙な実装境界も記録しておくべきです。高速シミュレーターは、物理列 64(インデックス 63)に明示的な重み 2−642^{-64} を割り当て、残りのテール質量を吸収する初期 kxp
=K
= K を使用します。一方、sketch.rs は、≥63\ge 63 の先行ゼロを持つすべてのハッシュを列 64(実際のヒット確率 2−632^{-63})に折りたたみますが、kxp から 2−642^{-64} を差し引き、浮動小数点ドリフトを制限するために 8 回のシフトごとに refresh_kxp を呼び出します。したがって、理想的なプロセスとスケッチプロセスが厳密に一致するのは、列 64 がヒットせず、refresh_kxp ドリフトが無視できる範囲に限られます。私たちの実行で 4×10134 \times 10^{13} 回以上のシミュレートされた挿入全体で、期待される列 64 のヒット合計は約 4.5×10−64.5 \times 10^{-6} であり、実際には無関係です。空の描画をスキップすると、試行あたりのコストが O(N)O(N) から O(C)O(C)(N
=1000KN = 1000K で約 10K10K クーポン)に削減され、実行時間が 2 オーダー削減されるため、すべての 11 行(simA で各 10610^6 回の試行)が 14 スレッドで約 11 分で完了しました。

統計的な落とし穴も回避する必要がありました。1 行の 6 つの分位点(−3σ
-3\sigma から +3σ+3\sigma)はすべて同じ 10610^6 回の試行から得られるため、相関しています。単純に二乗されたセルごとの z スコアを χ2\chi^2 分布に対して合計することは無効です。3 回の実行全体で、完全な生の試行ベクトル CC と HIP/N\text{HIP} / N をディスクに保存しました。

  1. simA: すべての 11 行(lg_k
    = 4..=14)にわたる行ごとの 10610^6 回の試行。
  2. 実際の CpcSketch コントロール: lg_k
    = 4..=7 で MurmurHash3 を使用した行ごとの 10610^6 回の試行。各 lg_k に対して独立したストリームシードを使用。
  3. simB: lg_k
    = 4..=12(9 行)にわたる高速シミュレーターの 2 番目の独立したシード。

2 つの独立した方法で、2,000 回のノンパラメトリックブートストラップリサンプリングとSiddiqui の順序統計漸近分散公式を使用して、各行の 6×66 \times 6 分位数共分散行列を推定し、独立した行全体で結合 Mahalanobis T2T^2 統計量を形成しました。

両方の健全性チェックコントロールはきれいに保持され、両方の共分散推定値間で密接に一致しました。

  • 同一シミュレーター null コントロール: simA と simB をすべての 54 個の共有自由度(lg_k
    = 4..=12)で比較すると、ブートストラップ共分散下で T2
    =62.58T^2 = 62.58 (p
    =0.198p = 0.198)、解析的には T2
    =63.77T^2 = 63.77 (p
    =0.171p = 0.171) となり、2 つの独立した 10610^6 回の試行バッチ間の教科書的な一致を示しています。
  • 実際の CpcSketch コントロール: ブートストラップ下で 24 DoF(lg_k
    = 4..=7)で実際のスケッチと simA を比較すると T2
    =36.72T^2 = 36.72 (p
    =0.047p = 0.047)、解析的には T2
    =36.20T^2 = 36.20 (p
    =0.052p = 0.052) となります。simA と simB の平均と比較すると、T2
    =34.65T^2 = 34.65 (p
    =0.074p = 0.074) および T2
    =33.96T^2 = 33.96 (p
    =0.085p = 0.085) となります。24 個のセルすべてで 3σ3\sigma を超えたものはなく、2σ2\sigma を超えたのは 1 つだけでした。系統的なバイアスの兆候は見られませんでした。

Kevin のチェックインされたテーブルと比較すると、ICON と HIP の間に明確な分割が見られました。

  • ICON テーブル: 66 個のセル全体で、simA は Kevin の整数 59 個をそのまま再現し、すべての基になる浮動小数点数は ±0.5\pm 0.5 の丸め区間内にあります。simB では、54 個の共有セル中 51 個がそのまま一致し、アップストリーム、simA、および simB で 49 個の正確な一致が重なっています。
  • HIP テーブル: 行の独立性、一様な 1/121/12 丸め分散、およびアップストリーム試行回数共分散の下で、アップストリーム対 simA は 66 DoF で T2
    =103.97T^2 = 103.97 (p
    =1.99×10−3p = 1.99 \times 10^{-3}、解析的 T2
    =102.27T^2 = 102.27、p
    =2.81×10−3p = 2.81 \times 10^{-3}) となります。アップストリーム対 simB は 54 DoF で T2
    =73.46T^2 = 73.46 (p
    =0.040p = 0.040、解析的 T2
    =73.04T^2 = 73.04、p
    =0.043p = 0.043) となります。アップストリーム対 simA と simB の平均との比較は T2
    =87.29T^2 = 87.29 (p
    =2.77×10−3p = 2.77 \times 10^{-3}、解析的 T2
    =86.36T^2 = 86.36、p
    =3.39×10−3p = 3.39 \times 10^{-3}) となります。信号の大部分は lg_k
    =7,9,11
    = 7, 9, 11 に集中しています。simA では、それらの単一行 pp 値は 5.4×10−35.4 \times 10^{-3}、0.0140.014、および 9.5×10−49.5 \times 10^{-4} であり、11 行全体での Holm 調整 pp 値は 0.0100.010 (lg_k
    =11
    = 11)、0.0540.054 (lg_k
    =7
    = 7)、および 0.130.13 (lg_k
    =9
    = 9) となります。一方、独立した simB では、それらの単一行 pp 値は 0.0920.092、0.0660.066、および 0.1670.167 です。したがって、軽微な全体的な不一致はありますが、行レベルの証拠は、それら 3 行を決定的に特定するには不十分です。絶対的な terms では、66 セルすべてにおける最大の違いはわずか 83.7483.74 テーブルユニット(lg_k
    =9
    = 9 で −3σ
    -3\sigma)であり、エラーファクター ε\varepsilon を最大で 1.49%、片側信頼幅を約 1.61% 変化させます。このシフトは実際には軽微ですが、経験的なカバレッジ率を直接再測定しませんでした。

なぜ確率的 ICON 分位点セルの約 90% が Kevin の元の整数と最後の桁まで一致するのでしょうか? それは、ICON が整数クーポンカウント CC にのみ依存するため、推定値を離散的な「階段状」に限定するからです。百万回の試行バッチでは、ターゲット分位点が整数 CC 遷移をまたいでサンプル補間をトリガーしない限り(すべての 66 個のターゲット分位点を検査した結果、 none がトリガーしないことを確認しました)、サンプル分位数は単一の整数 CC ステップにきれいに着地します。CC の各 +1+1 ステップは、スケールされたテーブルエントリを次のように増加させます。

Δatom(C)
=104KκN^(C)N(21/K−1)≈104ln⁡2K κ\Delta

_{\text{atom}}(C) = \frac{10^4 \sqrt{K}}{\kappa} \frac{\hat{N}(C)}{N} \left(2^{1/K} - 1\right) \approx \frac{10^4 \ln 2}{\sqrt{K},\kappa}

lg_k
=4
= 4 では、κ
=1\kappa = 1、隣接するステップは約 1,733 ユニット離れています。ステップ幅は N^(C)/N\hat{N}(C) / N によってわずかに変化しますが、2 つの独立したモンテカルロ実行が同じ整数 CC に着地する場合、それらの丸められていない浮動小数点数は最後のビットまで一致し、同じ整数に丸められます。7 つの不一致セルを反転させると、すべてのアップストリームエントリも正確な整数 CC ステップの ±0.5\pm 0.5 の範囲内にあり、1 から 3 カウント離れています(5 つのセルは 1 C1,C、それぞれ 2 C2,C および 3 C3,C の 1 つのセル)。lg_k
=7
= 7 では、+1σ+1\sigma の場合、私たちの実行は C
=1329C = 1329 (6806.33) に達しますが、Kevin の 7458 は隣接する C
=1330C = 1330 (7457.61) に丸められます。対照的に、ストリーミング HIP は有限 NN でもはるかに密な値のセットをカバーするため、独立した実行は ICON のように長年にわたって同じ整数にロックされることはありません。

明確にするために、百万回のモンテカルロシミュレーターと生の試行出力は、PR にチェックインされるのではなく、独立した検証記録としてローカルに保持されました。

証拠が証明できること、証明できないこと:6 つの未解決の質問

再構築されたジェネレーター、閉形式定数、および強化されたテストは、PR-355 でアップストリームにマージされました。

これらの単体テストを作成したことで、重要なエンジニアリングの教訓が強調されました。トートロジー的なテストは決して書かないこと。以前のドラフトでは、テストファイル内の 2 番目のハードコーディングされたコピーに対して漸近定数を検証し、信頼区間が点推定値を包含するかどうかをテストするだけで信頼区間をチェックしていました。単純な変異テストは両方のギャップを即座に露呈させました。本番定数を粗い 0.794024 に変更したり、すべての 132 個の信頼テーブルエントリをゼロにしても、すべてのテストに合格しました。2 つの方法でマージされたテストを強化しました。定数テストは、実行時定数と閉形式を比較するために本番コードを直接呼び出し、信頼テーブルテストは、kappa に対する区間幅の厳密な単調性をアサートし、コメントに検証限界を明示的に記載します。現在、すべての 23 個のハフマンテーブルと 16 個の順列テーブルにはビット単位で正確な構築テストがありますが、モンテカルロ信頼テーブルは、単体テストが経験的なセル値や真のカバレッジを検証しないことを明確に文書化しています。

レガシー数値コードをリバースエンジニアリングする際に、最大のトラップは「すべてのテストに合格したので、作者が書いたものを復元した」と考えることです。モデルが成果物を再現することを示すことは、作者がそのモデルをコーディングしたことを証明することではありません。コードコメントとこのレポート全体を通して、データによって一意に特定されたパラメータと、観測では区別できない同値クラスの間に明確な線を引きました。コミュニティのために 6 つの未解決の質問を残します。

  1. 定常状態バイトテーブルモデル: Kevin のスクリプトはポアソン極限を直接評価したのか、それとも 14≤B≤8414 \le B \le 84 までシフトされた K
    =232K = 2^{32} 二項モデルを評価したのか? f64 演算と 3×10−143 \times 10^{-14} の許容誤差の下では、両方とも区別不能に合格します。
  2. Package-Merge のタイブレーク: 1 つの 65 シンボルマージは、正確な重みタイ P(62)
    =P(63)+P(64)
    =2−63P(62) = P(63) + P(64) = 2^{-63} にヒットしますが、リーフファーストとパッケージファーストのタイブレークは、23 テーブルすべてで同一のコード長を生成します。
  3. 立方体分母の起源: なぜ先行立方体因子が 66.774757 を使用するのかは、解析的にもアップストリームの注釈でも説明されていません。
  4. 多項式フィッティンググリッドと重み: 全整数 [1,6K]1, 6K グリッドは lg_k ≤7\le 7 で強力なアブレーションサポートを持ちますが、重み付けの詳細は未解決のままです。lg_k ≥8\ge 8 の場合、サンプリンググリッドは約 101710^{17} の条件数の下で完全に識別不可能です。
  5. 0.7940236163830469 の選択基準: ゼロ周期平均相対誤差は定数を最後のビットまで再現しますが、Kevin が明示的にその最適化問題を解いたかどうかは確認できません。
  6. HIP 信頼テーブルの軽微な散らばり: 行の独立性および連続順序統計近似の下で、私たちの 10610^6 回の試行実行は、lg_k
    =7,9,11
    = 7, 9, 11 に集中した軽微な全体的な発散を示します(行ごとの強度が変化します。最大セル差 83.783.7 ユニット / 1.49% 相対誤差ファクターシフト)。既存の成果物は、履歴サンプリングノイズ、バッチ詳細、および微小な実装の癖を分離できません。ビット単位で正確な再現には、元の PRNG とシードが必要です。

1 月に CpcSketch をポートしていたときに、それらの 2 つの孤立した ocamlopt 行を見つけたとき、それは行き止まりのように見えました。12 桁の浮動小数点残差を追いかけ、直感的な推測をアブレーションで偽造し、複素平面上の極をトレースし、百万回のモンテカルロスイープを完全な共分散行列で実行し、変異テストでテスト境界を特定した後、Kevin J. Lang が論文で発表せずに本番コードに組み込んだ数学のほぼすべての部分が再構築されました。そして、正確な再構築が停止する場所では、成果物が私たちに伝えることができることの正確な境界を今や知っています。

付録:解析的導出

有限 K エントロピー誤差の一次展開

列 jj で、x
=1/(K⋅2j)≪1x = 1 / (K \cdot 2^j) \ll 1 とすると、有限 KK 二項モデルにおける対数生存確率はテイラー級数で次のように展開されます。

ln⁡(1−qbin)
=Nln⁡(1−x)
=−N(x+x22+O(x3))
=−NK⋅2j(1+12K⋅2j+O(K−2))
\ln(1 - q
_{\text{bin}}) = N \ln(1 - x) = -N\left(x + \frac{x^2}{2} + O(x^3)\right) = -\frac{N}{K \cdot 2^j}\left(1 + \frac{1}{2K \cdot 2^j} + O(K^{-2})\right)

これをポアソン極限 ln⁡(1−qpoi)
=−λ/2j\ln(1 - q
_{\text{poi}}) = -\lambda / 2^j と比較すると、有限 KK は各列の指数に摂動ファクター 1+1/(2K⋅2j)1 + 1 / (2K \cdot 2^j) を掛けます。このファクターは列全体で 2−j2^{-j} として減衰するため、単一のグローバルスカラー λ\lambda を調整してもすべての 8 つのウィンドウ列にわたる偏差を同時にキャンセルすることはできず、ΔH
=α/K+O(K−2)\Delta H = \alpha / K + O(K^{-2}) にエントロピーを線形にシフトする残差摂動 δqj
=O(2−j/K)\delta q_j = O(2^{-j} / K) が残ります。

指数定数と周期リップルの Mellin 変換導出

無限列期待値の和 f(λ)
=∑j≥1(1−e−λ/2j)f(\lambda) = \sum

_{j \ge 1} (1 - e^{-\lambda / 2^j}) の Mellin 変換 f∗(s)
=∫0∞f(λ) λs−1 dλf^

*(s) = \int

_0^\infty f(\lambda),\lambda^{s-1},d\lambda を基本帯 −1<Re⁡(s)<0
-1 < \operatorname{Re}(s) < 0 で、∫0∞(1−e−x)xs−1 dx
=−Γ(s)\int

_0^\infty (1 - e^{-x}) x^{s-1},dx = -\Gamma(s) (s
=−1/2s = -1/2 での符号の健全性チェック:正の被積分関数は −Γ(−1/2)
=2π

0
-\Gamma(-1/2) = 2\sqrt{\pi} > 0 に一致します)を使用すると、変換と振動フーリエ級数が得られます。

f∗(s)
=−Γ(s)∑j
=1∞2js
=−Γ(s)2s1−2sf^

*(s) = -\Gamma(s) \sum

_{j=1}^{\infty} 2^{js} = -\Gamma(s) \frac{2^s}{1 - 2^s}
P(t)

\mathcal{P}(t) = −1ln⁡2∑k≠0Γ ⁣(2πikln⁡2)e−2πikt\mathcal{P}(t) = -\frac{1}{\ln 2}\sum

_{k \neq 0} \Gamma!\left(\frac{2\pi i k}{\ln 2}\right) e^{-2\pi i k t}
a
=2∣Γ ⁣(2πiln⁡2)∣
=2πysinh⁡(πy)≈1.0904×10−6a = 2\left\lvert\Gamma!\left(\frac{2\pi i}{\ln 2}\right)\right\rvert = 2\sqrt{\frac{\pi}{y \sinh(\pi y)}} \approx 1.0904 \times 10^{-6}, \quad y = \frac{2\pi}{\ln 2}

Re⁡(s)
=0
\operatorname{Re}(s) = 0 に沿ってすべての極を越えて反転輪郭を右にシフトすると、対数先行項 log⁡2λ+γ/ln⁡2−1/2\log

_2 \lambda + \gamma / \ln 2 - 1/2 が得られる大 λ\lambda 漸近展開 f(λ)
=log⁡2λ+γ/ln⁡2−1/2+P(log⁡2λ)+R(λ)f(\lambda) = \log

_2 \lambda + \gamma / \ln 2 - 1/2 + \mathcal{P}(\log

_2 \lambda) + R(\lambda) が得られます。ここで R(λ)
=∑r≥0exp⁡(−2rλ)<2×10−17R(\lambda) = \sum

_{r \ge 0} \exp(-2^r \lambda) < 2 \times 10^{-17} は指数分岐(λ≥38.5\lambda \ge 38.5)で得られます。

  • s
    =0s = 0 における二重極
    : Γ(s)
    =1/s−γ+O(s)\Gamma(s) = 1/s - \gamma + O(s) に 2s/(1−2s)
    =−1/(sln⁡2)−1/2+O(s)2^s / (1 - 2^s) = -1 / (s \ln 2) - 1/2 + O(s) を掛けると、対数先行項 log⁡2λ+γ/ln⁡2−1/2\log

_2 \lambda + \gamma / \ln 2 - 1/2 が得られます。これを C/KC / K と等値すると、λ≈2 e−γ⋅2C/K\lambda \approx \sqrt{2},e^{-\gamma} \cdot 2^{C/K} となります。

  • sk
    =2πik/ln⁡2s_k = 2\pi i k / \ln 2 における単純極
    : 非ゼロ整数 k≠0k \neq 0 は、1 周期リップル P(t)\mathcal{P}(t) に寄与し、その k
    =±1k = \pm 1 基本調波によって支配されます。相対振幅に変換すると(ln⁡2\ln 2 を掛ける)、a≈1.0904×10−6a \approx 1.0904 \times 10^{-6} となります。
周期平均相対誤差と指数定数

R(λ)R(\lambda) を省略し、t
=log⁡2λt = \log

_2 \lambda と書くと、C/K≈log⁡2λ+γ/ln⁡2−1/2+P(t)C / K \approx \log

_2 \lambda + \gamma / \ln 2 - 1/2 + \mathcal{P}(t) の逆関数は λ≈D⋅2C/Ke−(ln⁡2)P(t)\lambda \approx D \cdot 2^{C/K} e^{-(\ln 2)\mathcal{P}(t)} となり、A⋅2C/KA \cdot 2^{C/K} は相対誤差 (A/D)e(ln⁡2)P(t)−1(A / D) e^{(\ln 2)\mathcal{P}(t)} - 1 を持ちます。その周期平均をゼロにするには、調和平均 A
=D/⟨e(ln⁡2)P(t)⟩A = D / \langle e^{(\ln 2)\mathcal{P}(t)} \rangle が必要です。

(ln⁡2)P(t)(\ln 2)\mathcal{P}(t) の基本調波を acos⁡(2πt+φ)a \cos(2\pi t + \varphi)(平均二乗 a2/2a^2 / 2)で表すと、修正ベッセル関数 ⟨e(ln⁡2)P⟩≈I0(a)
=1+a2/4+a4/64+…\langle e^{(\ln 2)\mathcal{P}} \rangle \approx I_0(a) = 1 + a^2/4 + a^4/64 + \dots に積分され、A≈D(1−a2/4)A \approx D(1 - a^2 / 4) となります。a2/4≈3×10−13a^2 / 4 \approx 3 \times 10^{-13} であるため、D/I0(a)D / I_0(a) と D(1−a2/4)D(1 - a^2 / 4) はわずか〜5×10−26\sim 5 \times 10^{-26} しか異なりません(高次調波は無視できるほど小さいです)。さらに、C/KC / K 全体で平均を取ると、t(t) 全体で平均を取るのと同じ結果になります。d(C/K)
=(1+P′(t)) dtd(C / K) = (1 + \mathcal{P}'(t)),dt では、導関数積分 ∫01e(ln⁡2)P(t)P′(t) dt
=0\int

_0^1 e^{(\ln 2)\mathcal{P}(t)} \mathcal{P}'(t),dt = 0 は [0,1]0, 1 で恒等的にゼロになります。

スプライスポイントでの有限 K による過大評価

固定 C/KC / K では、有限 KK は無限 KK 極限よりもわずかに低い真の密度 λ\lambda を必要とするため、ポアソンから導出された指数分岐はスプライスポイント C
=5.7KC = 5.7K の近くでカーディナリティをわずかに過大評価します。λsplice≈0.794×25.7≈41.3\lambda
_{\text{splice}} \approx 0.794 \times 2^{5.7} \approx 41.3 を一次有限 KK 補正に代入すると、最大相対バイアスが得られます。

ΔN^N≈12λspliceK≈182.6K\frac{\Delta \hat{N}}{N} \approx \frac{1}{2 \lambda
_{\text{splice}} K} \approx \frac{1}{82.6 K}

ICON および HIP の漸近相対標準誤差

λ≫1\lambda \gg 1 では、ポアソン極限では行列セルは独立しているため、合計クーポン分散は列全体で次のように合計されます。Var⁡(C)≈K∑exp⁡(−λ/2j)(1−exp⁡(−λ/2j))\operatorname{Var}(C) \approx K \sum \exp(-\lambda / 2^j)\left(1 - \exp(-\lambda / 2^j)\right)。この和を 1 つの二進数デカッドにわたる連続積分で近似すると、標準的なFrullani 積分が得られます。

Var⁡(C)K≈1ln⁡2∫0∞e−u−e−2uu du
=1  ⟹  sd⁡(C)≈K\frac{\operatorname{Var}(C)}{K} \approx \frac{1}{\ln 2}\int

_0^\infty \frac{e^{-u} - e^{-2u}}{u},du = 1 \implies \operatorname{sd}(C) \approx \sqrt{K}
Var⁡(N^HIP)≈∫0N(1p−1)dn≈ln⁡22N2K  ⟹  RSE⁡(N^HIP)≈ln⁡221K\operatorname{Var}(\hat{N}
_{\text{HIP}}) \approx \int

_0^N \left(\frac{1}{p} - 1\right) dn \approx \frac{\ln 2}{2} \frac{N^2}{K} \implies \operatorname{RSE}(\hat{N}
_{\text{HIP}}) \approx \sqrt{\frac{\ln 2}{2}} \frac{1}{\sqrt{K}}

  • ICON 推定器: sd⁡(C)\operatorname{sd}(C) を指数分岐 N^ICON∝2C/K\hat{N}
    _{\text{ICON}} \propto 2^{C/K} に伝播させると、RSE⁡(N^ICON)≈(ln⁡2/K)sd⁡(C)
    =ln⁡2/K\operatorname{RSE}(\hat{N}
    _{\text{ICON}}) \approx (\ln 2 / K)\operatorname{sd}(C) = \ln 2 / \sqrt{K} となり、ソースコードの ICON_ERROR_CONSTANT
    =ln⁡2
    = \ln 2 と一致します。
  • HIP 推定器: 到着密度 λ
    =n/K\lambda = n / K では、新しいアイテムは確率 p≈1/(λln⁡2)p \approx 1 / (\lambda \ln 2) で空のセルを反転させます。条件付きステップ分散 (1/p−1)(1 / p - 1) を 00 から NN まで積分すると、RSE⁡(N^HIP)≈(ln⁡2)/2/K\operatorname{RSE}(\hat{N}
    _{\text{HIP}}) \approx \sqrt{(\ln 2) / 2} / \sqrt{K} となり、その定数はソースコードで 0.5887050112577373 と評価されます。