math/rand,math/rand/v2: ExpFloat64 can sometimes return exactly 0

[argusdusty]

Go version

go version go1.21.6 windows/amd64

Output of go env in your module/workspace:

set GO111MODULE=
set GOARCH=amd64
set GOBIN=
set GOCACHE=C:\Users\Argusdusty\AppData\Local\go-build
set GOENV=C:\Users\Argusdusty\AppData\Roaming\go\env
set GOEXE=.exe
set GOEXPERIMENT=
set GOFLAGS=
set GOHOSTARCH=amd64
set GOHOSTOS=windows
set GOINSECURE=
set GOMODCACHE=O:\Code\pkg\mod
set GONOPROXY=
set GONOSUMDB=
set GOOS=windows
set GOPATH=O:\Code
set GOPRIVATE=
set GOPROXY=https://proxy.golang.org,direct
set GOROOT=C:\Program Files\Go
set GOSUMDB=sum.golang.org
set GOTMPDIR=
set GOTOOLCHAIN=auto
set GOTOOLDIR=C:\Program Files\Go\pkg\tool\windows_amd64
set GOVCS=
set GOVERSION=go1.21.6
set GCCGO=gccgo
set GOAMD64=v1
set AR=ar
set CC=gcc
set CXX=g++
set CGO_ENABLED=1
set GOMOD=NUL
set GOWORK=O:\Code\src\go.work
set CGO_CFLAGS=-O2 -g
set CGO_CPPFLAGS=
set CGO_CXXFLAGS=-O2 -g
set CGO_FFLAGS=-O2 -g
set CGO_LDFLAGS=-O2 -g
set PKG_CONFIG=pkg-config
set GOGCCFLAGS=-m64 -mthreads -Wl,--no-gc-sections -fmessage-length=0 -ffile-prefix-map=C:\Users\ARGUSD~1\AppData\Local\Temp\go-build672535778=/tmp/go-build -gno-record-gcc-switches

What did you do?

https://go.dev/play/p/-5HbPTMP5X9

Running ExpFloat64() after a few iterations on a brute-forced seed that triggers this case.

What did you see happen?

ExpFloat64() returns 0.0 exactly.

What did you expect to see?

Per the function's comment: "ExpFloat64 returns an exponentially distributed float64 in the range (0, +math.MaxFloat64]", so a value larger than 0 was expected.

This should occur whenever r.Uint32() at https://cs.opensource.google/go/go/+/refs/tags/go1.21.6:src/math/rand/exp.go;l=32 returns 0 exactly. This appears to still exist in math/rand/v2.

Note: as maybe a separate issue, ExpFloat64 can also theoretically return +Inf, also not in the range specified by the function comment, when r.Float64() returns exactly 0.0 at https://cs.opensource.google/go/go/+/refs/tags/go1.21.6:src/math/rand/exp.go;l=39 - though this is extremely unlikely (example of a specially crafted "random" source to trigger a +Inf https://go.dev/play/p/sugD7822wW5)

[mknyszek]

CC @rsc maybe?

[zephyrtronium]

I think this is a documentation issue. Wikipedia's article on the exponential distribution lists the support as [0, +inf), and I'm not aware of any particular reason to exclude 0 as a variate. (Not to say no such reason exists.)

The way to exclude 0 and +inf as outputs of the exponential generator without introducing bias would be by explicit rejection: check for the conditions we care about and continue. The ziggurat method is already a rejection sampling algorithm, so it should be fine to exclude two additional rare values if that is what we would prefer to do.

Note: as maybe a separate issue, ExpFloat64 can also theoretically return +Inf, also not in the range specified by the function comment, when r.Float64() returns exactly 0.0 ... though this is extremely unlikely

It's probably unlikely to find a seed with math/rand's default Source which will lead to this situation in feasible time, but it's possible to construct one with math/rand/v2's PCG. Any state which produces an x such that 0x00e290a139 <= x & (1<<40 - 1) <= 0x00ffffffff followed by a 0 will do it. By equidistribution, there are (1<<32 - 0xe290a139) * (1<<24) = 8285227180883968 such states. (Using math/rand/v2's ExpFloat64 to derive these numbers. The math would be slightly different with math/rand's ExpFloat64, which reuses bits between the ziggurat slice and x-coord.)

With the DXSM step, finding such an x is beyond what I know how to do, but I believe there are techniques better than brute force to do it. Once an appropriate state is found, NewPCG lets us construct a generator with it directly.

It seems more likely to me that +inf would be a problem than 0, but given it's been a possible output since ExpFloat64 was introduced and this is the first issue about it, I'm less certain. Maybe it has been a problem but it's too rare to diagnose with math/rand's source, though.

[argusdusty]

I'm fine with the 0 just being a documentation change.

I filed this is because I caught a 0 'in the wild', running a program generating tens of billions of ExpFloat64 results, then being surprised to see my program crash on a 0. It was trivial to adjust my code to support the range being [0, ...] instead of (0, ...], though.

The reason +Inf hasn't been reported before is probably because no one ever noticed. The odds of hitting it on any "real" rng source is extraordinarily low, since you not only have to get a 0 float64 (I think 1/2^63 odds under the v1 rand.Float64, 1/2^53 in v2), but it also has to come after two if statements that I think require ~1/2^11.3 odds. It's probably never happened even once before now; you would have to specifically design an rng source/seed to hit it.

[argusdusty]

Managed to find a PCG seed that triggers a +Inf rand/v2 ExpFloat64 output: https://go.dev/play/p/uGeWg2mcvDw?v=gotip