{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T14:29:17Z","timestamp":1754144957494,"version":"3.41.2"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T00:00:00Z","timestamp":1749772800000},"content-version":"vor","delay-in-days":3,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2311983"],"award-info":[{"award-number":["2311983"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,6,10]]},"abstract":"<jats:p>Generating random variates is a fundamental operation in diverse areas of computer science and is supported in almost all modern programming languages. Traditional software libraries for random variate generation are grounded in the idealized \"Real-RAM\" model of computation, where algorithms are assumed to be able to access uniformly distributed real numbers from the unit interval and compute with infinite-precision real arithmetic. These assumptions are unrealistic, as any software implementation of a Real-RAM algorithm on a physical computer can instead access a stream of individual random bits and computes with finite-precision arithmetic. As a result, existing libraries have few theoretical guarantees in practice. For example, the actual distribution of a random variate generator is generally unknown, intractable to quantify, and arbitrarily different from the desired distribution; causing runtime errors, unexpected behavior, and inconsistent APIs.<\/jats:p>\n          <jats:p>This article introduces a new approach to principled and practical random variate generation with formal guarantees. The key idea is to first specify the desired probability distribution in terms of a finite-precision numerical program that defines its cumulative distribution function (CDF), and then generate exact random variates according to this CDF. We present a universal and fully automated method to synthesize exact random variate generators given any numerical CDF implemented in any binary number format, such as floating-point, fixed-point, and posits. The method is guaranteed to operate with the same precision used to specify the CDF, does not overflow, avoids expensive arbitrary-precision arithmetic, and exposes a consistent API. The method rests on a novel space-time optimal implementation for the class of generators that attain the information-theoretically optimal Knuth and Yao entropy rate, consuming the least possible number of input random bits per output variate. We develop a random variate generation library using our method in C and evaluate it on a diverse set of \"continuous\" and \"discrete\" distributions, showing competitive runtime with the state-of-the-art GNU Scientific Library while delivering higher accuracy, entropy efficiency, and automation.<\/jats:p>","DOI":"10.1145\/3729251","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:02:27Z","timestamp":1749830547000},"page":"125-149","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Random Variate Generation with Formal Guarantees"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0505-795X","authenticated-orcid":false,"given":"Feras A.","family":"Saad","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0301-0872","authenticated-orcid":false,"given":"Wonyeol","family":"Lee","sequence":"additional","affiliation":[{"name":"POSTECH, Pohang, Republic of Korea"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1162\/99608f92.529e3cb9"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591220"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","unstructured":"Gilles Barthe Katoen Joost-Pieter and Alexandra Silva (Eds.). 2020. Foundations of Probabilistic Programming. Cambridge University Press Cambridge UK. https:\/\/doi.org\/10.1017\/9781108770750 10.1017\/9781108770750","DOI":"10.1017\/9781108770750"},{"key":"e_1_2_2_4_1","volume-title":"Proceedings of the 24th International Joint Conference on Artificial Intelligence. AAAI Press, Palo Alto. 2770\u20132776","author":"Belle Vaishak","year":"2015","unstructured":"Vaishak Belle, Andrea Passerini, and Guy Van den Broeck. 2015. Probabilistic Inference in Hybrid Domains by Weighted Model Integration. In Proceedings of the 24th International Joint Conference on Artificial Intelligence. AAAI Press, Palo Alto. 2770\u20132776."},{"key":"e_1_2_2_5_1","volume-title":"Probability and Measure","author":"Billingsley Patrick","unstructured":"Patrick Billingsley. 1986. Probability and Measure (2nd ed.). John Wiley & Sons, New York.","edition":"2"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-34514-5"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3632874"},{"key":"e_1_2_2_8_1","unstructured":"Taylor R. Campbell. 2014. Uniform Random Floats. https:\/\/prng.di.unimi.it\/random_real.c"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3495724.3497039"},{"key":"e_1_2_2_10_1","unstructured":"Catherine Daramy-Loirat David Defour Florent de Dinechin Matthieu Gallet Nicolas Gast Christoph Lauter and Jean-Michel Muller. 2006. CR-LIBM: A Library of Correctly Rounded Elementary Functions in Double-Precision. Laboratoire de l\u2019Informatique du Parall\u00e8lisme. https:\/\/ens-lyon.hal.science\/ensl-01529804"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1155\/2012\/675130"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1842722.1842723"},{"volume-title":"Non-Uniform Random Variate Generation","author":"Devroye Luc","key":"e_1_2_2_13_1","unstructured":"Luc Devroye. 1986. Non-Uniform Random Variate Generation. Springer-Verlag, New York."},{"key":"e_1_2_2_14_1","unstructured":"Luc Devroye and Claude Gravel. 2015. Sampling with Arbitrary Precision. arxiv:1502.02539v1."},{"key":"e_1_2_2_15_1","unstructured":"Allen B. Downey. 2007. Generating Pseudo-random Floating-Point Values. https:\/\/allendowney.com\/research\/rand\/downey07randfloat.pdf"},{"key":"e_1_2_2_16_1","volume-title":"Saad","author":"Draper Thomas L.","year":"2025","unstructured":"Thomas L. Draper and Feras A. Saad. 2025. Efficient Rejection Sampling in the Entropy-Optimal Range. arxiv:2504.04267."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2015.7293949"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00180-021-01136-w"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34961-4_26"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-014-0218-3"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_1"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.2478\/tmmp-2014-0022"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236463.1236468"},{"key":"e_1_2_2_24_1","volume-title":"GNU Scientific Library Reference Manual","author":"Galassi Mark","year":"2078","unstructured":"Mark Galassi, Jim Davies, James Theiler, Brian Gough, Gerard Jungman, Patrick Alken, Michael Booth, and Fabrice Rossi. 2009. GNU Scientific Library Reference Manual (3rd ed.). Network Theory Ltd., Surrey. isbn:0954612078 http:\/\/www.gnu.org\/software\/gsl\/","edition":"3"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656412"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.01.015"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3604935"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-50417-5_2"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3503512"},{"key":"e_1_2_2_30_1","unstructured":"Artur Grabowski. 2015. Generating Random Doubles. https:\/\/github.com\/art4711\/random-double\/blob\/master\/rd.c"},{"key":"e_1_2_2_31_1","volume-title":"GNU MP: The GNU Multiple Precision Arithmetic Library (6.3.0 ed.)","author":"Granlund Torbj\u00f6rn","year":"2023","unstructured":"Torbj\u00f6rn Granlund. 2023. GNU MP: The GNU Multiple Precision Arithmetic Library (6.3.0 ed.). Free Software Foundation, Inc, Boston. https:\/\/gmplib.org\/gmp-man-6.3.0.pdf"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556116"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-020-2649-2"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/IEEESTD.2019.8766229"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2018.2814587"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2710016"},{"key":"e_1_2_2_37_1","volume-title":"Yao","author":"Knuth Donald E.","year":"1976","unstructured":"Donald E. Knuth and Andrew C. Yao. 1976. The Complexity of Nonuniform Random Number Generation. In Algorithms and Complexity: New Directions and Recent Results, Joseph F. Traub (Ed.). Academic Press, Inc., Orlando, FL. 357\u2013428."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230636"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454049"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498664"},{"key":"e_1_2_2_41_1","unstructured":"J\u00e9r\u00e9mie Lumbroso. 2013. Optimal Discrete Uniform Generation from Coin Flips and Applications. arxiv:1304.1916."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382264"},{"volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher Michael","key":"e_1_2_2_43_1","unstructured":"Michael Mitzenmacher and Upfal Eli. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (second ed.). Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01975722"},{"key":"e_1_2_2_45_1","unstructured":"Peter Occil. 2023. More Random Sampling Methods. https:\/\/peteroupc.github.io\/randomnotes.pdf"},{"key":"e_1_2_2_46_1","unstructured":"Peter Occil. 2023. Partially-Sampled Random Numbers for Accurate Sampling of Continuous Distributions. https:\/\/peteroupc.github.io\/exporand.pdf"},{"key":"e_1_2_2_47_1","unstructured":"Peter Occil. 2024. Randomization and Sampling Methods. https:\/\/peteroupc.github.io\/randomfunc.pdf"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/3454287.3455008"},{"volume-title":"Standard for Posit \u2122 Arithmetic","author":"Posit Working Group","key":"e_1_2_2_49_1","unstructured":"Posit Working Group. 2022. Standard for Posit \u2122 Arithmetic. National Supercomputing Centre, A*STAR, Singapore. https:\/\/posithub.org\/docs\/posit_standard-2.pdf"},{"key":"e_1_2_2_50_1","volume-title":"Flannery","author":"Press William H.","year":"1992","unstructured":"William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. 1992. Numerical Recipes in C (2nd ed.). Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43414-7_19"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","unstructured":"Feras Saad and Wonyeol Lee. 2025. librvg: C Library for Random Variate Generation with Formal Guarantees. https:\/\/doi.org\/10.5281\/zenodo.15243770 10.5281\/zenodo.15243770","DOI":"10.5281\/zenodo.15243770"},{"key":"e_1_2_2_53_1","volume-title":"Mansinghka","author":"Saad Feras A.","year":"2020","unstructured":"Feras A. Saad, Cameron E. Freer, Martin C. Rinard, and Vikash K. Mansinghka. 2020. The Fast Loaded Dice Roller: A Near-optimal Exact Sampler for Discrete Probability Distributions. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research, Vol. 108). PMLR, Norfolk. 1036\u20131046."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371104"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454078"},{"volume-title":"Computational Geometry. Ph. D. Dissertation","author":"Shamos Michael Ian","key":"e_1_2_2_56_1","unstructured":"Michael Ian Shamos. 1978. Computational Geometry. Ph. D. Dissertation. Yale University."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/ARITH54963.2022.00014"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1972.5008973"},{"key":"e_1_2_2_59_1","unstructured":"Jason Stover. 2003. GNU Scientific Library: Gamma Cumulative Distribution Function. https:\/\/github.com\/ampl\/gsl\/blob\/v2.7.0\/cdf\/gamma.c"},{"key":"e_1_2_2_60_1","unstructured":"The MathWorks Inc.. 2024. Probability Distributions - MATLAB & Simulink. https:\/\/www.mathworks.com\/help\/stats\/probability-distributions-1.html"},{"key":"e_1_2_2_61_1","unstructured":"James Theiler and Brian Gough. 2007. GNU Scientific Library: Gamma Random Variate Generator. https:\/\/github.com\/ampl\/gsl\/blob\/v2.7.0\/randist\/gamma.c"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2008.4629938"},{"key":"e_1_2_2_63_1","first-page":"2542","article-title":"Two Algorithms for Random Number Generation Implemented by Using Arithmetic of Limited Precision","volume":"86","author":"Uyematsu Tomohiko","year":"2003","unstructured":"Tomohiko Uyematsu and Yuan Li. 2003. Two Algorithms for Random Number Generation Implemented by Using Arithmetic of Limited Precision. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 86, 10 (2003), Oct., 2542\u20132551.","journal-title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0686-2"},{"key":"e_1_2_2_65_1","series-title":"Bureau of Standards Applied Mathematics Series","volume-title":"Various Techniques Used in Connection with Random Digits","author":"von Neumann John","unstructured":"John von Neumann. 1951. Various Techniques Used in Connection with Random Digits. In Monte Carlo Method, A. S. Householder, G. E. Forsythe, and H. H. Germond (Eds.) (National Bureau of Standards Applied Mathematics Series, Vol. 12). U. S. Government Printing Office, Washington. 36\u201338."},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1049\/el:19740423"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-23696-0_9"},{"key":"e_1_2_2_68_1","unstructured":"Abraham Ziv Moshe Olshansky Ealan Henis and Anna Retiman. 2001. IBM Accurate Portable Mathlib. https:\/\/github.com\/dreal-deps\/mathlib"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33017825"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729251","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729251","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T06:04:54Z","timestamp":1752645894000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729251"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":69,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2025,6,10]]}},"alternative-id":["10.1145\/3729251"],"URL":"https:\/\/doi.org\/10.1145\/3729251","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"2024-11-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}