Lemire's algorithm for selecting a random number from a range

[Jim Cheetham]

Just finished reading https://veryseriousblog.com/posts/dissecting-lemire -
a blog discussing
implementations of Lemire's very very efficient algorithm for selecting a
random number from a range

I'll let the author's description stand - they do a better job that I would
...

"""

Lemire’s algorithm is a solution to the problem “Give me a random number
between 0 and N, not including N itself”. For simulating a dice, N would be
6 and you’d get back either 0, 1, 2, 3, 4, or 5 with equal probability.
Computers like to start at zero. We can always add one to the result to get
the familiar results you’d get on a real dice. I’ve worked on random number
generators and written quite a few. In 20 years of doing that, I’d never
come across a solution as cool as Lemire’s.

Before Lemire, the best-known solutions to this problem required one or two
divisions per number generated. You probably learned long division when you
were quite young. You may remember that it can be get pretty tedious and
cumbersome. It’s the same for computers. Division is actually one of the
slowest things we can ask a computer to do. Lemire avoids division by
translating numbers into a much larger number “space” and using
binary-friendly powers-of-two operations instead. His technique almost
always avoids needing a division.

"""
The art of writing software that needs to be understood in the future is a
difficult one :-) and it gets especially difficult when the techniques
being used are focused on efficiency to the machine itself -- if you
haven't read the old Story of Mel (
http://www.catb.org/jargon/html/story-of-mel.html) you probably should!

To go with that, there's the Unix kernel comment "You are not expected to
understand this" (which according to
https://en.wikipedia.org/wiki/Lions%27_Commentary_on_UNIX_6th_Edition,_with_Source_Code#%22You_are_not_expected_to_understand_this%22
wasn't actually a claim to being obtuse)

Lemire's original post is here -
https://lemire.me/blog/2019/06/06/nearly-divisionless-random-integer-generation-on-various-systems/

-jim
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ourshack.com/pipermail/discuss/attachments/20201004/8260df56/attachment.html>