Random Variate Generation with Formal Guarantees
summary
Automated synthesis produces exact random variate generators from a finite-precision CDF and a C library implements them using fast integer arithmetic (no arbitrary precision) for floats, fixed-point, and posits. The method is entropy-optimal (attains the Knuth–Yao rate), uses a binary-coded distribution representation and a dual distribution function to extend range and accuracy. Evaluation shows up to 142× fewer bits per variate than GSL, runtime comparable to state-of-the-art with occasional 35× speedups and median slowdowns around 6×.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 0:23State of the art
- 4:11Floating-point limitations
- 7:38Unified CDF-based approach
- 12:33Binary coded distributions
- 15:40Implementation challenges
- 17:04Extended accuracy with dual DF
- 18:06Experimental results
- 19:49Future work
- 20:10Summary
related talks
24mCompiling with Generating Functions
26mGenerating Correctly Rounded Math Libraries for New Floating Point Variants
22mComplexity and Applications of Random Circuit Sampling
58mPortable floating-point calculations
12mRandom Testing for C and C++ Compilers with YARPGen
32mDeterministic Rateless Codes for BSC
58mFast Cryptographic Code via Partial Evaluation
23mGenerating Programs for Polynomial Multiplication with Correctness Assurance