Bloom Bits per Key

Problem

Compute the optimal Bloom filter size in bits per key.

For a target false positive rate p, the optimal number of bits per key is -ln(p) / (ln 2)^2, which minimizes the false positive probability for a given memory budget. Rates outside the open interval (0, 1) return 0.0.

Return the bits per key as a float.

Hint

The constant 1 / (ln 2)^2 is approximately 2.08 bits per key per nat of ln(1/p).

Test cases

case 1

in: [0.01]

expected: 9.585058377367439

case 2

in: [0.1]

expected: 4.792529188683719

case 3

in: [0.5]

expected: 1.4426950408889634

case 4

in: [1]

expected: 0

Starter codePython

def bloom_bits_per_key(false_positive_rate):
    # Your code here
    pass

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