{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:03:43Z","timestamp":1784199823696,"version":"3.55.0"},"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 \u201cReal-RAM\u201d 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>\n                    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\n                    <jats:styled-content style=\"color:#9006ba\">Knuth and Yao<\/jats:styled-content>\n                    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 \u201ccontinuous\u201d and \u201cdiscrete\u201d distributions, showing competitive runtime with the state-of-the-art GNU Scientific Library while delivering higher accuracy, entropy efficiency, and automation.\n                  <\/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":1,"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"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0301-0872","authenticated-orcid":false,"given":"Wonyeol","family":"Lee","sequence":"additional","affiliation":[{"name":"POSTECH, Pohang, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","unstructured":"John M. Abowd et al. 2022. The 2020 Census Disclosure Avoidance System TopDown Algorithm. Harvard Data Science Review Special Issue 2 (June 2022) 77 pages. https:\/\/doi.org\/10.1162\/99608f92.529e3cb9 10.1162\/99608f92.529e3cb9","DOI":"10.1162\/99608f92.529e3cb9"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591220"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108770750"},{"key":"e_1_3_2_5_2","first-page":"2770","volume-title":"In Proceedings of the 24th International foint Conference on Artificial Intelligence","author":"Vaishak Belle","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 foint Conference on Artificial Intelligence. AAAI Press, Palo Alto, 2770-2776."},{"key":"e_1_3_2_6_2","volume-title":"Probability and Measure","author":"Patrick Billingsley","year":"1986","unstructured":"Patrick Billingsley. 1986. Probability and Measure (2nd ed.). John Wiley & Sons, New York."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-34514-5"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3632874"},{"key":"e_1_3_2_9_2","unstructured":"Taylor R. Campbell. 2014. Uniform Random Floats. https:\/\/prng.di.unimi.it\/random_real.c"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/3495724.3497039"},{"key":"e_1_3_2_11_2","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. Research Report ensl-01529804. Laboratoire de l'Informatique du Parall\u00e8lisme. https:\/\/ens-lyon.hal.science\/ensl-01529804"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","unstructured":"Christian de Schryver Daniel Schmidt Norbert Wehn Elke Korn Henning Marxen Anton Kostiuk and Ralf Korn. 2012. A Hardware Efficient Random Number Generator for Nonuniform Distributions with Arbitrary Precision. International Journal of Reconfigurable Computing 2012 Article 675130 (March 2012) 11 pages. https:\/\/doi.org\/10.1155\/2012\/675130 10.1155\/2012\/675130","DOI":"10.1155\/2012\/675130"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1842722.1842723"},{"key":"e_1_3_2_14_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-8643-8","volume-title":"Non-Uniform Random Variate Generation","author":"Luc Devroye","year":"1986","unstructured":"Luc Devroye. 1986. Non-Uniform Random Variate Generation. Springer-Verlag,New York."},{"key":"e_1_3_2_15_2","unstructured":"Luc Devroye and Claude Gravel. 2015. Sampling with Arbitrary Precision. arXiv:1502.02539v1"},{"key":"e_1_3_2_16_2","unstructured":"Allen B. Downey. 2007. Generating Pseudo-random Floating-Point Values. https:\/\/allendowney.com\/research\/rand\/downey07randfloat.pdf"},{"key":"e_1_3_2_17_2","unstructured":"Thomas L. Draper and Feras A. Saad. 2025. Efficient Rejection Sampling in the Entropy-Optimal Range. arXiv:2504.04267"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2015.7293949"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","unstructured":"Yusong Du Baoying Fan and Baodian Wei. 2022. An Improved Exact Sampling Algorithm for the Standard Normal Distribution. Computational Statistics 37 (2022) 721-737. https:\/\/doi.org\/10.1007\/s00180-021-01136-w 10.1007\/s00180-021-01136-w","DOI":"10.1007\/s00180-021-01136-w"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-349614_26"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-014-0218-3"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_1"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.2478\/tmmp-2014-0022"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/1236463.1236468"},{"key":"e_1_3_2_25_2","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. http:\/\/www.gnu.org\/software\/gsl\/"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3656412"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","unstructured":"Ivan Gazeau Dale Miller and Catuscia Palamidessi. 2016. Preserving Differential Privacy Under Finite-Precision Semantics. Theoretical Computer Science 655 (Dec. 2016) 92-108. https:\/\/doi.org\/10.1016\/j.tcs.2016.01.015 10.1016\/j.tcs.2016.01.015","DOI":"10.1016\/j.tcs.2016.01.015"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3604935"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-50417-5_2"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3503512"},{"key":"e_1_3_2_31_2","unstructured":"Artur Grabowski. 2015. Generating Random Doubles. https:\/\/github.com\/art4711\/random-double\/blob\/master\/rd.c"},{"key":"e_1_3_2_32_2","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_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.556116"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","unstructured":"Charles R Harris et al. 2020. Array Programming with NumPy. Nature 585 (Sept. 2020) 357-362. https:\/\/doi.org\/10.1038\/s41586-020-2649-2 10.1038\/s41586-020-2649-2","DOI":"10.1038\/s41586-020-2649-2"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/IEEESTD.2019.8766229"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2018.2814587"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2710016"},{"key":"e_1_3_2_38_2","first-page":"357","volume-title":"In Algorithms and Complexity: New Directions and Recent Results","author":"Donald E. Knuth","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-428."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3230636"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454049"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3498664"},{"key":"e_1_3_2_42_2","unstructured":"J\u00e9r\u00e9mie Lumbroso. 2013. Optimal Discrete Uniform Generation from Coin Flips and Applications. arXiv:1304.1916"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382264"},{"key":"e_1_3_2_44_2","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques.in Algorithms and Data Analysis (second ed.)","author":"Michael Mitzenmacher","year":"2017","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_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01975722"},{"key":"e_1_3_2_46_2","unstructured":"Peter Occil. 2023. More Random Sampling Methods. https:\/\/peteroupc.github.io\/randomnotes.pdf"},{"key":"e_1_3_2_47_2","unstructured":"Peter Occil. 2023. Partially-Sampled Random Numbers for Accurate Sampling of Continuous Distributions. https:\/\/peteroupc.github.io\/exporand.pdf"},{"key":"e_1_3_2_48_2","unstructured":"Peter Occil. 2024. Randomization and Sampling Methods. https:\/\/peteroupc.github.io\/randomfunc.pdf"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.5555\/3454287.3455008"},{"key":"e_1_3_2_50_2","unstructured":"Posit Working Group. 2022. Standard for Posit TM Arithmetic. National Supercomputing Centre A*STAR Singapore. https:\/\/posithub.org\/docs\/posit_standard-2.pdf"},{"key":"e_1_3_2_51_2","volume-title":"Numerical Recipes in C (2nd ed.)","author":"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_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43414-7_19"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.15243770"},{"key":"e_1_3_2_54_2","first-page":"1036","volume-title":"In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research","author":"Feras A. Saad","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-1046."},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3371104"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454078"},{"key":"e_1_3_2_57_2","unstructured":"Michael Ian Shamos. 1978. Computational Geometry. Ph. D. Dissertation. Yale University."},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/ARITH54963.2022.00014"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","unstructured":"John S. Sobolewski and W. H. Payne. 1972. Pseudonoise with Arbitrary Amplitude Distribution-Part I: Theory. IEEE Trans. Comput. C-21 4 (1972) 337-345. https:\/\/doi.org\/10.1109\/TC.1972.5008973 10.1109\/TC.1972.5008973","DOI":"10.1109\/TC.1972.5008973"},{"key":"e_1_3_2_60_2","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_3_2_61_2","unstructured":"The MathWorks Inc. 2024. Probability Distributions - MATLAB & Simulink. https:\/\/www.mathworks.com\/help\/stats\/probability-distributions-1.html"},{"key":"e_1_3_2_62_2","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_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2008.4629938"},{"issue":"10","key":"e_1_3_2_64_2","first-page":"2542","article-title":"Two Algorithms for Random Number Generation Implemented by Using Arithmetic of Limited Precision","volume":"86","author":"Tomohiko Uyematsu","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 (Oct. 2003), 2542-2551.","journal-title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0686-2"},{"key":"e_1_3_2_66_2","first-page":"36","volume-title":"In Monte Carlo Method","author":"voan Neumann John","year":"1951","unstructured":"John voan 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, Chapter 13, 36-38."},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1049\/el:19740423"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","unstructured":"Michael Walter. 2019. Sampling the Integers with Low Relative Error. In Proceedings of the 11th International Conference on Cryptology in Africa (Lecture Notes in Computer Science Vol. 11627). Springer Cham 157-180. https:\/\/doi.org\/10.1007\/978-3-030-23696-0_9 10.1007\/978-3-030-23696-0_9","DOI":"10.1007\/978-3-030-23696-0_9"},{"key":"e_1_3_2_69_2","unstructured":"Abraham Ziv Moshe Olshansky Ealan Henis and Anna Retiman. 2001. IBM Accurate Portable Mathlib. https:\/\/github.com\/dreal-deps\/mathlib"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","unstructured":"Pedro Zuidberg Dos Martires Anton Dries and Luc DeRaedt. 2019. Exact and Approximate Weighted.Model Integration with Probability Density Functions Using Knowledge Compilation. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence. AAAI Press Palo Alto 7825-7833. https:\/\/doi.org\/10.1609\/aaai.v33i01.33017825 10.1609\/aaai.v33i01.33017825","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":[[2026,7,16]],"date-time":"2026-07-16T10:03:53Z","timestamp":1784196233000},"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":[{"value":"2475-1421","type":"electronic"}],"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"}}]}}