This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
The following commit(s) were added to refs/heads/main by this push:
new 9a90f38 test(cpc): add generation and verification tests for static
lookup tables (#355)
9a90f38 is described below
commit 9a90f385f25e72eb038a4bf779a0901be1a01ef4
Author: tison <[email protected]>
AuthorDate: Mon Nov 16 16:10:22 2026 +0800
test(cpc): add generation and verification tests for static lookup tables
(#355)
---
datasketches/src/cpc/compression_data.rs | 448 ++++++++++++++++++++++++++++
datasketches/src/cpc/estimator.rs | 484 +++++++++++++++++++++++++++++++
2 files changed, 932 insertions(+)
diff --git a/datasketches/src/cpc/compression_data.rs
b/datasketches/src/cpc/compression_data.rs
index 3c9923e..38342f0 100644
--- a/datasketches/src/cpc/compression_data.rs
+++ b/datasketches/src/cpc/compression_data.rs
@@ -11962,10 +11962,458 @@ pub static DECODING_TABLES_FOR_HIGH_ENTROPY_BYTE:
[[u16; 4096]; 22] = [
#[cfg(test)]
mod tests {
+ // Reconstructs and verifies all six static lookup tables in this module
from first principles.
+ //
+ // In the original C/C++/Java implementations of CPC ("FM85"), only the
generated static arrays
+ // and the runtime table-inversion helpers (`makeDecodingTable` /
`makeInversePermutation` in
+ // `fm85Compression.c`) were checked into source control. The three
offline OCaml generators
+ // written by Kevin J. Lang referenced in the comments above were never
published:
+ //
+ // 1. `columnProbabilities.ml`: computes cell occupancy probabilities in
the FM85 coupon matrix
+ // and derives the symbol distributions for high-entropy window bytes
and for the column
+ // deltas of surprise pairs.
+ // 2. `generateHuffmanCodes.ml`: builds length-limited (<= 12 bits)
canonical LSB-first Huffman
+ // encoding tables (`LENGTH_LIMITED_UNARY_ENCODING_TABLE65` and the 22
tables of
+ // `ENCODING_TABLES_FOR_HIGH_ENTROPY_BYTE`).
+ // 3. `generatePermutationsForSLIDING.ml`: orders the 56 non-window
columns by descending
+ // surprise probability across the 16 sliding-window phases
+ // (`COLUMN_PERMUTATIONS_FOR_ENCODING`).
+ //
+ // The helpers and tests below document which hidden parameters the
checked-in tables and
+ // header comments identify, which ones they leave open, and verify a
1-to-1 bit-exact match
+ // for every entry of all six tables.
+
+ use std::array::from_fn;
+
use googletest::assert_that;
use googletest::prelude::container_eq;
+ use googletest::prelude::near;
use super::*;
+ use crate::common::inv_pow2::inv_pow2;
+
+ /// Occupancy model of the midrange tables: binomial cell marginals at
sketch size `K = 2^32`.
+ ///
+ /// How `K = 2^32` was reverse-engineered: the midrange codewords are
reproduced by every
+ /// `K >= 2^16`, so only the 20-digit header entropies
(`RECORDED_HEADER_STATS`) can pin `K`.
+ /// The worst deviation over the six midrange headers is `6e-15` at `K =
2^32`, versus
+ /// `4.9e-11` at `K = 2^31`, `2.5e-11` at `K = 2^33`, and `4.9e-11` in the
Poisson limit
+ /// `K -> inf`. The residuals on both sides follow the `1 / K` scaling of
the finite-`K`
+ /// correction (`ln(1 - x) = -x - x^2 / 2 - ...` multiplies the Poisson
exponent by roughly
+ /// `1 + 1 / (2 * K * 2^col)`), and `2^32` is also the upper end of the
`2^4 .. 2^32` range
+ /// named in the ICON estimator notes.
+ const MIDRANGE_MODEL: Occupancy = Occupancy::Binomial {
+ k: (1_u64 << 32) as f64,
+ };
+
+ /// Occupancy model of the steady-state tables and the sliding column
permutations: the
+ /// stationary Poisson limit `K -> inf`.
+ ///
+ /// At the true base `C / K = 6.0 + phase` (`STEADY_STATE_C_OVER_K_BASE`),
the steady-state
+ /// byte tables identify only this limit: the Poisson model matches all 16
steady-state headers
+ /// within `1.1e-14`, whereas the binomial model at `K = 2^32` misses them
by `6.1e-12`. That
+ /// residual halves with every unit added to the base (`3.1e-12` at `7.0 +
phase`, `1.5e-12` at
+ /// `8.0 + phase`), which is the `2^-col / K` signature of the finite-`K`
correction at the
+ /// window columns, not an effect of the matrix edge. Although `lambda` is
solved over all 128
+ /// columns, the Poisson identity `f(2 * lambda) = f(lambda) + 1 -
exp(-lambda)` for
+ /// `f(lambda) = E[C] / K` means that raising the base by one doubles
`lambda` and shifts the
+ /// window by one column up to a relative `ln(2) * exp(-lambda)`, about
`2e-23` at `C / K = 6 +
+ /// 1/32` (`lambda ≈ 51.9`). Consequently `K = 2^32` with any base from
`14` to `84` also
+ /// matches both the entropy and average-length headers of all 16
steady-state tables within
+ /// `HEADER_STATS_TOLERANCE`; the Poisson limit at base `6` is preferred
because a single
+ /// operating point then explains both the byte tables and the
permutations, which are
+ /// insensitive to `K`.
+ const STEADY_STATE_MODEL: Occupancy = Occupancy::Poisson;
+
+ /// Integer part of the steady-state operating point `C / K = 6.0 +
phase`, where
+ /// `phase = (2 * m + 1) / 32` is the midpoint of the `m`-th sixteenth.
+ ///
+ /// The base is pinned by `COLUMN_PERMUTATIONS_FOR_ENCODING` (see
+ /// `generate_sliding_column_permutation`). Under `STEADY_STATE_MODEL` the
steady-state byte
+ /// tables accept any base from `6` to `84` across both entropy and
average-length headers
+ /// within `HEADER_STATS_TOLERANCE`; below `6` the left edge starts to
matter, and beyond `84`
+ /// the 128-column right edge does (at base `85` the average length error
already reaches
+ /// `3.1e-14`; base `100` misses by `7e-10`).
+ const STEADY_STATE_C_OVER_K_BASE: f64 = 6.0;
+
+ /// Maximum Huffman codeword length, chosen so single-step lookup decoding
tables occupy
+ /// `2^12 = 4096` `u16` entries.
+ const MAX_CODE_LENGTH: usize = 12;
+
+ //
-------------------------------------------------------------------------
+ // 1. Reconstructed `columnProbabilities.ml`
+ //
-------------------------------------------------------------------------
+
+ /// Probability model for one cell of the coupon matrix after `N = lambda
* K` distinct items.
+ #[derive(Clone, Copy)]
+ enum Occupancy {
+ /// Finite sketch size `K`: a cell in 1-based column `col` stays `0`
with probability
+ /// `p_0 = (1 - 1 / (K * 2^col))^N`.
+ Binomial { k: f64 },
+ /// Limit `K -> inf` at fixed `lambda = N / K`: `p_0 = exp(-lambda *
2^-col)`.
+ Poisson,
+ }
+
+ impl Occupancy {
+ /// `ln(p_0)` for 1-based column `col` (`1..=128`) at density `lambda
= N / K`.
+ fn ln_zero_prob(self, lambda: f64, col: u8) -> f64 {
+ match self {
+ Occupancy::Binomial { k } => k * lambda * (-inv_pow2(col) /
k).ln_1p(),
+ Occupancy::Poisson => -lambda * inv_pow2(col),
+ }
+ }
+
+ /// Probability `q = 1 - p_0` that a cell in 1-based column `col` is
set.
+ fn one_prob(self, lambda: f64, col: u8) -> f64 {
+ -self.ln_zero_prob(lambda, col).exp_m1()
+ }
+
+ /// Probability `p_0` that a cell in 1-based column `col` is still `0`.
+ ///
+ /// Evaluated as `exp(...)` rather than `1.0 - one_prob(...)`:
`one_prob` cannot hold a
+ /// difference from `1.0` below the `2^-53` spacing there, so it
rounds to exactly `1.0`
+ /// once `p_0 <= 2^-54` (`f64::EPSILON / 4`) and the subtraction then
yields `0.0`. That
+ /// cancellation would misrank tiny surprise probabilities in
+ /// `generate_sliding_column_permutation`.
+ fn zero_prob(self, lambda: f64, col: u8) -> f64 {
+ self.ln_zero_prob(lambda, col).exp()
+ }
+
+ /// Expected coupon density `E[C] / K = sum_{col=1..=128} q(col)` of
the unclipped
+ /// 128-column FM85 matrix.
+ fn expected_c_over_k(self, lambda: f64) -> f64 {
+ (1..=128).map(|col| self.one_prob(lambda, col)).sum()
+ }
+
+ /// Inverts `expected_c_over_k(lambda) = target_c_over_k` by monotone
binary search.
+ fn solve_lambda(self, target_c_over_k: f64) -> f64 {
+ let mut lo = 0.0;
+ let mut hi = 1.0;
+ while self.expected_c_over_k(hi) < target_c_over_k {
+ hi *= 2.0;
+ }
+ for _ in 0..96 {
+ let mid = 0.5 * (lo + hi);
+ if self.expected_c_over_k(mid) < target_c_over_k {
+ lo = mid;
+ } else {
+ hi = mid;
+ }
+ }
+ 0.5 * (lo + hi)
+ }
+ }
+
+ /// Computes the 256-entry probability distribution for the 8-bit window
starting at 0-based
+ /// column `offset` at density `c_over_k` (`columnProbabilities.ml`).
+ ///
+ /// Within a single row, the 8 window columns `offset .. offset + 8`
(1-based
+ /// `offset + 1 ..= offset + 8`) are treated as independent Bernoulli
variables, giving
+ /// `P(byte) = prod_{bit=0..8} (q_bit if byte has bit set else p0_bit)`.
Independence is exact
+ /// in the Poisson model; with `Occupancy::Binomial` the marginals are
exact and the product
+ /// form is an approximation.
+ fn window_byte_probabilities(model: Occupancy, c_over_k: f64, offset: u8)
-> [f64; 256] {
+ let lambda = model.solve_lambda(c_over_k);
+ let mut p_one = [0.0; 8];
+ let mut p_zero = [0.0; 8];
+ for bit in 0..8_u8 {
+ let col_1based = offset + bit + 1;
+ p_one[bit as usize] = model.one_prob(lambda, col_1based);
+ p_zero[bit as usize] = model.zero_prob(lambda, col_1based);
+ }
+
+ let mut probs = [0.0; 256];
+ for (byte_val, slot) in probs.iter_mut().enumerate() {
+ let mut prob = 1.0;
+ for bit in 0..8 {
+ if ((byte_val >> bit) & 1) != 0 {
+ prob *= p_one[bit];
+ } else {
+ prob *= p_zero[bit];
+ }
+ }
+ *slot = prob;
+ }
+ probs
+ }
+
+ /// Computes the 65-symbol truncated dyadic geometric distribution for
+ /// `LENGTH_LIMITED_UNARY_ENCODING_TABLE65` (`columnProbabilities.ml`):
+ /// `P(s) = 2^{-(s+1)}` for `s in 0..64` and `P(64) = 2^{-64}`, which sums
to `1.0` and has
+ /// exact Shannon entropy `2 - 2^{-63}` bits (which rounds to `2.0` in
`f64`).
+ ///
+ /// The symbol is the column delta `x_delta` that the pair encoder writes
for each surprise
+ /// `(row, col)` pair (the row delta is Golomb-coded with a plain unary
high part instead).
+ /// The geometric law is the column distribution of a single coupon, and
"unary" describes the
+ /// shape of the resulting code: lengths `1, 2, 3, 4, 5, 7, 8, 8, 10, 10,
11, 12, ...` follow
+ /// the unary pattern until the 12-bit limit forces a redistribution.
+ fn unary65_probabilities() -> [f64; 65] {
+ let mut probs = [0.0; 65];
+ for (s, slot) in probs.iter_mut().enumerate().take(64) {
+ *slot = inv_pow2((s + 1) as u8);
+ }
+ probs[64] = inv_pow2(64);
+ probs
+ }
+
+ fn shannon_entropy(probs: &[f64]) -> f64 {
+ probs
+ .iter()
+ .filter(|&&p| p > 0.0)
+ .map(|&p| -p * p.log2())
+ .sum()
+ }
+
+ fn expected_code_length(probs: &[f64], table: &[u16]) -> f64 {
+ probs
+ .iter()
+ .zip(table.iter())
+ .map(|(&p, &entry)| p * ((entry >> 12) as f64))
+ .sum()
+ }
+
+ //
-------------------------------------------------------------------------
+ // 2. Reconstructed `generateHuffmanCodes.ml`
+ //
-------------------------------------------------------------------------
+
+ /// Generates a length-limited (`<= max_length`) canonical LSB-first
Huffman encoding table
+ /// (`generateHuffmanCodes.ml`), packing each symbol's entry as `(length
<< 12) | codeword`.
+ ///
+ /// How the algorithm was reverse-engineered from the static tables:
+ /// 1. Length-limited optimality (Larmore-Hirschberg Package-Merge, 1990):
symbols with tiny
+ /// probabilities such as `2^-64` are capped at length 12 while
strictly minimizing `sum_s
+ /// P(s) * len[s]` subject to Kraft's equality `sum_s 2^-len[s] = 1`.
In Package-Merge over
+ /// `max_length` levels, each level pairs adjacent items `(2k, 2k+1)`
from the previous level
+ /// and stably merges `[leaves, packages]` by non-decreasing weight,
breaking leaf ties by
+ /// ascending symbol index. Selecting the `2 * n - 2` lightest items at
the final level and
+ /// counting each symbol's leaf occurrences yields the optimal code
lengths. Exact weight
+ /// ties between a leaf and a package do occur (e.g. `P(62) = 2^-63 ==
P(63) + P(64)`), but
+ /// the tables do not identify a tie rule: ordering packages ahead of
leaves yields the same
+ /// code lengths for all 23 tables. Leaves go first here.
+ /// 2. Canonical LSB-first codeword assignment: sorting symbols by
`(len[s], s)` ascending,
+ /// assigning standard canonical MSB-first integers (`code <<= len -
prev_len`, then
+ /// incrementing), and bit-reversing the low `len` bits
(`reverse_bits() >> (16 - len)`) so
+ /// CPC's LSB-first bitstream writer can emit `codeword` directly
reproduces every codeword.
+ fn generate_length_limited_huffman_table(probs: &[f64], max_length: usize)
-> Vec<u16> {
+ let n = probs.len();
+ assert!(n >= 2 && max_length <= 15);
+
+ let mut leaves: Vec<(f64, Vec<usize>)> = probs
+ .iter()
+ .enumerate()
+ .map(|(s, &p)| (p, vec![s]))
+ .collect();
+ leaves.sort_by(|a, b| a.0.total_cmp(&b.0).then_with(||
a.1[0].cmp(&b.1[0])));
+
+ let mut current = leaves.clone();
+ for level in 0..max_length {
+ if level > 0 {
+ let mut packages = Vec::with_capacity(current.len() / 2);
+ for pair in current.chunks_exact(2) {
+ let mut syms = Vec::with_capacity(pair[0].1.len() +
pair[1].1.len());
+ syms.extend_from_slice(&pair[0].1);
+ syms.extend_from_slice(&pair[1].1);
+ packages.push((pair[0].0 + pair[1].0, syms));
+ }
+ let mut merged = Vec::with_capacity(leaves.len() +
packages.len());
+ merged.extend_from_slice(&leaves);
+ merged.extend(packages);
+ // Rust's `sort_by` is guaranteed stable, keeping `leaves`
ahead of `packages`
+ // whenever weights tie exactly.
+ merged.sort_by(|a, b| a.0.total_cmp(&b.0));
+ current = merged;
+ }
+ }
+
+ let mut lengths = vec![0_usize; n];
+ for item in current.iter().take(2 * n - 2) {
+ for &sym in &item.1 {
+ lengths[sym] += 1;
+ }
+ }
+
+ let mut order: Vec<usize> = (0..n).collect();
+ order.sort_by(|&a, &b| lengths[a].cmp(&lengths[b]).then_with(||
a.cmp(&b)));
+
+ let mut table = vec![0_u16; n];
+ let mut next_code = 0_u32;
+ let mut prev_len = 0_usize;
+ for sym in order {
+ let len = lengths[sym];
+ assert!((1..=max_length).contains(&len));
+ next_code <<= len - prev_len;
+ let msb_code = next_code as u16;
+ next_code += 1;
+ prev_len = len;
+
+ let lsb_code = msb_code.reverse_bits() >> (16 - len);
+ table[sym] = ((len as u16) << 12) | lsb_code;
+ }
+ assert_eq!(next_code, 1_u32 << prev_len, "Kraft sum must equal 1");
+ table
+ }
+
+ //
-------------------------------------------------------------------------
+ // 3. Reconstructed `generatePermutationsForSLIDING.ml`
+ //
-------------------------------------------------------------------------
+
+ /// Generates the 56-column encoding permutation for sliding-window `phase
= (2 * m + 1) / 32`
+ /// (`generatePermutationsForSLIDING.ml`).
+ ///
+ /// In `Sliding` mode (`c/k >= 3.375`), the 0-based window offset is
`floor(c/k - 2.375)`.
+ /// Outside the 8-bit window `[offset, offset + 7]`, a bit at `col <
offset` is surprising when
+ /// `0` (probability `p_0`), and a bit at `col >= offset + 8` is
surprising when `1`
+ /// (probability `q`). Rotating column indices via `canon = (col + 56 -
offset) % 64` places
+ /// post-window columns at `0 .. 56 - offset` and pre-window columns at
`56 - offset .. 56`.
+ /// Ranking the 56 canonical columns by descending surprise probability
(ties by index) assigns
+ /// shorter unary codes to more frequent surprise columns.
+ ///
+ /// What the 16 stored permutations identify:
+ /// * The base of `c/k = 6.0 + phase`. The base enters only through
`offset`, which equals the
+ /// base minus 3 below `phase = 3/8` and the base minus 2 above it. With
`p_0` computed as an
+ /// exponential, bases 5, 6, and 7 reproduce 6, 16, and 10 of the 16
phases.
+ /// * That `p_0` was computed without cancellation. Computing it as `1.0 -
q` reproduces 15 of
+ /// 16 phases for both base 6 and base 7, so the decisive datum is a
single comparison at
+ /// `phase = 19/32` (`offset = 4`): column 1 (`canon = 52`) has `p_0 ≈
2.22e-17` and must rank
+ /// ahead of 1-based column 62 (`canon = 49`, `q ≈ 1.66e-17`), whereas
`1.0 - q` rounds `p_0`
+ /// to `0.0` and ranks it last.
+ /// * Nothing about `K`: every `K` from `2^8` to the Poisson limit yields
identical
+ /// permutations.
+ fn generate_sliding_column_permutation(phase_index: usize) -> [u8; 56] {
+ let model = STEADY_STATE_MODEL;
+ let phase = (2 * phase_index + 1) as f64 / 32.0;
+ let c_over_k = STEADY_STATE_C_OVER_K_BASE + phase;
+ let offset = (c_over_k - 2.375).floor() as usize;
+ let lambda = model.solve_lambda(c_over_k);
+
+ let mut surprise_prob = [0.0; 56];
+ for col in 0..64_usize {
+ if (offset..offset + 8).contains(&col) {
+ continue;
+ }
+ let canon = (col + 56 - offset) % 64;
+ let col_1based = (col + 1) as u8;
+ surprise_prob[canon] = if col < offset {
+ model.zero_prob(lambda, col_1based)
+ } else {
+ model.one_prob(lambda, col_1based)
+ };
+ }
+
+ let mut cols_by_prob: [usize; 56] = from_fn(|i| i);
+ cols_by_prob.sort_by(|&a, &b| {
+ surprise_prob[b]
+ .total_cmp(&surprise_prob[a])
+ .then_with(|| a.cmp(&b))
+ });
+
+ let mut encode_perm = [0_u8; 56];
+ for (rank, &canon) in cols_by_prob.iter().enumerate() {
+ encode_perm[canon] = rank as u8;
+ }
+ encode_perm
+ }
+
+ #[test]
+ fn unary_encoding_table65() {
+ let probs = unary65_probabilities();
+ let generated = generate_length_limited_huffman_table(&probs,
MAX_CODE_LENGTH);
+
+ assert_that!(shannon_entropy(&probs), near(2.0, 1e-15));
+ assert_that!(
+ expected_code_length(&probs, &generated),
+ near(2.02490234375, 1e-15),
+ );
+ assert_that!(
+ generated,
+ container_eq(LENGTH_LIMITED_UNARY_ENCODING_TABLE65),
+ );
+ }
+
+ /// `(entropy, avg_length)` printed by `generateHuffmanCodes.ml` above
each table of
+ /// `ENCODING_TABLES_FOR_HIGH_ENTROPY_BYTE`, copied verbatim from the
header comments.
+ ///
+ /// These 20-digit values are the only continuous output of the original
generator that
+ /// survived, so they are the evidence that discriminates between
occupancy models: the
+ /// codewords alone are reproduced by a wide range of models (e.g. every
`K >= 2^16` for the
+ /// midrange tables), whereas the entropies resolve differences of
~`1e-14`.
+ #[allow(clippy::excessive_precision)]
+ const RECORDED_HEADER_STATS: [(f64, f64); 22] = [
+ (4.4619200780464778333, 4.5415773046232610355), // table 0
+ (4.4574755684414029133, 4.5336306265208552446), // table 1
+ (4.4520619712441886762, 4.5253989110544479146), // table 2
+ (4.4457680500675866853, 4.5181192844586535173), // table 3
+ (4.4386754570568340839, 4.5071584786605640716), // table 4
+ (4.4308578632493116345, 4.4996166821663301505), // table 5
+ (4.4310364988500126060, 4.5051134111084252254), // table 6
+ (4.4417871821766841123, 4.5206419191518980583), // table 7
+ (4.4505873338397474726, 4.5270058771550303334), // table 8
+ (4.4575203029748040606, 4.5315465600684730063), // table 9
+ (4.4626765653088611430, 4.5373141251902122661), // table 10
+ (4.4661524304421691411, 4.5443750890419041255), // table 11
+ (4.4680486273043946710, 4.5521643785256946657), // table 12
+ (4.4684687952964843305, 4.5509169030369793774), // table 13
+ (4.4675179140944036860, 4.5477235350841240802), // table 14
+ (4.4653007097343397902, 4.5480722016259509388), // table 15
+ (2.1627885076675394949, 2.2704182849800043087), // table 16
+ (2.9553294756640680063, 3.0766035704232641557), // table 17
+ (3.5218672531711128215, 3.6153551492375441967), // table 18
+ (3.9228873257934386842, 3.9989687586992346269), // table 19
+ (4.1937026483207340277, 4.2809622975207295426), // table 20
+ (4.3601926041863263706, 4.4384101723259572481), // table 21
+ ];
+
+ /// Tolerance for matching `RECORDED_HEADER_STATS`: a few dozen `f64`
ULPs, two orders of
+ /// magnitude below the deviation of the rejected base-6 finite-`K`
steady-state model
+ /// (`6.1e-12`) and the alternative midrange models (`>= 2.5e-11` away
from `K = 2^32`).
+ const HEADER_STATS_TOLERANCE: f64 = 3e-14;
+
+ #[test]
+ fn high_entropy_byte_encoding_tables() {
+ for (idx, &(entropy, avg_length)) in
RECORDED_HEADER_STATS.iter().enumerate() {
+ let probs = if idx < 16 {
+ // Tables 0..16: steady-state sliding window at `c/k = 6.0 +
(2*m + 1)/32`,
+ // `offset = floor(c/k - 2.375)` (`3` for `m < 6`, `4` for `m
>= 6`).
+ let phase = (2 * idx + 1) as f64 / 32.0;
+ let c_over_k = STEADY_STATE_C_OVER_K_BASE + phase;
+ let offset = (c_over_k - 2.375).floor() as u8;
+ window_byte_probabilities(STEADY_STATE_MODEL, c_over_k, offset)
+ } else {
+ // Tables 16..22: midrange pinned window (`offset = 0`) at
`c/k = (2*m + 3) / 6`.
+ let m = idx - 16;
+ window_byte_probabilities(MIDRANGE_MODEL, (2 * m + 3) as f64 /
6.0, 0)
+ };
+ let table = generate_length_limited_huffman_table(&probs,
MAX_CODE_LENGTH);
+
+ assert_that!(
+ shannon_entropy(&probs),
+ near(entropy, HEADER_STATS_TOLERANCE)
+ );
+ assert_that!(
+ expected_code_length(&probs, &table),
+ near(avg_length, HEADER_STATS_TOLERANCE),
+ );
+ assert_that!(
+ table,
+ container_eq(ENCODING_TABLES_FOR_HIGH_ENTROPY_BYTE[idx])
+ );
+ }
+ }
+
+ #[test]
+ fn sliding_column_permutations() {
+ for phase_idx in 0..16 {
+ let generated = generate_sliding_column_permutation(phase_idx);
+ assert_that!(
+ generated.as_slice(),
+ container_eq(COLUMN_PERMUTATIONS_FOR_ENCODING[phase_idx]),
+ );
+ }
+ }
+
+ //
-------------------------------------------------------------------------
+ // 4. Decoding table inversions (`fm85Compression.c` /
`CompressionData.java`)
+ //
-------------------------------------------------------------------------
#[test]
fn decoding_tables() {
diff --git a/datasketches/src/cpc/estimator.rs
b/datasketches/src/cpc/estimator.rs
index 20e9866..c171a04 100644
--- a/datasketches/src/cpc/estimator.rs
+++ b/datasketches/src/cpc/estimator.rs
@@ -427,3 +427,487 @@ fn icon_estimate(lg_k: u8, num_coupons: u32) -> f64 {
let result = c * factor * term;
if result >= c { result } else { c }
}
+
+#[cfg(test)]
+mod tests {
+ // Reference ICON estimator, least-squares polynomial reconstruction, and
confidence-table
+ // verification.
+ //
+ // Provenance in Kevin J. Lang's original FM85 / CPC implementation:
+ // 1. `iconEstimator.c` / `icon_estimator.hpp` / `IconEstimatorTest.java`:
Defines the exact
+ // FM85 ICON (Inverted Coupon Number) estimator by numerically
inverting the expected coupon
+ // count `E[C | N] = K * sum_{col=1..=128} (1 - (1 - 1/(K*2^col))^N)`,
together with a
+ // validation sweep comparing `icon_estimate` against
`exact_icon_estimate`.
+ // 2. `icon_estimator.hpp` / `IconPolynomialCoefficients.java`: only the
fitted degree-19
+ // coefficient matrix `ICON_POLYNOMIAL_COEFFICIENTS` and the constants
`0.7940236163830469`,
+ // `2.0`, and `66.774757` were checked into C/C++/Java; the offline
fitting script was not.
+ // What `icon_estimate`'s evaluation formula, the Maclaurin series of
`N(C) / C`, and the
+ // error profile beyond `5.7 * K` reveal about that script is
documented next to
+ // `fit_icon_polynomial_row` below, including what remains unknown.
+ // 3. `cpc_confidence.hpp` / `CpcConfidence.java` (offline Monte Carlo
characterization):
+ // Defines the theoretical asymptotic relative standard error constants
(`ICON_ERROR_CONSTANT
+ // = ln 2` and `HIP_ERROR_CONSTANT = sqrt((ln 2) / 2)`) alongside the
empirical
+ // ~1,000,000-trial quantile tables `ICON_{LOW,HIGH}_SIDE_DATA` and
+ // `HIP_{LOW,HIGH}_SIDE_DATA` measured at `N = 1000 * K` for `lg_k =
4..=14`.
+
+ use std::array::from_fn;
+ use std::f64::consts::PI;
+ use std::f64::consts::SQRT_2;
+
+ use googletest::assert_that;
+ use googletest::prelude::gt;
+ use googletest::prelude::lt;
+ use googletest::prelude::near;
+
+ use super::*;
+ use crate::common::inv_pow2::inv_pow2;
+
+ const EULER_MASCHERONI: f64 = 0.577_215_664_901_532_9;
+ const ICON_CUBIC_PRECONDITIONER: f64 = 66.774757;
+
+ //
-------------------------------------------------------------------------
+ // 1. Exact FM85 ICON estimator (`IconEstimatorTest.java` / `fm85`)
+ //
-------------------------------------------------------------------------
+
+ const ICON_INVERSION_TOLERANCE: f64 = 1.0e-15;
+
+ /// Precomputes `ln(1 - 1 / (K * 2^col))` for 1-based `col = 1..=128` at
fixed `kf`, matching
+ /// `qnj` in `IconEstimatorTest.java` bit-for-bit while avoiding repeated
`ln_1p` evaluations
+ /// inside the binary-search inner loop.
+ fn precompute_col_ln1p(kf: f64) -> [f64; 128] {
+ from_fn(|idx| (-inv_pow2((idx + 1) as u8) / kf).ln_1p())
+ }
+
+ /// Expected coupon count `E[C | N] = K * sum_{col=1..=128} (1 - (1 -
1/(K*2^col))^N)` in the
+ /// unclipped 128-column FM85 coupon matrix (`exactCofN` in
`IconEstimatorTest.java`).
+ fn exact_coupon_count_with_ln1p(kf: f64, col_ln1p: &[f64; 128], nf: f64)
-> f64 {
+ let mut total = 0.0;
+ // Iterating from 128 down to 1 accumulates tiny tail probabilities
first before large
+ // head probabilities, preserving full `f64` summation precision.
+ for &tmp2 in col_ln1p.iter().rev() {
+ total += -f64::exp_m1(nf * tmp2);
+ }
+ kf * total
+ }
+
+ /// Exact ICON estimate `N_hat` solving `exact_coupon_count(kf, N_hat) =
target_c` by bracket
+ /// doubling and binary search (`exactIconEstimator` in
`IconEstimatorTest.java`).
+ fn exact_icon_estimate(kf: f64, target_c: f64) -> f64 {
+ if target_c == 0.0 || target_c == 1.0 {
+ return target_c;
+ }
+ let col_ln1p = precompute_col_ln1p(kf);
+ exact_icon_estimate_with_ln1p(kf, &col_ln1p, target_c)
+ }
+
+ fn exact_icon_estimate_with_ln1p(kf: f64, col_ln1p: &[f64; 128], target_c:
f64) -> f64 {
+ if target_c == 0.0 || target_c == 1.0 {
+ return target_c;
+ }
+ let mut lo = target_c;
+ let mut hi = 2.0 * target_c;
+ while exact_coupon_count_with_ln1p(kf, col_ln1p, hi) <= target_c {
+ lo = hi;
+ hi *= 2.0;
+ }
+ for _ in 0..100 {
+ let mid = lo + 0.5 * (hi - lo);
+ if (hi - lo) / mid < ICON_INVERSION_TOLERANCE || mid <= lo || mid
>= hi {
+ return mid;
+ }
+ let mid_c = exact_coupon_count_with_ln1p(kf, col_ln1p, mid);
+ if mid_c == target_c {
+ return mid;
+ } else if mid_c < target_c {
+ lo = mid;
+ } else {
+ hi = mid;
+ }
+ }
+ 0.5 * (lo + hi)
+ }
+
+ //
-------------------------------------------------------------------------
+ // 2. Reconstructed generator for `ICON_POLYNOMIAL_COEFFICIENTS`
+ //
-------------------------------------------------------------------------
+ //
+ // What the stored coefficients reveal about the offline fit, and what
they do not:
+ //
+ // * Pre-conditioned target function: for `2 <= C <= threshold * K`,
`icon_estimate` returns
+ // `C*(1+(C/K)^3/66.774757)*P(x)` with `x = C / (2 * K)`, so row `lg_k`
of
+ // `ICON_POLYNOMIAL_COEFFICIENTS` is a degree-19 polynomial
approximating the ratio
+ // `g_K(x)=N_exact/(C*(1+(C/K)^3/66.774757))`. Without the cubic
pre-conditioner, `N_exact/C`
+ // grows by more than 8x over `C/K` in `[0, 6]` as it transitions into
`0.794*K*2^(C/K)`; with
+ // it, `g_K` stays within `[0.89, 1.48]`, and the stored rows reach a
maximum relative error
+ // of about `2e-7` on `[2, threshold * K]`.
+ //
+ // The argument `x = C / (2 * K)` maps `C in [0, 6 * K]` onto `[0, 3]`
instead of `[0, 6]`,
+ // keeping `x^19` bounded by `3^19 ≈ 1.16e9` rather than `6^19 ≈
6.09e14`. Where the value
+ // `66.774757` comes from is not known.
+ //
+ // * Maclaurin series check on the leading columns: For `K -> inf` and
`lambda = N / K -> 0`,
+ // `E[C] / K = sum_{j>=1} (1 - exp(-lambda * 2^-j)) = lambda -
lambda^2/6 + lambda^3/42 -
+ // ...`. Series inversion yields `N / C = 1 + (C/K)/6 + 2*(C/K)^2/63 +
... = 1 + x/3 +
+ // 8*x^2/63 + ...`. Dividing by `1 + 8*x^3 / 66.774757` preserves the
degree-0..2 Maclaurin
+ // terms, so columns 0, 1, 2 of `ICON_POLYNOMIAL_COEFFICIENTS` should
approximate `1`, `1/3`,
+ // and `8/63`. They do so only approximately: `a_0` approaches `1` like
`1 - O(1 / K)`, but
+ // `a_1` wanders at the `1e-5` level and `a_2` plateaus near `0.1267`
for `lg_k >= 8` instead
+ // of `0.12698`, because least squares optimizes uniform accuracy on
`[0, 3]` rather than
+ // Taylor accuracy at `0`.
+ //
+ // * Fitting domain `C in [1, 6 * K]` (`x in (0, 3]`): past the runtime
threshold (`5.6 * K` or
+ // `5.7 * K`) the stored rows keep a relative error below `5e-7` against
`exact_icon_estimate`
+ // up to `C = 6 * K`, and diverge within a few percent beyond it (at
`6.25 * K` every row is
+ // off by `4e-6` to `1.3e-4`). The end is sharp for small `K`: `lg_k =
4` has at most `8.7e-8`
+ // up to `C = 96` and `2.2e-6` at `C = 97`. For larger `lg_k` an integer
step is too fine to
+ // locate it: `lg_k = 8` is still at `-6.6e-8` at `C = 6 * K + 1`. The
end at exactly `6 * K`
+ // rests on the grid experiments for `lg_k <= 7` below. Why the fit
extends past the runtime
+ // threshold, e.g. as a guard band against endpoint oscillation, is not
documented.
+ //
+ // * Sample grid for `lg_k <= 7` (`6 * K <= 768`): ordinary least squares
on `g_K` over every
+ // integer `C = 1 ..= 6 * K` reproduces the stored coefficients within
`0.07%` to `1.4%` and
+ // the stored polynomial to `< 2e-8` relative prediction difference,
although the unscaled
+ // monomial basis on these grids has a 2-norm condition number of about
`1e17` (`1e14` after
+ // scaling its columns). The agreement is discriminating: moving either
end of the grid by one
+ // integer, dropping `C = 1` (where the exact estimator returns `N = 1`
by definition), or
+ // halving the grid spacing makes the coefficient agreement at least 4x
(`lg_k = 6`) to 59x
+ // (`lg_k = 5`) worse. This strongly supports the grid but does not
establish the original
+ // procedure: the weighting and the numerics are not identified, and a
relative-error-weighted
+ // fit agrees slightly better (`0.63%`) at `lg_k = 4`.
+ //
+ // * Sample grid for `lg_k >= 8`: not identified. A discontinuity between
`lg_k = 7` and `8`
+ // (`a_2`: `0.12534 -> 0.12667`; `a_19`: `4.28e-5 -> 2.91e-5`) and the
irregular high-order
+ // coefficients afterwards suggest that the procedure changed, plausibly
to a sampled grid,
+ // but neither exhaustive integer grids nor the dense-then-geometric
grid of
+ // `icon_fitting_grid` reproduce the stored coefficients (deviations of
14% to 65%). For these
+ // rows the test only demonstrates functional equivalence: a fit of the
same form attains the
+ // same `~1e-7` accuracy.
+
+ /// Solves the overdetermined linear least-squares problem `min_a ||V * a
- y||_2` (`m >= n`)
+ /// via Householder QR factorization without external linear-algebra
dependencies.
+ fn solve_least_squares_qr(mut v: Vec<f64>, mut y: Vec<f64>, m: usize, n:
usize) -> Vec<f64> {
+ assert!(m >= n && v.len() == m * n && y.len() == m);
+
+ for k in 0..n {
+ let mut norm_sq = 0.0;
+ for row in k..m {
+ let val = v[row * n + k];
+ norm_sq += val * val;
+ }
+ let norm = norm_sq.sqrt();
+ if norm == 0.0 {
+ continue;
+ }
+
+ let v_kk = v[k * n + k];
+ let alpha = if v_kk >= 0.0 { -norm } else { norm };
+ let u0 = v_kk - alpha;
+
+ let mut u_norm_sq = u0 * u0;
+ for row in (k + 1)..m {
+ let val = v[row * n + k];
+ u_norm_sq += val * val;
+ }
+ let beta = 2.0 / u_norm_sq;
+
+ v[k * n + k] = alpha;
+ for col in (k + 1)..n {
+ let mut dot = u0 * v[k * n + col];
+ for row in (k + 1)..m {
+ dot += v[row * n + k] * v[row * n + col];
+ }
+ let scale = beta * dot;
+ v[k * n + col] -= scale * u0;
+ for row in (k + 1)..m {
+ v[row * n + col] -= scale * v[row * n + k];
+ }
+ }
+
+ let mut dot_y = u0 * y[k];
+ for row in (k + 1)..m {
+ dot_y += v[row * n + k] * y[row];
+ }
+ let scale_y = beta * dot_y;
+ y[k] -= scale_y * u0;
+ for row in (k + 1)..m {
+ y[row] -= scale_y * v[row * n + k];
+ }
+ }
+
+ let mut coeffs = vec![0.0; n];
+ for i in (0..n).rev() {
+ let mut sum = y[i];
+ for j in (i + 1)..n {
+ sum -= v[i * n + j] * coeffs[j];
+ }
+ coeffs[i] = sum / v[i * n + i];
+ }
+ coeffs
+ }
+
+ /// Generates the sample grid of coupon counts `C in [1, 6 * K]` for
fitting row `lg_k`.
+ ///
+ /// For `lg_k <= 7` this is the exhaustive integer grid that reproduces
the stored
+ /// coefficients. For `lg_k >= 8` the original grid is unknown; the
dense-then-geometric grid
+ /// below is an assumption that reproduces the accuracy of the stored
rows, not their
+ /// coefficients.
+ fn icon_fitting_grid(lg_k: usize) -> Vec<u64> {
+ let k = 1_u64 << lg_k;
+ let max_c = 6 * k;
+ if lg_k <= 7 {
+ (1..=max_c).collect()
+ } else {
+ // Assumed grid: dense small integers, then 4% geometric steps up
to `6 * K`.
+ let mut grid = Vec::with_capacity(512);
+ let mut c = 1_u64;
+ while c < max_c {
+ grid.push(c);
+ c = if c < 64 {
+ c + 1
+ } else {
+ (c + 1).max((1040 * c) / 1000)
+ };
+ }
+ grid.push(max_c);
+ grid
+ }
+ }
+
+ /// Fits the 20 degree-19 polynomial coefficients for `lg_k` by least
squares against
+ /// `exact_icon_estimate` on `C in [1, 6 * K]` (see `icon_fitting_grid`
for which rows this
+ /// reproduces coefficient by coefficient).
+ fn fit_icon_polynomial_row(lg_k: usize) -> Vec<f64> {
+ let kf = (1_u64 << lg_k) as f64;
+ let col_ln1p = precompute_col_ln1p(kf);
+ let grid = icon_fitting_grid(lg_k);
+ let m = grid.len();
+ let n = ICON_POLYNOMIAL_NUM_COEFFICIENTS;
+
+ let mut vandermonde = vec![0.0; m * n];
+ let mut target = vec![0.0; m];
+
+ for (row, &c_int) in grid.iter().enumerate() {
+ let cf = c_int as f64;
+ let n_exact = exact_icon_estimate_with_ln1p(kf, &col_ln1p, cf);
+ let ratio = cf / kf;
+ let precond = 1.0 + (ratio * ratio * ratio) /
ICON_CUBIC_PRECONDITIONER;
+ target[row] = n_exact / (cf * precond);
+
+ let x = cf / (2.0 * kf);
+ let mut x_pow = 1.0;
+ for col in 0..n {
+ vandermonde[row * n + col] = x_pow;
+ x_pow *= x;
+ }
+ }
+
+ solve_least_squares_qr(vandermonde, target, m, n)
+ }
+
+ #[test]
+ fn exact_icon_estimator_matches_approximation() {
+ for lg_k in ICON_MIN_LOG_K..=ICON_MAX_LOG_K {
+ let lg_k_u8 = lg_k as u8;
+ let k = 1_u64 << lg_k;
+ let kf = k as f64;
+
+ assert_eq!(icon_estimate(lg_k_u8, 0), 0.0);
+ assert_eq!(icon_estimate(lg_k_u8, 1), 1.0);
+
+ // Verify strict monotonicity across the polynomial-to-exponential
splice threshold
+ // (`5.7 * K` for `lg_k < 14`, `5.6 * K` for `lg_k >= 14`).
+ let threshold_factor = if lg_k < 14 { 5.7 } else { 5.6 };
+ let splice_c = (threshold_factor * kf).floor() as u32;
+ let mut prev_est = icon_estimate(lg_k_u8, splice_c - 2);
+ for c in (splice_c - 1)..=(splice_c + 2) {
+ let est = icon_estimate(lg_k_u8, c);
+ assert_that!(est, gt(prev_est));
+ prev_est = est;
+ }
+
+ // Geometric sweep from `C = 2` into the exponential regime (`60 *
K`), matching the
+ // characterization sweep in `IconEstimatorTest.java`.
+ let max_c = (60 * k).min(u32::MAX as u64);
+ let mut c = 2_u64;
+ while c <= max_c {
+ let exact = exact_icon_estimate(kf, c as f64);
+ let approx = icon_estimate(lg_k_u8, c as u32);
+ let rel_err = ((approx - exact) / exact).abs();
+ // In the polynomial region (`<= threshold * K`) the stored
rows stay below
+ // `2.1e-7` on a dense sweep over every `lg_k`.
+ //
+ // In the exponential region (`> threshold * K`) two effects
add up. The finite-`K`
+ // correction makes the Poisson-based approximation
overestimate `N` by about
+ // `1 / (2 * K * lambda)` with `lambda = N / K`; this decays
with `C` and peaks at
+ // the splice point, where `lambda ≈ 41.3` gives `1 / (82.6 *
K)`. The
+ // `1.0 / (80 * k)` bound in
`IconEstimatorTest::quickIconEstimatorTest` matches
+ // this peak with a small margin. For large `K` the periodic
term of FM85 theory
+ // dominates instead, with relative amplitude `1.09e-6`; the
dense-sweep maximum
+ // for `lg_k >= 14` is `1.53e-6`.
+ let tol = if (c as f64) <= threshold_factor * kf {
+ 3e-7
+ } else {
+ (2.5e-6_f64).max(1.0 / (80.0 * kf))
+ };
+ assert_that!(rel_err, lt(tol));
+
+ c = if c < 32 {
+ c + 1
+ } else {
+ (c + 1).max((125 * c) / 100)
+ };
+ }
+ }
+ }
+
+ #[test]
+ fn icon_exponential_constant_matches_theory() {
+ // The coefficient used at runtime, read back from the production
function.
+ let runtime_constant = icon_exponential_approximation(1.0, 0.0);
+
+ // Asymptotic FM85 theory (Mellin transform of the harmonic sum `E[C]
/ K`):
+ // `E[C]/K = log2(N/K) + gamma/ln(2) - 1/2 + P(log2(N/K)) + o(1)`,
where `P` is 1-periodic
+ // and `ln(2) * P` has the fundamental amplitude `a = 2 *
|Gamma(2*pi*i / ln 2)|`, about
+ // `1.09e-6`. Hence `N = D * K * 2^(C/K) * exp(-ln(2) * P)`, where the
closed form
+ // `D = sqrt(2) * exp(-gamma) = 0.7940236163832829` differs from the
runtime constant by
+ // `2.4e-13`.
+ //
+ // The approximation `A * K * 2^(C/K)` has relative error `(A / D) *
exp(ln(2) * P) - 1`.
+ // Choosing `A` so that this error averages to zero over a period of
`C / K` gives
+ // `A = D / <exp(ln(2) * P)> = D * (1 - a^2 / 4)` up to `O(a^3)`, where
+ // `a^2 / 4 = |Gamma(i * y)|^2 = pi / (y * sinh(pi * y))` with `y = 2
* pi / ln 2`. This
+ // value rounds to the runtime constant, which explains its last
digits; whether the
+ // original fitting script used this criterion is not known.
+ let d = SQRT_2 * (-EULER_MASCHERONI).exp();
+ let y = 2.0 * PI / LN_2;
+ let zero_mean_error_constant = d * (1.0 - PI / (y * (PI * y).sinh()));
+ assert_that!(runtime_constant, near(zero_mean_error_constant, 3e-16));
+
+ // The same criterion evaluated numerically: the harmonic mean of
`N_exact / (K * 2^(C/K))`
+ // over one period of `C / K`. At `C / K in [20, 21)` the finite-`K`
bias
+ // `1 / (2 * K * lambda)` is below `2e-16` for `K = 2^32`, and the
tolerance separates this
+ // criterion from `D` (`2.4e-13` away) and from the arithmetic mean
(`4.7e-13` away).
+ let kf = (1_u64 << 32) as f64;
+ let samples = 32;
+ let mut inverse_ratio_sum = 0.0;
+ for m in 0..samples {
+ let c_over_k = 20.0 + (m as f64 + 0.5) / (samples as f64);
+ let n_exact = exact_icon_estimate(kf, c_over_k * kf);
+ inverse_ratio_sum += kf * 2.0_f64.powf(c_over_k) / n_exact;
+ }
+ let harmonic_mean = samples as f64 / inverse_ratio_sum;
+ assert_that!(runtime_constant, near(harmonic_mean, 1e-14));
+ }
+
+ #[test]
+ fn reconstruct_icon_polynomial_coefficients() {
+ // The highest-`lg_k` stored row (`lg_k = 26`) is consistent with the
Maclaurin series
+ // `N / C = 1 + (1/3)*x + (8/63)*x^2 + ...` (`x = C / (2 * K)`) only
up to the bias of a
+ // least-squares fit on `[0, 3]`: the stored `a_0`, `a_1`, `a_2`
differ from the series by
+ // `2.9e-9`, `5.0e-6`, and `3.4e-4`, and `a_2` does not converge with
growing `lg_k`.
+ let last_row_start = ICON_POLYNOMIAL_NUM_COEFFICIENTS *
(ICON_MAX_LOG_K - ICON_MIN_LOG_K);
+ assert_that!(
+ ICON_POLYNOMIAL_COEFFICIENTS[last_row_start],
+ near(1.0, 1e-7)
+ );
+ assert_that!(
+ ICON_POLYNOMIAL_COEFFICIENTS[last_row_start + 1],
+ near(1.0 / 3.0, 1e-5),
+ );
+ assert_that!(
+ ICON_POLYNOMIAL_COEFFICIENTS[last_row_start + 2],
+ near(8.0 / 63.0, 4e-4),
+ );
+
+ for lg_k in ICON_MIN_LOG_K..=ICON_MAX_LOG_K {
+ let fitted = fit_icon_polynomial_row(lg_k);
+ let stored_start = ICON_POLYNOMIAL_NUM_COEFFICIENTS * (lg_k -
ICON_MIN_LOG_K);
+ let stored = &ICON_POLYNOMIAL_COEFFICIENTS
+ [stored_start..stored_start +
ICON_POLYNOMIAL_NUM_COEFFICIENTS];
+
+ if lg_k <= 7 {
+ // On `lg_k <= 7`, the exact exhaustive integer grid `C = 1
..= 6 * K` reproduces
+ // `a_0` to `< 1e-6`, `a_1` to `< 2e-5`, and all 20 monomials
within `2.5%`.
+ // Closer agreement is not expected: the unscaled degree-19
monomial basis on these
+ // grids is ill-conditioned (2-norm condition number `~1e17`),
so tiny differences
+ // in the target values move the high-degree coefficients by
percents while leaving
+ // `P(x)` invariant to `< 2e-8`.
+ assert_that!(fitted[0], near(stored[0], 1e-6));
+ assert_that!(fitted[1], near(stored[1], 2e-5));
+ for deg in 0..ICON_POLYNOMIAL_NUM_COEFFICIENTS {
+ let rel_diff = ((fitted[deg] - stored[deg]) /
stored[deg]).abs();
+ assert_that!(rel_diff, lt(0.025));
+ }
+ }
+
+ // Across every `lg_k = 4..=26`, verify that the fitted polynomial
agrees with both
+ // the checked-in `ICON_POLYNOMIAL_COEFFICIENTS` row and
`exact_icon_estimate`
+ // throughout the active evaluation interval `[2, threshold * K]`.
For `lg_k >= 8` this
+ // shows functional equivalence only; the coefficients themselves
are not reproduced.
+ let k = 1_u64 << lg_k;
+ let kf = k as f64;
+ let threshold_factor = if lg_k < 14 { 5.7 } else { 5.6 };
+ let max_active_c = (threshold_factor * kf).floor() as u64;
+
+ let pred_vs_stored_tol = if lg_k <= 7 { 2e-8 } else { 4e-7 };
+ for step in 0..=40 {
+ let c_int = 2 + ((max_active_c - 2) * step) / 40;
+ let cf = c_int as f64;
+ let x = cf / (2.0 * kf);
+ let ratio = cf / kf;
+ let precond = 1.0 + (ratio * ratio * ratio) /
ICON_CUBIC_PRECONDITIONER;
+
+ let n_fitted = cf * precond * evaluate_polynomial(&fitted, 0,
fitted.len(), x);
+ let n_stored = cf * precond * evaluate_polynomial(stored, 0,
stored.len(), x);
+ let n_exact = exact_icon_estimate(kf, cf);
+
+ let rel_vs_stored = ((n_fitted - n_stored) / n_stored).abs();
+ let rel_vs_exact = ((n_fitted - n_exact) / n_exact).abs();
+ assert_that!(rel_vs_stored, lt(pred_vs_stored_tol));
+ assert_that!(rel_vs_exact, lt(4e-7));
+ }
+ }
+ }
+
+ //
-------------------------------------------------------------------------
+ // 3. Confidence interval constants & empirical tables
(`cpc_confidence.hpp`)
+ //
-------------------------------------------------------------------------
+
+ #[test]
+ fn confidence_constants_and_bounds() {
+ // Both asymptotic (`K -> inf`) relative standard errors, scaled by
`sqrt(K)`, follow from
+ // the Poisson model of the coupon matrix:
+ // - ICON: cells are independent, so `Var(C) ≈ K * sum_j q_j * (1 -
q_j)`. Averaged over a
+ // period, the sum equals `(1 / ln 2) * int_0^inf (exp(-u) -
exp(-2u)) / u du = 1`
+ // (Frullani), so `sd(C) ≈ sqrt(K)`; since `N_hat` grows like
`2^(C/K)`, the relative
+ // error is `ln(2) / sqrt(K)`.
+ // - HIP: a new item changes the sketch with probability `p ≈ 1 /
(lambda * ln 2)`, and the
+ // HIP variance `int_0^n (1/p - 1) dm ≈ n^2 * ln(2) / (2 * K)` gives
`sqrt(ln(2) / 2)`.
+ // `HIP_ERROR_CONSTANT` is spelled out as a decimal literal, so check
it against that form.
+ assert_that!(HIP_ERROR_CONSTANT, near((LN_2 / 2.0).sqrt(), 1e-16));
+
+ // For `lg_k <= 14` the bounds use the Monte Carlo tables instead.
Each entry is
+ // `10_000 * sqrt(K) * eps / kappa`, where `eps` is the one-sided
`Phi(-kappa)` tail
+ // quantile of `estimate / N - 1` (high side, used by the lower bound)
or of
+ // `1 - estimate / N` (low side, used by the upper bound) at `N = 1000
* K`. Being random
+ // measurements, the tables can only be re-measured statistically, not
regenerated, and
+ // this test does not verify their values or the coverage of the
resulting intervals. It
+ // checks only how the bounds use them: every bound brackets the
estimate, respects `C`,
+ // and widens strictly as `kappa` grows.
+ for lg_k in 4..=16_u8 {
+ let c = 3 * (1_u32 << lg_k);
+ let icon_est = estimate(true, 0.0, lg_k, c);
+ for (merge_flag, hip_est) in [(true, 0.0), (false, icon_est)] {
+ let mut prev_lb = icon_est;
+ let mut prev_ub = icon_est;
+ for kappa in [NumStdDev::One, NumStdDev::Two,
NumStdDev::Three] {
+ let lb = lower_bound(merge_flag, hip_est, lg_k, c, kappa);
+ let ub = upper_bound(merge_flag, hip_est, lg_k, c, kappa);
+ assert!(lb >= c as f64 && lb < prev_lb && ub > prev_ub);
+ prev_lb = lb;
+ prev_ub = ub;
+ }
+ }
+ }
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]