HyperLogLog Bias Correction

Problem

Correct a raw HyperLogLog estimate with the standard small-range and large-range fixes for 32-bit hashes.

If the raw estimate is at most 2.5 * m and some registers are zero, return the linear-counting value m * ln(m / zero_registers). If the estimate exceeds 2^32 / 30, return -2^32 * ln(1 - estimate / 2^32); otherwise return the raw estimate unchanged. A non-positive register count returns 0.0.

Hint

Small estimates use linear counting with the zero registers; huge estimates use the 32-bit range correction.

Test cases

case 1

in: [10,3,16]

expected: 26.783622937146745

case 2

in: [1000,0,64]

expected: 1000

case 3

in: [1000000000,0,1024]

expected: 1138371196.542651

case 4

in: [100,2,16]

expected: 100

case 5

in: [0,4,4]

expected: 0

Starter codePython

import math


def hll_correct_estimate(raw_estimate, zero_registers, num_registers):
    # Your code here
    pass

5 test cases · run your code against them in the editor