grfn: Uniformly-random pre-factored numbers (Kalai)
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]
Downloads
- grfn-1.0.0.1.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
For package maintainers and hackage trustees
Candidates
| Versions [RSS] | 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] |
| Tested with | ghc ==9.8.2, ghc ==9.6.5 |
| 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:13:33Z |
| Distributions | NixOS:1.0.0.1 |
| Executables | grfn-exe |
| Downloads | 64 total (6 in the last 30 days) |
| Rating | (no votes yet) [estimated by Bayesian average] |
| Your Rating | |
| Status | Docs uploaded by user Build status unknown [no reports yet] |
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])