Just finished reading https://

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://

To go with that, there's the Unix kernel comment "You are not expected to

understand this" (which according to

https://

wasn't actually a claim to being obtuse)

Lemire's original post is here -

https://

-jim

**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%22wasn'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