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

Info

2017-03-02 19:33

原文： 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。

（图片来源：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}\) 个。

补充材料：