Fast Random Integer Generation in an Interval
ACM Transactions on Modeling and Computer Simulation · 31.01.2019 · 29 (1) · 1-12
DOI: 10.1145/3230636 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Modeling and Computer Simulation, online erschienen am 24.01.2019. Verfasst von Daniel Lemire. Die Arbeit wurde bisher 43-mal zitiert (Crossref) und nennt 40 Literaturangaben. Gefördert von: Natural Sciences and Engineering Research Council of Canada.
Abstract (Originalsprache)
In simulations, probabilistic algorithms, and statistical tests, we often generate random integers in an interval (e.g., [0, s )). For example, random integers in an interval are essential to the Fisher-Yates random shuffle. Consequently, popular languages such as Java, Python, C++, Swift and Go include ranged random integer generation functions as part of their runtime libraries. Pseudo-random values are usually generated in words of a fixed number of bits (e.g., 32b, 64b) using algorithms such as a linear congruential generator. We need functions to convert such random words to random integers in an interval ([0, s )) without introducing statistical biases. The standard functions in programming languages such as Java involve integer divisions. Unfortunately, division instructions are relatively expensive. We review an unbiased function to generate ranged integers from a source of random words that avoids integer divisions with high probability. To establish the practical usefulness of the approach, we show that this algorithm can multiply the speed of unbiased random shuffling on x64 processors. Our proposed approach has been adopted by the Go language for its implementation of the shuffle function.
Förderung
- Natural Sciences and Engineering Research Council of Canada
Zitieren
APA
Lemire, D. (2019). Fast Random Integer Generation in an Interval. ACM Transactions on Modeling and Computer Simulation, 29(1), 1-12. https://doi.org/10.1145/3230636
Vancouver
Lemire D. Fast Random Integer Generation in an Interval. ACM Transactions on Modeling and Computer Simulation. 2019;29(1):1-12. doi:10.1145/3230636
BibTeX
@article{Lemire2019,
author = {Lemire, Daniel},
title = {Fast Random Integer Generation in an Interval},
journal = {ACM Transactions on Modeling and Computer Simulation},
year = {2019},
volume = {29},
number = {1},
pages = {1--12},
doi = {10.1145/3230636}
}
EUVIMED