<div dir="ltr">Just finished reading <a href="https://veryseriousblog.com/posts/dissecting-lemire">https://veryseriousblog.com/posts/dissecting-lemire</a> - a blog discussing <div>implementations of Lemire's very very efficient algorithm for selecting a random number from a range</div><div><br></div><div>I'll let the author's description stand - they do a better job that I would ...</div><div><br></div><div>"""</div><div><p class="gmail-" style="white-space:pre-wrap">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.</p><p class="gmail-" style="white-space:pre-wrap">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.</p><p class="gmail-" style="white-space:pre-wrap">"""</p></div><div>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 (<a href="http://www.catb.org/jargon/html/story-of-mel.html">http://www.catb.org/jargon/html/story-of-mel.html</a>) you probably should!</div><div><br></div><div>To go with that, there's the Unix kernel comment "You are not expected to understand this" (which according to <a href="https://en.wikipedia.org/wiki/Lions%27_Commentary_on_UNIX_6th_Edition,_with_Source_Code#%22You_are_not_expected_to_understand_this%22">https://en.wikipedia.org/wiki/Lions%27_Commentary_on_UNIX_6th_Edition,_with_Source_Code#%22You_are_not_expected_to_understand_this%22</a> wasn't actually a claim to being obtuse)</div><div><br></div><div>Lemire's original post is here - <a href="https://lemire.me/blog/2019/06/06/nearly-divisionless-random-integer-generation-on-various-systems/">https://lemire.me/blog/2019/06/06/nearly-divisionless-random-integer-generation-on-various-systems/</a><br></div><div><br></div><div>-jim</div></div>