code review 95460049: math/rand: restore Go 1.2 value stream for Float32, Float64

src/pkg/math/rand/rand.go

 // Copyright 2009 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 // Package rand implements pseudo-random number generators.
 //
 // Random numbers are generated by a Source. Top-level functions, such as
 // Float64 and Int, use a default shared Source that produces a deterministic
 // sequence of values each time a program is run. Use the Seed function to
 // initialize the default Source if different behavior is required for each run.
@@ skipping 83 matching lines @@
         if n <= 0 {
                 panic("invalid argument to Intn")
         }
         if n <= 1<<31-1 {
                 return int(r.Int31n(int32(n)))
         }
         return int(r.Int63n(int64(n)))
 }
 
 // Float64 returns, as a float64, a pseudo-random number in [0.0,1.0).
-func (r *Rand) Float64() float64 { return float64(r.Int63n(1<<53)) / (1 << 53) }
+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.Int31n(1<<24)) / (1 << 24) }
+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++ {
                 j := r.Intn(i + 1)
                 m[i] = m[j]
                 m[j] = i
         }
         return m
@@ skipping 83 matching lines @@
         n = r.src.Int63()
         r.lk.Unlock()
         return
 }
 
 func (r *lockedSource) Seed(seed int64) {
         r.lk.Lock()
         r.src.Seed(seed)
         r.lk.Unlock()
 }