grfn: Uniformly-random pre-factored numbers (Kalai)

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]

grfn is a focused library -- an implementation of Adam Kalai's algorithm to get uniform pre-factored numbers. See README for more details.


[Skip to Readme]

Properties

Versions 1.0.0.0, 1.0.0.0, 1.0.0.1
Change log CHANGELOG.md
Dependencies arithmoi (>=0.13.0 && <0.14), async (>=2.2.5 && <2.3), base (>=4.18.2 && <=4.20.0.1), grfn, monad-loops (>=0.4.3 && <3.3), parallel (>=3.2.2 && <3.3), parallel-io (>=0.3.5 && <0.4), protolude (>=0.3.4 && <0.4), random (>=1.2.1.2 && <1.3), text (>=2.0.2 && <=2.1.1), time (>=1.12.2 && <1.13), unamb (>=0.2.7 && <0.3) [details]
License BSD-3-Clause
Copyright 2024 ThreeEyedGod
Author Venkatesh Narayanan
Maintainer venkatesh.narayanan@live.in
Category Algorithm, Random, Numbers
Home page https://github.com/threeeyedgod/grfn#readme
Source repo head: git clone https://github.com/threeeyedgod/grfn
Uploaded by ThreeEyedGod at 2024-06-22T10:05:52Z

Modules

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


Readme for grfn-1.0.0.0

[back to package description]

grfn

GitHub CI MPL-2.0 license Stable Version Hackage

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])