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.
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.1, 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:54Z |
Modules
- FactoredRandomNumbers
Downloads
- grfn-1.0.0.1.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
Package maintainers
For package maintainers and hackage trustees
Readme for grfn-1.0.0.1
[back to package description]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])