Get the latest tech news
really divisionless random numbers
I previously wrote about Daniel Lemire’s algorithm for nearly divisionless unbiased bounded random numbers. Recently I found out there is a way to get really divisionless random numbers, as explained by Steve Canon and demonstrated by Kendall Willets.
On further investigation (not shown in the results above) I found that both algorithms take the early-exit with about the same probability, but nearly-divisionless calls rng() much less often in the slow path. The old Intel box is less able to handle the greater complexity of the really-divisionless code, so it performs significantly slower even when mostly taking the early-out. It’s easier to understand than Lemire’s nearly-divisionless algorithm, but the really-divisionless code ends up being longer and more branchy, so it has a hard time keeping up.
Or read this on Hacker News