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

21–30 of 45 posts

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

#21

Post by physicles »

infogulch wrote: post #13

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

> Second, all changes must be rooted in respect for existing usage and users

This is one of the reasons I love working in Go. I feel that the language maintainers understand that people using Go have more important work to do than update their code to whatever the new hotness is this month.

Basically the opposite of this: https://steve-yegge.medium.com/dear-google-cloud-your-deprec...

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

#22

Post by lifthrasiir »

> 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.

And even more ideally, as many v1 usages should be automatically fixed as possible by `go fix` or similar tools. Allowing this to all user packages would be a major improvement over the status quo.

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

#23

Post by neonsunset »

giancarlostoro wrote: post #20
wiseowise wrote: post #19

Earlier quoted context omitted.

“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.

You don’t get it through NuGet. You get it by specifying the sdk type in the project.

https://learn.microsoft.com/en-us/dotnet/core/project-sdk/ov...

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

#24

Post by josephg »

Someone wrote: post #6
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…

> 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…

> (As a simpler example, try converting 4 equally likely values into 3.)

No, but you can convert a RNG that emits 4 equally likely values into an RNG that emits 3 equally likely values. Just - anytime the RNG returns 4, try again.

Here's a fun puzzle / annoying interview question: You have a biased coin. You can flip it as often as you want, but heads and tails are not equally likely. Without figuring out the bias of the coin, how do you produce purely random bits?

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

#25

Post by pjmlp »

physicles wrote: post #21
infogulch wrote: post #13

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

> Second, all changes must be rooted in respect for existing usage and users This is one of the reasons I love working in Go. I feel that the language maintainers understand that people using Go have more important work to do than update their code to whatever the new hotness is this month. Basically the opposite of this: https://steve-yegge.medium.com/dear-google-cloud-your-deprec...

A long tradition in the Java, C and C++ ecosystems.

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

#26

Post by codeflo »

infogulch wrote: post #12
cmeacham98 wrote: post #11

Earlier quoted context omitted.

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?

Why would you need to “see” it? Unlike the distribution of the RNG itself, this is trivial to solve analytically.

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

#27

Post by josephg »

tempest_ wrote: post #14
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!

Rust has rand in a separate crate which felt weird at first but makes sense for reasons like this thread.

Yeah. "Why should / shouldn't code be put in the standard library" is a really interesting question that I think people don't think about enough.

I think a lot of the benefit of putting stuff in the standard library is interoperability. It seems obvious but - having a string and list type in std means you can pass strings and lists between packages. I think a lot of standard stuff that acts as "glue" should be in std. For example, in nodejs the standard library includes HTTP request and response types because of how useful they are in their ecosystem.

Notably, unlike swift, rust doesn't have an "inlined string" type in std. There's a lot of crates that implement small strings, but most interfaces that need to pass an actual string buffer use std::String - and thats way less efficient. (Thankfully, &str is more common at interface boundaries). Rust also doesn't have much support for futures in std - which upsets a lot of people, because tokio ends up being included by a lot of programs.

Anyway, when it comes to crates like rand where interoperability isn't important, I think its fine to keep this stuff out of std. Code can evolve much more easily when it lives as a 3rd party library.

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

#28

Post by stouset »

josephg wrote: post #24
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…

> (As a simpler example, try converting 4 equally likely values into 3.) No, but you can convert a RNG that emits 4 equally likely values into an RNG that emits 3 equally likely values. Just - anytime the RNG returns 4, try again. Here's a fun puzzle / annoying interview question: You have a biased coin. You can flip it as often as you want, but heads and tails are not equally likely. Without figuring out the bias of…

My guess after a few glasses of wine and thinking on it for a few minutes:

Flip twice. If both flips are the same discard the result. Output 0 for TH, 1 for HT.

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

#29

Post by flyingmutant »

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 algorithm produces biased result with probability 1/2^(32-bitwidth(N)). Using 64 or 128 random bits can make the bias practically undetectable. Comprehensive overview of the approach can be found here: https://github.com/apple/swift/pull/39143
Post reply on HN