FA-73030 / Probabilistic sketches / Member archive

HyperLogLog merge across precisions: displaced-bit rank counts from the wrong end · case 05

Folded ranks grow with the value of displaced bits rather than with leading zeros.

Member previewVariant 5 · 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 p6 into p3	`[3, [3, 4, 4, 7, 3, 8, 3, 3]]`	`[3, [1, 4, 4, 7, 3, 8, 3, 2]]`	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.