> 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...<p>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.)<p>Say you want to generate a number, G, in interval [0,N] where N<=UInt32Max. The algorithm is:<p><pre><code> G = uint32( uint64(N)*uint64(rand.UInt32())>>32 )
</code></pre>
It seems like this should select a number in the range with no bias. Is there something I missed?
As often I’m impressed by the quality of all of this. The amount of thinking that went into this, this excellent written blog post. I love the Go blog.
I like the Principles section. Very measured and practical approach to releasing new stdlib packages. <a href="https://go.dev/blog/randv2#principles" rel="nofollow">https://go.dev/blog/randv2#principles</a><p>The end of the post they mention that an encoding/json/v2 package is in the works: <a href="https://github.com/golang/go/discussions/63397">https://github.com/golang/go/discussions/63397</a>
Related, this article discusses difference generators and tradeoffs for Go using them as Source:
<a href="https://zephyrtronium.github.io/articles/randomness.html" rel="nofollow">https://zephyrtronium.github.io/articles/randomness.html</a>
> Ideally, the v2 package should be able to do everything the v1 package could do, and when v2 is released, the v1 package should be rewritten to be a thin wrapper around v2.<p>And even more ideally, as many v1 usages should be automatically fixed as possible by `go fix` or similar tools. Allowing this to <i>all</i> user packages would be a major improvement over the status quo.