生成均匀的随机浮点数，该浮点数可以返回所有可能的值

问题描述：

An easy way to generate a random float64 in [0,1) is by generating a uniformly random int in [0,2⁵³) and dividing it by 2⁵³. This is essentially what rand.Float64() is doing. However, not all possible float64 values between 0 and 1 can be generated this way: if the value is lower than 2⁻⁴ for example, the 4 last bits of the significand are always going to be 0. Or, put more simply, the naive method always returns multiples of 2⁻⁵³, and not all floating point numbers between 0 and 1 are multiples of 2⁻⁵³.

How do you generate a uniformly random float64 such as every possible value has a chance of being returned? (Here, uniformly random means over the real interval [0,1): conceptually, I want to pick a uniformly random real number between 0 and 1 and return the closest float.)

For context, I need this because I'm implementing this paper and the assumption "all possible values between 0 and 1 are represented" is essential for the result to hold.

在[0,1）中生成随机float64的一种简单方法是在[0中生成统一的int ，2⁵³），然后将其除以2⁵³。这基本上就是 rand.Float64（） code> 正在执行。但是，并不是所有可能的0和1之间的float64值都可以这种方式生成：例如，如果该值小于2⁻⁴，则有效位的最后4位始终变为0。或者，更简单地说，朴素方法总是返回23³的倍数，并且并非所有0到1之间的浮点数都是2 3 3的倍数。 p>

如何生成均匀随机的float64，例如每个可能的值都有可能返回？（这里，在 real interval em> [0,1]上，均匀随机表示：从概念上讲，我想选择一个介于0和1之间的均匀随机实数，并返回最接近的float。） p> \ n

对于上下文，我需要这样做，因为我正在实现本文以及假设“表示0到1之间的所有可能值”对于保持结果至关重要。 p> div>

答

Porting this code (suggested in Severin's answer) is a possible option.

I think that it is equivalent to first generate the significand bits (by generating a random float in [1,2)), and then choose the exponent from a geometric distribution (it has a 0.5 chance of being -1, 0.25 of being -2, etc.).

// uniform returns a uniformly random float in [0,1).
func uniform() float64 {
  sig := rand.Uint64() % (1 << 52)
  return (1 + float64(i)/(1<<52)) / math.Pow(2, geometric())
}

// geometric returns a number picked from a geometric
// distribution of parameter 0.5.
func geometric() float64 {
  b := 1
  for rand.Uint64()%2 == 0 {
     b++
  }
  return b
}

We can probably make geometric() faster by using one of the LeadingZeros* functions from the bits package instead of doing one coin flip per bit.

答

You can use rand Float64 function to return float in the [0, 1) range:

package main

import (
    "fmt"
    "math/rand"
)

func main() {
    fmt.Println(rand.Float64())
}

From the docs:

Float64 returns, as a float64, a pseudo-random number in [0.0,1.0) from the default Source.

答

Because the binary64 floating point numbers are not uniformly spaced, you cannot generate a uniform distribution which can return all possible values less that 1.

If you omit the requirement uniform you have to generate all representable multiples of the smallest positive denormal number 2^(-1074)and zero.

答

Well, standard way, I believe, is to generate up to 1074bits integer and map it to the double. Beware, that your RNG should have internal state at least 1074bits long.

Reference implementation: http://xoshiro.di.unimi.it/random_real.c

Discussion about it: http://xoshiro.di.unimi.it/

Another good link: https://lemire.me/blog/2017/02/28/how-many-floating-point-numbers-are-in-the-interval-01/

答

You could use brute-force rejection sampling by generating 16 random bytes and using it only if it's a valid float64 in [0,1). This approach should give you a normal distribution of all values in that range with performance not much worse than other strategies based on simple benchmarking.

For example (Go Playground):

import "math/rand"

func randFloat64() float64 {
  for {
    f := math.Float64frombits(rand.Uint64())
    if f >= 0 && f < 1.0 {
      return f
    }
  }
}

If performance is critical then you could build an enormous lookup table containing only the valid numbers and choose a random location in the table. The table could be generated ahead of time in a similar fashion as above, by enumerating the bitfield and storing only valid numbers.

生成均匀的随机浮点数，该浮点数可以返回所有可能的值

相关推荐