It started with a routine feature in ScopeDB: implementing approx_count_distinct for approximate distinct counting.
HyperLogLog (HLL) is the standard textbook choice. Early on, Rust’s HLL ecosystem was uneven, so I started with Cloudflare’s open-source cardinality-estimator. That crate leaned heavily on unsafe code and manual bit-packing tricks, though, so to keep things auditable and under our control, I forked and maintained an internal copy inside ScopeDB.
While evaluating alternatives, I came across Apache DataSketches, which offered a battle-tested HllSketch alongside CpcSketch, an even more space-efficient design. At the time, Apache DataSketches only shipped Java and C++ implementations, whereas ScopeDB is written in Rust.
As it turned out, the Apache DataSketches community was interested in an official Rust port. Starting late last year, I teamed up with a few other Rust developers well-versed in sketching algorithms to build and ship the initial releases of datasketches-rust, beginning with HllSketch. Soon after, I switched ScopeDB’s distinct counting over to our datasketches-rust implementation.

Anyone who has implemented streaming distinct counting knows how HLL works: elements are hashed into buckets, and each bucket keeps only the maximum leading-zero count seen so far (typically 4 to 6 bits), while every other hit in that bucket goes unrecorded. Once HLL enters dense mode, every bucket maintains a fixed-width register.
In his 2017 paper Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm, Yahoo! Research scientist Kevin J. Lang proposed going back to basics: instead of keeping only per-bucket maxima, retain the full bit matrix of the classic FM85 coupon collector’s process. Whenever row sees a hash with leading zeros, set bit to . Keeping the full two-dimensional hit matrix lets CPC pair a streaming HIP estimator with a mergeable ICON estimator for higher statistical efficiency than HLL. On serialization, it adapts its layout to fill density: low cardinalities use a sparse PairTable of (row, column) pairs, while medium and high cardinalities combine a sliding 8-bit window, length-limited Huffman coding, and column permutations to pack the sketch near the information-theoretic entropy limit. According to the DataSketches documentation, serialized CPC shrinks storage by 30% to 40% compared with HLL at equal accuracy.
In late January, I ported CpcSketch to datasketches-rust (PR-75) and switched ScopeDB over to it. It has run smoothly in production for more than six months.

While porting CpcSketch from the upstream C++ and Java implementations, however, I noticed several hardcoded magic lookup tables in the source code:
- 23 static Huffman encoding tables
- 16 sliding-window column permutations
- 23 sets of degree-19 polynomial correction coefficients
- 4 empirical confidence-interval quantile tables
These four sets of static tables live in compression_data.rs and estimator.rs. Here is a short excerpt:
// datasketches/src/cpc/compression_data.rs
pub 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.rs
static 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] = [ /* ... */ ];
Whenever I port lookup tables, I prefer to derive the values from first principles in unit tests and check them element by element against the static array. For kxp_byte_lookup, for example, I kept the derivation right inside the test suite:
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);
}
For CompressionData and the ICON estimator tables, though, no generator source existed anywhere in the repositories, so I had no way to derive them on my own back then. Only two build commands remained in an upstream comment:
~/ocaml-4.03.0/bin/ocamlopt -o generateHuffmanCodes columnProbabilities.ml generateHuffmanCodes.ml
./generateHuffmanCodes > raw-encoding-tables.c
I searched every Apache DataSketches repository and came up empty on those .ml files. So I opened ISSUE-720 on datasketches-java to ask where the generator sources lived. Lee Rhodes replied:
Kevin did most of his math simulations and modeling in OCaml. And his code was on his computer, which no longer exists. And his personal code died with him … even if they have a copy of his old computer it might be trying to find a needle in a haystack.
Kevin passed away in April 2019, and any code left on his personal machine is effectively lost to history.
I was saddened to hear that. Kevin’s research in sketching algorithms underpins many of the core sketches in Apache DataSketches:
- A Framework for Estimating Stream Expression Cardinalities (Theta Sketch)
- Optimal Quantile Approximation in Streams (KLL Sketch, the “L” in KLL)
- A High-Performance Algorithm for Identifying Frequent Items in Data Streams (Frequent Items Sketch)
- Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm (CPC Sketch and HLL estimators)
Still, with the runtime decoders and detailed header comments sitting right there in the source files, it seemed possible to reverse-engineer the offline generators from the artifacts alone. I asked Lee whether the CPC paper explained how the tables were derived, and he answered:
You should definitely read the paper. But it won’t tell you any details on the Huffman codings. As I recall, in his paper he used a more standard compression scheme. He finished his work on the code after he had finished his paper — and in the process came up with the modified Huffman coding idea, which is quite a bit more efficient than what he discussed in the paper.
That placed the derivation well beyond what I could work out on my own in an afternoon.
Since CpcSketch worked fine in datasketches-rust as long as the lookup arrays were copied faithfully, I left the mystery aside for the time being.
Then Gemini 4 Carbon came out just as I was preparing the next release of datasketches-rust. Since the checked-in tables and 20-digit header comments already acted as a strict numerical oracle, any candidate generator could be tested immediately in code: either it reproduced every codeword, permutation entry, and floating-point diagnostic within IEEE-754 precision, or it was wrong. That made the problem well suited to an agentic workflow built around executable checks and adversarial review.
Over several iterations, I steered three models against that oracle and against one another:
- Initial synthesis (Gemini 4 Carbon): Starting from the static arrays and source comments, it wrote executable probes and built the first constructive test harness, reproducing the Huffman codewords and column permutations bit-for-bit and fitting the ICON polynomials to matching accuracy.
- Mathematical falsification (Claude Opus 5.5): Tasked with breaking those initial claims, it ran controlled ablations that disproved an early “left-edge truncation” explanation, isolated an
f64cancellation trap, mapped out where the polynomial fits stop being identifiable, and re-ran the million-trial Monte Carlo statistics. - Mutation and analytical audit (GPT 6 Astra): Auditing both the tests and the derivations, it used mutation testing to expose two tautological assertions, caught several mathematical overstatements in earlier drafts, and derived a closed-form expression matching the trailing digits of the asymptotic exponential constant.
None of the models got everything right on the first try, and several plausible-looking explanations collapsed as soon as we tested perturbations in code. What survived that filter became PR-355, which checks the reconstructed generators and derivations into datasketches-rust as unit tests, following the same approach we took for kxp_byte_lookup.

The rest of this post focuses on the mathematics and numerical forensics behind those four sets of tables: how each structure works, which wrong turns looked convincing until an ablation broke them, and where the surviving artifacts cannot tell two models apart. Formal derivations sit in the appendix at the end; if you spot an error, feel free to leave a comment or open a PR on datasketches-rust.
The Blind Spot of Discrete Codewords, and a 20-Digit Fingerprint
We begin with the 23 Huffman coding tables in compression_data.rs.
Why hardcode 23 static Huffman tables at all? Building trees dynamically per sketch would force the serializer to write tree headers into the compressed stream, wiping out the tens of bytes saved on small sketches. Meanwhile, the probability that column of the coupon matrix is set depends mainly on the fill ratio (collected coupons over row count ). Finite- corrections enter only at order , a tiny difference that turns out to be the key clue below. Precomputing optimal tables offline across representative checkpoints lets determine_pseudo_phase select the right table solely from lg_k and num_coupons without storing a table ID.
The first 22 tables encode 8-bit sliding-window bytes ( through ). Given the per-column bit probabilities through for the 8 adjacent columns in the window (treated as independent), byte has theoretical probability equal to the product of eight Bernoulli terms: if bit is , and if bit is .
Upstream decoders use a -entry lookup table, immediately revealing a hard 12-bit cap on codeword length. Feeding the byte probabilities into Larmore and Hirschberg’s 1990 Package-Merge algorithm yields the length-limited code lengths; assigning canonical codewords sorted by length and symbol value, then bit-reversing each codeword for CPC’s LSB-first bitstream, reproduces all 5,697 codewords across all 23 tables bit-for-bit.
The next question is which occupancy model columnProbabilities.ml actually used for column :
- Finite- binomial model: each item hits column with single-trial probability , giving after insertions.
- Infinite- Poisson limit: letting with fixed density , occupancy converges to .
Comparing integer codewords alone immediately runs into a blind spot: across the six midrange tables (array indices 16..21), sweeping from all the way to infinity yields the exact same 256 codewords. Huffman lengths are discrete step functions, so tiny shifts in probability rarely flip tree merge decisions.
What actually acts as a continuous fingerprint to pin down are the two 20-digit floating-point comments that generateHuffmanCodes.ml printed above each table. Here is table 16 (the first midrange byte table):
// entropy: 2.1627885076675394949
// avg_length: 2.2704182849800043087; max_length = 12; num_symbols = 256
Shannon entropy and average code length vary continuously with the underlying distribution. Holding the checkpoints fixed, we swept from to infinity across all 22 byte tables. Here are the worst-case errors across the six midrange tables:
| Candidate Parameter | Max Entropy Error | Max Avg Code Length Error |
|---|---|---|
| (Poisson) |
At , the residual drops by four orders of magnitude, right down to IEEE-754 double-precision rounding noise.
Look at the clean symmetry in that table: produces the exact same error as , while has half the error. That happens because, to first order, the finite- departure from the Poisson limit scales linearly with (derived in the first appendix section). When the true parameter is , both and sit one step of away on the axis, whereas sits half a step away. Fittingly, comments in the upstream ICON estimator also put the maximum number of table rows at slots.
Steady-State Tables: The “Left-Edge Truncation” Mirage
Moving to the 16 steady-state tables, which cover phases at fill ratios , we ran into a convincing false lead.
The column permutation tables (covered next) establish that the steady-state integer baseline is . Yet plugging our newly recovered and into the 16 steady-state tables leaves a entropy residual in the 12th decimal place.
At first glance, “left-edge truncation” looks like the obvious explanation: around , column 1 of the coupon matrix is not quite 100% saturated, and its probability of still being is roughly , right on the order of the residual. Sure enough, keeping fixed and pushing the working point out to () drops the entropy error to . Everything seemed to line up to the order of magnitude.
Two controlled ablations quickly ruled that hypothesis out:
- Holding fixed while switching from the binomial model to the Poisson limit drops the error across all 16 steady-state tables to , right down to double-precision rounding noise.
- Holding fixed while stepping gives maximum entropy errors of , , and , halving with every step in .
Why does it halve every time? Incrementing by shifts the 8-bit sliding window one column to the right, where the binomial correction relative to the Poisson limit decays as . Pushing to did nothing to left-edge truncation; it merely pushed the window out near column 29, shrinking the in-window finite- correction below f64 machine epsilon and inadvertently faking the Poisson limit with deep columns.
How much effect can the left edge actually have? Even though the generator solves for using the expectation over all 128 columns before computing window probabilities (so column 1 does enter indirectly through ), the shift identity bounds its magnitude cleanly. For the infinite-column Poisson expectation , doubling shifts the series index by one and adds a single leading term . For the truncated 128-column sum evaluated by the code, cutting off at column 128 subtracts the right-edge tail term as well:
In other words, incrementing by doubles and shifts the window one column right, keeping in-window distributions nearly shift-invariant up to the left- and right-edge truncation terms. At (), the left-edge term is roughly (a relative effect on ), and the right-edge term is roughly . Both sit more than ten and twenty orders of magnitude below the residual. The discrepancy came from finite , not the left edge.
This also draws a sharp identifiability boundary. On the 16 steady-state tables alone, under the test’s tolerance, both the Poisson limit for and the binomial model for match every entropy and average-length header within tolerance. They are not bit-identical (still differing by ), only indistinguishable within double-precision arithmetic and that tolerance. Right at , the 128-column right-edge term has already grown exponentially to ; by , table 7’s average-length error hits and breaks tolerance; further right, right-edge truncation takes over completely, reaching at . We chose the ” Poisson limit” model because it shares the exact working point of the column permutations without inventing an arbitrary , though the static tables by themselves cannot rule out the equivalent finite- shifted interval.
Column Permutations: A Rounding Trap at Phase 19/32
In the steady-state regime, columns left of the sliding window are nearly all , while columns to the right are nearly all . The remaining 56 out-of-window columns therefore store only surprising bits, namely zeros left of the window or ones right of the window, encoded via column index deltas. Putting higher-probability surprising columns first keeps unary deltas short, which is what the 16 56-byte tables from generatePermutationsForSLIDING.ml accomplish.
First, their indexing scheme:
- Let the window offset be . Physical 0-based column
colmaps to canonical indexcanon = (col + 56 - offset) % 64, putting right-side columns first and the left-side columns at the tail. - The 56 canonical slots are ranked in descending order of surprising-bit probability.
- Each static array stores
encode_perm[canon] = rank, rather than listing columns in sorted order.
That layout alone pins down : in the first six tables (phase indices 0..5), three trailing slots correspond to columns left of the window and get interleaved upward; in the last ten tables, that count jumps to four. Since steps from to at phase 3/8, jumping from 3 to 4 settles . Testing candidates confirms it directly: match tables out of 16, respectively. Unlike the byte tables, sweeping from to leaves all 16 permutation tables byte-for-byte identical: column permutations are completely insensitive to .
Once is fixed, a subtle numerical trap waits in , the probability that a column left of the window remains . If you lazily compute 1.0 - q from the already-computed 1-bit probability , both and match 15 out of 16 tables, missing just 4 entries in the single table for phase 19/32. At that phase (), look at the four trailing slots:
Canonical Index canon | Physical Column (1-based) | Surprising Probability | Rank |
|---|---|---|---|
| 49 | 62 | 53 | |
| 50 | 63 | 54 | |
| 51 | 64 | 55 | |
| 52 | 1 | 52 |
Physical column 1 has surprising probability , strictly larger than column 62’s . Sorted by descending probability, the trailing canonical sequence must be 48, 52, 49, 50, 51, putting [53, 54, 55, 52] at slice encode_perm[49..=52]. Computing 1.0 - q instead pushes slot 52 to last place, yielding [52, 53, 54, 55].
The root cause is floating-point cancellation. Although is easily representable in IEEE-754 f64 (nowhere near underflow), lands right below , where adjacent doubles are spaced by . Under round-to-nearest-even, whenever , rounds up to , turning 1.0 - q into and wiping out completely before subtraction even happens.
Evaluating the exponential directly (such as (-lambda / 2^j).exp() in Rust) avoids catastrophic cancellation and reproduces all 16 permutation tables bit-for-bit at . This single comparison simultaneously rules out and 1.0 - q, though strictly speaking, it only proves Kevin’s generator did not use 1.0 - q, not the exact syntax he wrote.
Degree-19 Polynomials and the Exponential Constant
Next comes the ICON cardinality estimator in estimator.rs. Rather than running Newton’s method across all 128 columns at query time, Kevin designed a two-piece approximation:
- For (tightened to for
lg_k), evaluate a degree-19 polynomial preconditioned with a cubic leading factor - Beyond that splice point, switch to an asymptotic exponential formula
Factoring out keeps the polynomial’s target ratio within , instead of letting expand more than over . Scaling the variable as maps onto , keeping at rather than .
Fitting Interval and Identifiability
If runtime switches branches at or , what domain were the 23 polynomials originally fitted over? Evaluating the checked-in polynomials past the runtime cutoff reveals a clear pattern:
- Every row holds relative error within all the way out to , then diverges rapidly just past ; by , errors jump to between and across the board.
- For
lg_k(), the cliff is razor-sharp: across , maximum relative error is (at ), dips to at , and spikes two orders of magnitude to at . - At larger , however, a single integer step barely moves , smoothing out any sharp break: at
lg_k, relative error at is still , even slightly smaller than at .
Our confidence that fitting stopped right at therefore relies on the coefficient regression below rather than error cliffs alone. Extending the fit slightly past the threshold makes intuitive sense as a buffer against Runge boundary oscillations, though no upstream note confirms that intent.
Attempting to reconstruct the coefficients exposes a sharp identifiability boundary between small and large sketches:
- For
lg_k( integer points), unweighted least squares on every integer point from to recovers all 20 coefficients within 0.07% to 1.4% of upstream values. Dropping or shifting either endpoint by degrades coefficient agreement by to . While that strongly supports an all-integer grid, it still leaves details unpinned: relative-error weighting actually fits slightly closer atlg_k, and the original solver details are lost. - For
lg_k, both all-integer grids and boundary-weighted grids yield coefficients 14% to 65% off from upstream, even while predicted values track the reference curve within in-range and within past the splice point. Recovering high-degree monomial coefficients from samples is severely ill-conditioned: the unscaled degree-19 Vandermonde matrix on has an condition number around ( atlg_k), still hovering around after column normalization. Two coefficient vectors far apart in Euclidean space can produce virtually identical curves.
Three Constants Behind the Exponential Branch
The exponential constant and upstream test bounds used to look like pure empirical tuning. In reality, all three fall straight out of the Poisson model (derived in the appendix):
- Leading constant: Taking the Mellin transform of the infinite-column Poisson expectation and computing the residue at the double pole yields , where is 1-periodic and drops below on the exponential branch (). Neglecting and gives with closed form , differing from the hardcoded runtime constant only in the 13th decimal place by .
- Part-per-million periodic ripple: The oscillatory series arises from simple poles on the imaginary axis; its fundamental harmonic adds a periodic ripple of relative amplitude , setting the exact accuracy floor observed at large .
- Why
1 / (80 * K)in upstream tests: Java’sIconEstimatorTestuses an error bound ofmax(2e-6, 1.0 / (80 * k)). Finite- effects make the Poisson formula slightly overestimate cardinality, reaching peak relative bias at the () splice point. Rounding down to covers that peak with roughly a 3% margin, though whether Kevin picked 80 this way is undocumented.
Pinning Down the Trailing Digits
That gap between and the runtime constant has a remarkably crisp mathematical explanation down to the last bit. Suppose was chosen so that has zero mean relative error over one period relative to the exact Poisson inverse. By the appendix derivation on period-mean relative error, must satisfy:
Replacing with the second-order expansion of the modified Bessel function omits only , far below double precision. Rounded to f64, this closed form matches 0.7940236163830469 bit-for-bit. Our unit test queries the production constant directly at runtime and verifies an exact match (and agrees within 2 ULPs against numerical harmonic integration over a full cycle). Still, the epistemological caveat holds: showing that an optimality criterion reproduces a constant bit-for-bit does not prove Kevin wrote that exact criterion.
A Million Monte Carlo Trials and the Discrete Staircase Effect
The remaining pieces are the four confidence-bound tables: ICON_{LOW,HIGH}_SIDE_DATA and HIP_{LOW,HIGH}_SIDE_DATA. Upstream comments note that they record empirical quantiles from Monte Carlo trials per row at true cardinality : each cell stores rounded to an integer, where is the one-sided relative-error quantile corresponding to normal tail probability .
Stochastic tables cannot be reconstructed bit-for-bit like Huffman codes; they have to be checked statistically against independent simulations. Two practical hurdles arise immediately: how to run trials across lg_k = 4..=14 on a single machine, and why today’s numbers match Kevin’s original integers as closely as they do.
Simulating individual insertions naively at lg_k () takes steps per trial ( iterations across trials), which is impractical on a single machine. Our fast simulator builds on the exponential-skip coupon process Kevin sketched in Appendix B of his paper: maintain just 64 empty-cell counters , the running HIP accumulator, and processed element count. Note one essential catch: HIP values cannot be reconstructed from final column counts alone, because HIP is strictly path-dependent on discovery order. As a minimal counterexample at , hitting column 1 and then column 2 yields 2.0323, whereas hitting column 2 and then column 1 yields 2.0159, even though the final column counts are identical. At each step, total new-cell probability is , so waiting steps between hits follow an exact geometric distribution sampled via a single logarithm; on each hit, add to HIP and sample column proportionally to .
One subtle implementation boundary also belongs on the record: the fast simulator assigns explicit weight to physical column 64 (index 63) with initial kxp absorbing the remaining tail mass, whereas sketch.rs folds all hashes with leading zeros into column 64 (actual hit probability ) while still deducting from kxp and calling refresh_kxp every 8 shifts to limit floating-point drift. Ideal and sketch processes therefore match strictly only as long as column 64 goes unhit and refresh_kxp drift stays negligible. Across over simulated insertions in our runs, expected column-64 hits total roughly , making it irrelevant in practice. Skipping empty draws reduces per-trial cost from to (roughly coupons at ), cutting runtime by two orders of magnitude so all 11 rows ( trials each in simA) finished in ~11 minutes across 14 threads.
We also had to avoid a statistical pitfall. Because all six quantiles in a row ( to ) come from the same trials, they are correlated; simply summing squared per-cell z-scores against a distribution is invalid. We saved full raw trial vectors and to disk across three runs:
simA: trials per row across all 11 rows (lg_k= 4..=14)- Real CpcSketch control: trials per row with MurmurHash3 across
lg_k= 4..=7, with independent stream seeds perlg_k simB: a second independent seed of the fast simulator acrosslg_k= 4..=12(9 rows)
We estimated each row’s quantile covariance matrix in two independent ways, using 2,000 nonparametric Bootstrap resamples and Siddiqui’s order-statistic asymptotic variance formula, and formed joint Mahalanobis statistics across independent rows.
Both sanity-check controls held cleanly and agreed closely between both covariance estimators:
- Same-simulator null control: Comparing
simAvs.simBacross all 54 shared degrees of freedom (lg_k= 4..=12) yields () under Bootstrap covariance and () analytically, showing textbook agreement between two independent -trial batches. - Real CpcSketch control: Comparing real sketches against
simAover 24 DoF (lg_k= 4..=7) yields () Bootstrap and () analytic; comparing against the average ofsimAandsimBgives () and (). Zero of the 24 cells exceeded , and only one exceeded , showing no sign of systematic bias.
Comparing against Kevin’s checked-in tables revealed a clear divide between ICON and HIP:
- ICON tables: Across all 66 cells,
simAreproduces 59 of Kevin’s integers verbatim, with every underlying float sitting inside the rounding interval. InsimB, 51 of 54 shared cells match verbatim, with 49 exact matches overlapping across Upstream,simA, andsimB. - HIP tables: Under row independence, uniform rounding variance, and upstream trial-count covariance, Upstream vs.
simAover 66 DoF yields (; analytic , ); Upstream vs.simBover 54 DoF yields (; analytic , ); and Upstream vs. the average ofsimAandsimBgives (; analytic , ). Most of the signal concentrates inlg_k: insimAtheir single-row -values are , , and , yielding Holm-adjusted -values across 11 rows of (lg_k), (lg_k), and (lg_k), whereas in independentsimBtheir single-row -values are , , and . So while a mild aggregate discrepancy exists, row-level evidence is too uneven to pin down those three rows conclusively. In absolute terms, the largest difference across all 66 cells is just table units (atlg_k, ), changing error factor by at most 1.49% and one-sided confidence width by roughly 1.61%. That shift is minor in practice, though we did not re-measure empirical coverage rates directly.
Why do nearly 90% of stochastic ICON quantile cells match Kevin’s original integers down to the last digit? Because ICON depends solely on the integer coupon count , confining estimates to discrete “stair steps”. In a million-trial batch, as long as a target quantile does not straddle an integer- transition and trigger sample interpolation — and inspecting all 66 target quantiles confirms none did — the sample quantile lands cleanly on a single integer step. Each step in raises the scaled table entry by:
At lg_k , , adjacent steps sit roughly 1,733 units apart. Step widths vary slightly with , yet whenever two independent Monte Carlo runs fall on the same integer , their unrounded floats agree to the last bit and round to the same integer. Inverting the 7 mismatched cells shows that every upstream entry also sits within of an exact integer- step, just 1 to 3 counts away (5 cells differ by , and one cell each by and ). At lg_k , , for example, our run hits (6806.33), while Kevin’s 7458 rounds neighboring (7457.61). Streaming HIP, by contrast, spans a vastly denser set of values even at finite , so independent runs never lock onto the same integers across years the way ICON does.
To be clear, the million-trial Monte Carlo simulator and raw trial outputs were kept locally as an independent verification record rather than checked into the PR.
What the Evidence Can and Cannot Prove: Six Open Questions
The reconstructed generators, closed-form constants, and hardened tests have been merged upstream in PR-355.
Writing those unit tests underscored an important engineering lesson: never write tautological tests. An earlier draft verified the asymptotic constant against a second hardcoded copy inside the test file, and checked confidence bounds only by testing whether they bracketed the point estimate. Simple mutation testing exposed both gaps immediately: changing the production constant to a coarse 0.794024 or zeroing out all 132 confidence-table entries still passed every test. We hardened the merged tests in two ways: the constant test calls production code directly to compare the runtime constant against the closed form, and the confidence-table test asserts strict monotonicity of interval width with kappa while stating its verification limits explicitly in comments. Today, all 23 Huffman tables and 16 permutation tables have bit-exact constructive tests, whereas the Monte Carlo confidence tables clearly document that unit tests do not verify empirical cell values or true coverage.
When reverse-engineering legacy numerical code, the biggest trap is thinking, “all tests pass, so we recovered what the author wrote.” Proving a model reproduces the artifacts is not proving the author coded that model. Throughout code comments and this report, we drew a bright line between parameters uniquely pinned by data and equivalence classes that observations cannot tell apart, leaving six open questions for the community:
- Steady-state byte table model: Did Kevin’s script evaluate the Poisson limit directly, or a binomial model shifted out to ? Under
f64arithmetic and a tolerance, both pass indistinguishably. - Package-Merge tie-breaking: One 65-symbol merge hits an exact weight tie , yet leaf-first and package-first tie-breaking produce identical code lengths across all 23 tables.
- Origin of the cubic denominator: Why the leading cubic factor uses
66.774757remains unexplained analytically or in upstream notes. - Polynomial fitting grid and weights: An all-integer grid has strong ablation support for
lg_k, though weighting details remain unpinned; forlg_k, sampling grids are completely unidentifiable beneath condition numbers. - Selection criterion for
0.7940236163830469: Zero period-mean relative error reproduces the constant down to the last bit, but whether Kevin explicitly solved that optimization problem cannot be confirmed. - Mild HIP confidence-table scatter: Under row independence and continuous order-statistic approximations, our -trial runs show a mild overall divergence concentrated in
lg_k(varying per-row strength; max cell diff units / 1.49% relative error-factor shift). Existing artifacts cannot separate historical sampling noise, batch details, and tiny implementation quirks; bit-exact reproduction would require the original PRNG and seed.
When I first spotted those two orphaned ocamlopt lines while porting CpcSketch back in January, they looked like a dead end. After chasing 12th-decimal floating-point residuals, falsifying intuitive guesses with ablations, tracing poles on the complex plane, running million-trial Monte Carlo sweeps with full covariance matrices, and pinning down test boundaries with mutation testing, almost every piece of mathematics Kevin J. Lang built into production code without publishing in his paper has been reconstructed — and where exact reconstruction stops, we now know the exact boundary of what the artifacts can tell us.
Appendix: Analytic Derivations
First-Order Expansion of Finite-K Entropy Error
In column , letting , the log-survival probability in the finite- binomial model expands via Taylor series as:
Comparing this with the Poisson limit , finite multiplies each column exponent by a perturbation factor . Since that factor decays as across columns, tuning a single global scalar cannot cancel deviations across all 8 window columns simultaneously, leaving residual perturbations that shift Shannon entropy linearly in : .
Mellin Transform Derivation of the Leading Term and Periodic Ripple
Taking the Mellin transform of the infinite-column expectation sum in the fundamental strip using (sanity-checking the sign at : a positive integrand matches ) yields the transform and oscillatory Fourier series:
Shifting the inversion contour rightward past all poles along produces the large- asymptotic expansion , where on the exponential branch ():
- Double pole at : Multiplying by yields the logarithmic leading term . Equating this to gives .
- Simple poles at : Nonzero integers contribute the 1-periodic ripple , dominated by its fundamental harmonic. Converting to relative amplitude in (multiplying by ) yields .
Period-Mean Relative Error and the Exponential Constant
Dropping and writing , inverting gives , so has relative error . Setting its period mean to zero requires the harmonic mean .
Representing the fundamental harmonic of as (mean square ) integrates to the modified Bessel function , yielding . Because , and differ by only (and higher harmonics are negligible). Moreover, averaging over gives the exact same result as averaging over : in , the derivative integral vanishes identically over .
Finite-K Overestimation at the Splice Point
At fixed , finite requires a slightly lower true density than the infinite- limit, so the Poisson-derived exponential branch slightly overestimates cardinality near the splice point . Plugging into the first-order finite- correction gives the peak relative bias:
Asymptotic Relative Standard Errors of ICON and HIP
For , matrix cells are independent in the Poisson limit, so total coupon variance sums across columns as . Approximating the sum by a continuous integral over one dyadic decade yields a standard Frullani integral:
- ICON estimator: Propagating through the exponential branch gives , matching
ICON_ERROR_CONSTANTin source code. - HIP estimator: At arrival density , a new item flips an empty cell with probability . Integrating conditional step variance from to yields , whose constant evaluates to
0.5887050112577373in source code.