diff options
Diffstat (limited to 'src/pkg/math/rand/rand.go')
| -rw-r--r-- | src/pkg/math/rand/rand.go | 52 |
1 files changed, 46 insertions, 6 deletions
diff --git a/src/pkg/math/rand/rand.go b/src/pkg/math/rand/rand.go index 2157cdb46..3ffb5c4e5 100644 --- a/src/pkg/math/rand/rand.go +++ b/src/pkg/math/rand/rand.go @@ -60,6 +60,9 @@ func (r *Rand) Int63n(n int64) int64 { if n <= 0 { panic("invalid argument to Int63n") } + if n&(n-1) == 0 { // n is power of two, can mask + return r.Int63() & (n - 1) + } max := int64((1 << 63) - 1 - (1<<63)%uint64(n)) v := r.Int63() for v > max { @@ -74,6 +77,9 @@ func (r *Rand) Int31n(n int32) int32 { if n <= 0 { panic("invalid argument to Int31n") } + if n&(n-1) == 0 { // n is power of two, can mask + return r.Int31() & (n - 1) + } max := int32((1 << 31) - 1 - (1<<31)%uint32(n)) v := r.Int31() for v > max { @@ -95,20 +101,54 @@ func (r *Rand) Intn(n int) int { } // Float64 returns, as a float64, a pseudo-random number in [0.0,1.0). -func (r *Rand) Float64() float64 { return float64(r.Int63()) / (1 << 63) } +func (r *Rand) Float64() float64 { + // A clearer, simpler implementation would be: + // return float64(r.Int63n(1<<53)) / (1<<53) + // However, Go 1 shipped with + // return float64(r.Int63()) / (1 << 63) + // and we want to preserve that value stream. + // + // There is one bug in the value stream: r.Int63() may be so close + // to 1<<63 that the division rounds up to 1.0, and we've guaranteed + // that the result is always less than 1.0. To fix that, we treat the + // range as cyclic and map 1 back to 0. This is justified by observing + // that while some of the values rounded down to 0, nothing was + // rounding up to 0, so 0 was underrepresented in the results. + // Mapping 1 back to zero restores some balance. + // (The balance is not perfect because the implementation + // returns denormalized numbers for very small r.Int63(), + // and those steal from what would normally be 0 results.) + // The remapping only happens 1/2⁵³ of the time, so most clients + // will not observe it anyway. + f := float64(r.Int63()) / (1 << 63) + if f == 1 { + f = 0 + } + return f +} // Float32 returns, as a float32, a pseudo-random number in [0.0,1.0). -func (r *Rand) Float32() float32 { return float32(r.Float64()) } +func (r *Rand) Float32() float32 { + // Same rationale as in Float64: we want to preserve the Go 1 value + // stream except we want to fix it not to return 1.0 + // There is a double rounding going on here, but the argument for + // mapping 1 to 0 still applies: 0 was underrepresented before, + // so mapping 1 to 0 doesn't cause too many 0s. + // This only happens 1/2²⁴ of the time (plus the 1/2⁵³ of the time in Float64). + f := float32(r.Float64()) + if f == 1 { + f = 0 + } + return f +} // Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n). func (r *Rand) Perm(n int) []int { m := make([]int, n) for i := 0; i < n; i++ { - m[i] = i - } - for i := 0; i < n; i++ { j := r.Intn(i + 1) - m[i], m[j] = m[j], m[i] + m[i] = m[j] + m[j] = i } return m } |