> In 2018, Daniel Lemire found an algorithm that avoids the divisions nearly all the time (see also his 2019 blog post). In math/rand, adopting Lemire’s algorithm would make Intn(1000) 20-30% faster...
I recently found a super simple algorithm that appears to produce a number in the interval [0,N] with a branchless expression with a single multiplication in an extended number size. (Sorry I don't have a reference.)
Say you want to generate a number, G, in interval [0,N] where N<=UInt32Max. The algorithm is:
G = uint32( uint64(N)*uint64(rand.UInt32())>>32 )
It seems like this should select a number in the range with no bias. Is there something I missed?
I recently found a super simple algorithm that appears to produce a number in the interval [0,N] with a branchless expression with a single multiplication in an extended number size. (Sorry I don't have a reference.)
Say you want to generate a number, G, in interval [0,N] where N<=UInt32Max. The algorithm is:
It seems like this should select a number in the range with no bias. Is there something I missed?