Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Evolving the Go Standard Library with math/rand/v2

go.dev

Post reply on HN
Print view View original

11–20 of 45 posts

Re: Evolving the Go Standard Library with math/rand/v2

#11

Post by cmeacham98 »

infogulch wrote: post #10
Someone wrote: post #6

Earlier quoted context omitted.

> 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

UInt32Max (i.e. 4294967295) is divisible by 3, so your code actually is perfectly random (or more accurately, as random as go's rand package). It would be biased with N=4, for example.

Regardless, with small values of N, the bias is very slight so you would need many many iterations to see the imperfection in a statically significant way.

Re: Evolving the Go Standard Library with math/rand/v2

#12

Post by infogulch »

cmeacham98 wrote: post #11
infogulch wrote: post #10

Earlier quoted context omitted.

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

UInt32Max (i.e. 4294967295) is divisible by 3, so your code actually is perfectly random (or more accurately, as random as go's rand package). It would be biased with N=4, for example. Regardless, with small values of N, the bias is very slight so you would need many many iterations to see the imperfection in a statically significant way.

That makes sense.

A quick search didn't reveal any good resources for how to test the quality of a random number generator in a number range. Is what I came up with the best strategy, and you just need to run it for much longer (and compare to a known-good implementation) to see the difference?

Re: Evolving the Go Standard Library with math/rand/v2

#13

Post by infogulch »

I like the Principles section. Very measured and practical approach to releasing new stdlib packages. https://go.dev/blog/randv2#principles

The end of the post they mention that an encoding/json/v2 package is in the works: https://github.com/golang/go/discussions/63397

Re: Evolving the Go Standard Library with math/rand/v2

#15

Post by ironhaven »

infogulch wrote: post #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.) S…

You have written a deterministic function. If you test this function with all 4 billion uint32 on one odd interval, go and count the number of times you get each result. Now look at your results, are all of the numbers equally likely or is there bias towards some outputs?

Ps: it looks like your function is exclusive like [0,N) not [0,N] Also your function is described in this blog post https://www.pcg-random.org/posts/bounded-rands.html

Re: Evolving the Go Standard Library with math/rand/v2

#16

Post by assbuttbuttass »

infogulch wrote: post #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.) S…

This maps UInt32Max input values to N output values, so there is guaranteed to be bias by pigeonhole, unless N divides Uint32Max

Re: Evolving the Go Standard Library with math/rand/v2

#17

Post by infogulch »

ironhaven wrote: post #15
infogulch wrote: post #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.) S…

You have written a deterministic function. If you test this function with all 4 billion uint32 on one odd interval, go and count the number of times you get each result. Now look at your results, are all of the numbers equally likely or is there bias towards some outputs? Ps: it looks like your function is exclusive like [0,N) not [0,N] Also your function is described in this blog post https://www.pcg-random.org/post…

Correct on all counts. Thanks!

Re: Evolving the Go Standard Library with math/rand/v2

#18

Post by giancarlostoro »

Smaug123 wrote: post #2

Nice - I wish .NET would be more willing to condemn chunks of the standard library and replace them with something better!

At least .NET is very capable of allowing you to support third party libraries. Heck, even ASP .NET Core isn't built-in anymore, you get it through NuGet. So you're not stuck with the standard libraries.

Re: Evolving the Go Standard Library with math/rand/v2

#19

Post by wiseowise »

giancarlostoro wrote: post #18
Smaug123 wrote: post #2

Nice - I wish .NET would be more willing to condemn chunks of the standard library and replace them with something better!

At least .NET is very capable of allowing you to support third party libraries. Heck, even ASP .NET Core isn't built-in anymore, you get it through NuGet. So you're not stuck with the standard libraries.

“Don’t you guys have internet?”

What happened to batteries-included support?

Re: Evolving the Go Standard Library with math/rand/v2

#20

Post by giancarlostoro »

wiseowise wrote: post #19
giancarlostoro wrote: post #18

Earlier quoted context omitted.

At least .NET is very capable of allowing you to support third party libraries. Heck, even ASP .NET Core isn't built-in anymore, you get it through NuGet. So you're not stuck with the standard libraries.

“Don’t you guys have internet?” What happened to batteries-included support?

ASP isnt included OOTB anymore, so if you want to do web dev in .NET you have to install it, they decoupled a ton of things from the core of the language.
Post reply on HN