Uniformly-random pre-factored numbers (Kalai)

grfn

Synopsis

Implementation of this paper "Get pre-factored random numbers easily". The full paper may be read here. A synopsis is available in Section 2 in this other paper dealing with getting pre-factored random numbers for Gausian distributions. A reference Python implemention is here.

The Adam Kalai algorithm itself is an easier (but less efficient) version of Eric Bach's original algorithm.

Notes

Parallelized / Concurrent ; Property Testing (QuickCheck), Stan for Static analysis hlint; github actions, IDE:Cursor+ormolu ; Haddock ; makefile; Benchmark (tasty) ; Verification using Refinement Types (LiquidHaskell) during development ; HPC code coverage enabled; cabal/stack profiling; Kleisli Applicative

Performance

Development on an entry level M1 ==> Ghc settings and usable cores (rtsopts as well) set to 4.

Usage

Example: a single pre-factored number guaranteed with uniform probability may be obtained by one of these 3 calls.

⚠️ Note: preFactoredNumOfBitSizePar is a concurrent parallized implementation and may offer performance benefits.

>>> genARandomPreFactoredNumberLTEn 20 -- will give a pre-factored number less 
than or equal to 20.
>>> Right (8,[2,2,2,1])

>>> preFactoredNumOfBitSize 20 -- will give a pre-factored number in the 
range [2^20, 2^21 - 1]
>>> Right (1695177,[17123,11,3,3,1])

>>> preFactoredNumOfBitSizePar 60 -- will give a pre-factored number in the 
range [2^60, 2^61 - 1]
>>> Right (1245467344549977447,[332515759,233924281,179,19,3,3,1])