[0,1]区间中有多少个浮点数?

原文: How many floating-point numbers are in the interval [0, 1]?

地址:http://lemire.me/blog/2017/02/28/how-many-floating-point-numbers-are-in-the-interval-01/

作者:Daniel Lemire,魁北克大学计算机教授

绝大多数处理器支持 IEEE 754标准的单精度浮点数 。虽然这种格式很常见,但还是常常被用错。

我的一位读者在评论中说 ,从 \([0, 2^{32})\) 中随机抽取一个整数,除以 \(2^{32}\) ,等价于从 \([0, 1)\) 中随机取一个数。

基本正确,但是如果真要这么做的话,会有误差。误差有多大呢?

浮点数由符号位、尾数(有效数字)和指数组成。

  • 符号位只有1位。由于我们只关心正数,所以这一位是固定的,可以不考虑。
  • 尾数有23位,还有1位隐含的1。(译注:尾数实际是24位。754标准规定尾数大于等于1,小于2,所以整数部分总是1,因此在存储时可以省略这一位,只记录小数部分的23位。)
  • 还有8位用于表示指数。如果指数值位于-126到127之间,则含义明确,直接表示其本身的数值。除此之外,则有特殊约定,包括无穷,NaN,非正规数,以及数字零。特别的,当指数值为-127,同时尾数为0时,表示数字0。
/images/754single.png

(图片来源:https://en.wikipedia.org/wiki/IEEE_754-1985

那么,0和1之间有多少个“正常”的非零数呢?指数应该是负的,从-1到-126。由于尾数是23位,则对于每一个指数,都对应 \(2^{23}\) 个不同的浮点数。所以,在 \([0,1)\) 之间有 \(126\times 2^{23}\) 个正常的浮点数。如果你手边没有计算器,可以告诉你这个数是1,056,964,608。如果算上1,则为 \(126\times 2^{23}+1\) ,即1,056,964,609。

很多人认为0也是一个“正常”的数字,所以你可以把它也算上。这样就是1,056,964,610。

32位二进制字符串总共有4,294,967,296个,所以,大概有四分之一的数字位于区间 \([0, 1]\) 内。有趣吧?你的电脑所能表示的所有浮点数,有四分之一位于区间 \([0, 1]\) 。扩展一下,一半的浮点数位于区间 \([-1, 1]\)

这下我们有麻烦了。数字 \(2^{32}\) 不能被1,056,964,610整除。所以一个32位的非负整数除以 \(2^{32}\) 的结果不可能是 \([0, 1]\) 区间上无误差的数字。

那么误差有多大呢?得到0的方法只有一种,但是有257种不同的方法可以得到0.5:任何介于2,147,483,584和2,147,483,776(包含)之间的数除以 \(2^{32}\) 的结果都是0.5。

257分之1是一个相当大的偏差。所以标准库应该不是用这种方式生成 \([0, 1]\) 中的随机数。

如何得到一个无偏差的映射?

因为尾数是23位的,所以可以从 \([0, 2^{24})\) 中任选一个整数,除以 \(2^{24}\) ,这样,商乘以 \(2^{24}\) 可以得到原来的整数。这种方法只对 \(2^{24}\) 有效,换成 \(2^{25}\) 或者更大的数都不行。

所以,你可以在 \([0, 2^{24})\) 中随机选一个整数,除以 \(2^{24}\) 得到一个没有误差的 \([0, 1)\) 中的随机数。也就是说,对于 \([0, 2^{24})\) 中的每一个整数,有且仅有一个 \([0, 1)\) 中的数与之对应。而且,在这些浮点数是等距分布(间隔为 \(2^{-24}\) )的意义上,随机数的分布服从均匀分布。

所以,尽管单精度浮点数有32位,尽管你的电脑可以表示大约 \(2^{30}\)\([0, 1)\) 区间上不同的浮点数,但是随机数发生器很可能只能生成 \([0, 1)\) 区间上 \(2^{24}\) 个不同的浮点数。

多数情况下这就够用了,但是也可能会让你失望。生成 \([0, N)\) 中随机整数的常见方法是先生成随机的浮点数,再乘以 \(N\) 。如果 \(N\)\(2^{24}\) 小,这种方法可行。但是,如果 \(N\)\(2^{24}\) 大,就无法生成 \([0, N)\) 中所有的整数,这样误差太大。

我分析了32位的情况,64位是一样的道理,结论也是相似的。只是在 \([0, 1]\) 区间上可以生成 \(2^{53}\) 个不同的浮点数,而不是 \(2^{24}\) 个。

补充材料:

Comments

Comments powered by Disqus