False Positive Rate

A Bloom filter's only tunable error is how often it says MAYBE for a key that was never added. This lesson turns that into arithmetic. After it, your program can answer three questions: how many bits and hash functions a filter needs for a target error rate, what error rate a given filter really has, and how many bits per key a target costs.

Where the formula comes from

Take a filter with m bits, k hash functions, and n keys added. One hash function sets one particular bit with probability 1/m. After k*n bit-settings the bit is still 0 with probability

(1 - 1/m)^(k*n)  ≈  e^(-k*n/m)

A key that was never added is a false positive only if all k of its bits are 1, so

fp = (1 - e^(-k*n/m))^k

More hash functions give a key more chances to hit a 0, but they also fill the array faster. There is a best k. Setting the derivative of fp with respect to k to zero gives

k = (m/n) * ln 2        and then      fp = 2^(-k)

so at the best k exactly half of the bits are 1. Solve fp = p for m and you get the sizing rule:

m = ceil( -n * ln(p) / (ln 2)^2 )        k = round( (m/n) * ln 2 ), at least 1

Every ln here is the natural logarithm. -ln(p) / (ln 2)^2 is the bits per key, about 1.44 * log2(1/p).

A worked example

Size a filter for n = 500 keys at p = 0.02.

bits per key = -ln(0.02) / (ln 2)^2 = 8.1424
m = ceil(500 * 8.1424) = 4072
k = round((4072/500) * 0.6931) = round(5.645) = 6

Check the result with the forward formula: fp = (1 - e^(-6*500/4072))^6 = 0.020075, close to the 0.02 we asked for. Nearby values of k are worse, which is the whole point of the formula:

What the numbers look like

Each factor of 10 on p costs about 4.8 more bits per key. The cost does not depend on how big the keys are, which is why a filter is so much smaller than a set of the keys.

What happens past n

fp assumes the n you sized for. Add more and k*n/m grows, more bits turn to 1, and the error climbs toward 100% (FP 10 1000 7 is essentially 1). A filter degrades silently, which is why a later lesson monitors it.

Common mistakes

• Integer division. In C, C++, Go and Rust, m / n and k * n / m on integers truncate. FP 1000 100 5 must be 0.009431; with integer division the exponent becomes 0 and you print 0.000000. Convert to floating point before dividing.
• Using log10 or log2 where the formula says ln.
• Rounding m instead of taking the ceiling. A filter one bit too small is a filter that misses its target.
• Forgetting the floor of 1 on k. OPTIMAL 0.8 100 needs fewer than one bit per key, so the formula rounds k to 0, and it must be raised to 1.
• Printing fewer decimals than asked. The expected output is compared exactly.

Your exercise

The starter reads each command and parses its numbers. You implement the three formulas and print them with the right number of decimals.