-- | Various formulas for working with bloomfilters.
module Data.BloomFilter.Calc (
    falsePositiveProb,
    filterSize,
) where

import           Numeric (expm1)

-- $setup
-- >>> import Numeric (showFFloat)

-- | Approximate probability of false positives
-- \[
-- {\displaystyle \varepsilon =\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}}
-- \]
--
-- >>> [ showFFloat (Just 5) (falsePositiveProb 10_000 100_000 k) "" | k <- [1..5] ]
-- ["0.09516","0.03286","0.01741","0.01181","0.00943"]
--
falsePositiveProb ::
       Double  -- ^ /n/, number of elements
    -> Double  -- ^ /m/, size of bloom filter
    -> Double  -- ^ /k/, number of hash functions
    -> Double
falsePositiveProb :: Double -> Double -> Double -> Double
falsePositiveProb Double
n Double
m Double
k =
    -- (1 - (1 - recip m) ** (k * n)) ** k
    Double -> Double
forall a. Num a => a -> a
negate (Double -> Double
forall a. Floating a => a -> a
expm1 (Double -> Double
forall a. Num a => a -> a
negate (Double
k Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
n Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
m))) Double -> Double -> Double
forall a. Floating a => a -> a -> a
** Double
k

-- | Filter size for given number of elements, false positive rate and
-- number of hash functions.
filterSize ::
       Double  -- ^ /n/, number of elements
    -> Double  -- ^ /e/, false positive rate
    -> Double  -- ^ /k/, number of hash functions
    -> Double
filterSize :: Double -> Double -> Double -> Double
filterSize Double
n Double
e Double
k  =
    -- recip (1 - (1 - e ** recip k) ** recip (k * n))
    Double -> Double
forall a. Num a => a -> a
negate Double
k Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
n Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double -> Double
forall a. Floating a => a -> a
log (Double
1 Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
e Double -> Double -> Double
forall a. Floating a => a -> a -> a
** Double -> Double
forall a. Fractional a => a -> a
recip Double
k)