HackerPapers

arXiv:1805.10941cs.DS

Fast Random Integer Generation in an Interval

Daniel Lemire

Abstract

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 like 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., 32 bits, 64 bits) 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.

arXiv comments
to appear in ACM Transactions on Modeling and Computer Simulation
Journal reference
ACM Transactions on Modeling and Computer Simulation 29 (1), 2019
DOI
doi:10.1145/3230636
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 6 identifiable commenters in 6 comments across 5 threads, from Sep 2019 to Mar 2022. Found in 2 HN submissions from May 2018 to Mar 2019. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments5 threads

  1. It is high time we let go of the Mersenne Twister (2019) 1 comment

    • It's Lemire's Lehmer Generator or LEMUR 64 for short https://arxiv.org/pdf/1805.10941.pdf https://archive.org/details/proceedings_of_a_second_symposiu...

      jartView on HNParent context

  2. A fast alternative to the modulo reduction (2016) 1 comment

    • For many use cases biased is good enough. The topic of unbiased bounded generation is pretty interesting itself and both lemire and M.E. O'Neill (author of pcg) wrote blog posts and an academic paper comparing different approaches (some using as building block the fixed point…

      NWDDView on HNParent context

  3. Dissecting Lemire's nearly divisionless random number generator 2 comments

    • After reading the intro of the article, I wanted to see whether I could get the gist of the algorithm just from looking at the first code of it that I come upon. I thus took the first such link from the article (https://arxiv.org/pdf/1805.10941.pdf) while trying to avoid any…

      MauranKilomView on HNParent context

    • I'm a bit confused. Looking at the original paper (https://arxiv.org/pdf/1805.10941.pdf) this doesn't seem to be a RNG itself but rather a method to efficiently transform the output of a RNG onto an arbitrary interval while maintaining a uniform distribution. (This is at odds…

      ReelinView on HNParent context

  4. Julia 1.5 Highlights 1 comment

    • It is Julia all the way down. julia> @which randn(1000) randn(dims::Integer...) in Random at ~/Software/Julia/share/julia/stdlib/v1.5/Random/src/normal.jl:210 julia> @edit randn(1000) # Opens the normal.jl file in your editor julia> @run randn(1000) # Starts the debugger in…

      iggView on HNParent context

  5. Algorithm No One Knows About (2016) 1 comment

    • This appears to be the state of the art in minimising the resampling cost: https://arxiv.org/pdf/1805.10941.pdf

      cafView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.