Evolving the Go Standard Library with math/rand/v2
1–10 of 45 posts
Re: Evolving the Go Standard Library with math/rand/v2
#2Nice - I wish .NET would be more willing to condemn chunks of the standard library and replace them with something better!
Re: Evolving the Go Standard Library with math/rand/v2
#3Nice - I wish .NET would be more willing to condemn chunks of the standard library and replace them with something better!
That's precisely what I was thinking when I was reading this. The go module transition was not awesome, but if the result is being able to "step" the standard library forward like this without a corresponding major language release, then I take back all the bad things I ever said about it.
Re: Evolving the Go Standard Library with math/rand/v2
#4Related, this article discusses difference generators and tradeoffs for Go using them as Source:
https://zephyrtronium.github.io/articles/randomness.html
Re: Evolving the Go Standard Library with math/rand/v2
#5> 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
G = uint32( uint64(N)*uint64(rand.UInt32())>>32 )
Re: Evolving the Go Standard Library with math/rand/v2
#6> 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.) S…
> It seems like this should select a number in the range with no bias. Is there something I missed?
Yes. There are many values of N that aren’t divisors of UInt32Max.
As the article says: “However, no algorithm can convert 2⁶³ equally likely values into n equally likely values unless 2⁶³ is a multiple of n: otherwise some outputs will necessarily happen more often than others. (As a simpler example, try converting 4 equally likely values into 3.)”
Re: Evolving the Go Standard Library with math/rand/v2
#7Nice - I wish .NET would be more willing to condemn chunks of the standard library and replace them with something better!
That's precisely what I was thinking when I was reading this. The go module transition was not awesome, but if the result is being able to "step" the standard library forward like this without a corresponding major language release, then I take back all the bad things I ever said about it.
What this have to do with go modules? Any standard lib should have the ability add a new builtin module under a different namespace regardless of how third-party packages of managed, right?
Re: Evolving the Go Standard Library with math/rand/v2
#8Earlier quoted context omitted.
That's precisely what I was thinking when I was reading this. The go module transition was not awesome, but if the result is being able to "step" the standard library forward like this without a corresponding major language release, then I take back all the bad things I ever said about it.
What this have to do with go modules? Any standard lib should have the ability add a new builtin module under a different namespace regardless of how third-party packages of managed, right?
The standard lib was considered core code and to make even the smallest change can have a huge impact. It was more a matter of, "if we're going to do a v2 language, what would we fix?" And, as it turns out this required no regression of existing core language code.
Re: Evolving the Go Standard Library with math/rand/v2
#9Nice - I wish .NET would be more willing to condemn chunks of the standard library and replace them with something better!
Not the same, but I wanted to say that when I was upgrading apps from .NET Framework to Core and above, I was surprised how many Framework packages not only had upgrades, but were deprecated entirely and replaced by a new package. We had a difficult time migrating. (This was at MSFT btw)
Re: Evolving the Go Standard Library with math/rand/v2
#10> 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.) S…
> It seems like this should select a number in the range with no bias. Is there something I missed? Yes. There are many values of N that aren’t divisors of UInt32Max . As the article says: “However, no algorithm can convert 2⁶³ equally likely values into n equally likely values unless 2⁶³ is a multiple of n: otherwise some outputs will necessarily happen more often than others. (As a simpler example, try converting 4…
Are you sure? Maybe this isn't a good test but it seems pretty evenly distributed to me:
https://go.dev/play/p/IeJQEAclBCU
Edit: maybe this shows the bias better: https://go.dev/play/p/3eKJibIlF1a