FA-73022 / Probabilistic sketches / Member archive

HyperLogLog merge across precisions: fold index uses the low bits · case 02

Registers are merged into slots that the lower-precision sketch would never have chosen.

Member previewVariant 2 · 3 implementations · 7 checks per implementation

Case contract

Input {a, b}, each {p, regs}. Both sketches are folded to q = min precision. Folding from p to q with d = p - q maps register j to j >> d; if the low d bits of j are non-zero they become the leading bits of the new remainder, giving rank d - bitlen(low) + 1, otherwise the rank is r + d. Empty registers contribute nothing. The merged sketch is the element-wise maximum. Return [q, regs].

Why this case matters

Merging distinct-count sketches produced with different precision settings requires re-deriving ranks, not just re-indexing registers.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
fold p5 into p3	`[3, [6, 2, 3, 3, 7, 2, 1, 2]]`	`[3, [3, 2, 3, 5, 5, 7, 6, 3]]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

Member access is invitation-based. Sign in with your invited account to inspect the sources.