浮点数可以表示很大的,且未必是整数的值。然而,众所周知,即使 都是 C 势集,故一般的实数显然不可能用几个字节表示出来。然而,一些教师往往错误地讲授浮点数的概念,导致学生对其不理解,进而错误地使用浮点数,而产生 个 bug。
下面我们以 IEEE-754 规定的二进制双精度浮点数 (即 C 中的 double
类型) 为例,对浮点数进行简介。
双精度浮点数在存储时使用 个二进制位,从高位 (MSB) 到低位 (LSB) 排列,有符号 位,指数 位,有效数字 位。
用 表示从高到低数第 位,如果指数位不都是 1,也不都是 0 [1],则该浮点数表示一个实数值:
其中 为
我们可以将其理解为,将 位有效数字取出,最高位拼上一个 后视为一个 位无符号二进制数,然后将其除以 得到一个 中的实数,再将其乘以 ,并根据符号位确定其符号;而 又是将 位指数取出并视为一个 位无符号二进制数,并将其减去 的结果。
大家在高中已经学习了科学计数法,可见浮点数就类似于二进制的科学计数法。这也是它只用 位就能 (近似) 表示很大的数的原因。
假设在运算过程中,所有的值都在 double
的表示范围内 (即不会得到 NaN
或者无穷大量),则我们可以将 (不太小的) double
看做一个二进制科学计数法表示的数字,其有效数字有 位。这就意味着,如果某个实数的二进制表示的有效位数超过了 位,则多余的有效数字会被进行舍入处理[2]。这意味着假设你有一个绝对精确 (且不超过 double
表示范围) 的实数值,当你将其存放到一个双精度浮点变量后,读出的 double
值和原来的精确值之间可能最大有 的绝对误差。我们可以认为这个实数值的数量级是 ,因此相对误差就可能达到 。
这一不精确性意味着,将一个接近或超过 的整数值存入 double
,可能会改变其值。例如,一个刚听完 C 语言老师讲 double
的人很容易试图如此判断一个整数是否是 的整数次幂:
bool is_power_of_2(int64_t x)
{
if (x <= 0)
return false;
return pow(2, floor(log2(x))) == x;
}
这样就会将 这样的数误判为 的幂。
另外值得注意的是,很多数在 进制表示下可以简单地用几位有效数字表示,但是在 进制下却是无限小数。可以很容易地证明, 进制有限小数在 进制下也有限,但反之不然。
例如 这个数,在二进制下就是无限循环的。最接近它的双精度浮点值是
即 ,我们很容易看出循环节 。
这意味着一些看似很简单的数值也会存在精度问题[3]。例如,某人曾经编写了非常愚蠢的代码并发到邮件列表里,抱怨“编译器将 <=
解释成 <
”:
#include <stdio.h>
int main(void)
{
float n, step;
step = 0.1;
for (n = 2; n <= 10; n = n + step )
printf("%3.4f\n", n ); /* This stops at 9.9000 and not at 10.0000 */
}
但是如果你学过数论的话,一眼就能看出 这个东西二进制下是无限的…… 与它最接近的 float
值是 。
设 ,且 是双射,即存在 。从数学上,显然有
但是,在使用浮点数进行运算的情况下, 的结果可能与 相差甚远。我们在 的邻域,对 和 进行线性近似,则有
结果的相对误差是
即相对误差会被放大
倍。可见,如果 很大,则原来 量级的误差可能被放大到无法容忍的程度。
这里一种极端的情况是,我们在进行浮点比较,即 为阶跃函数:
int f(double x) { return x < 114.514; }
此时 在 附近是无限的。这告诉我们,不能使用答案的正确性依赖于浮点比较结果的算法。需要特别注意的是,即使你使用了 eps
:
int f(double x)
{
if (fabs(x - 114.514) < 1e-6)
return 0;
return (int) copysign(1.0, x - 114.514);
}
也无法改变 趋于无穷的事实。
另一种常见的情况是 为三角函数, 为对应的反三角函数。例如,我们考虑对于一个接近 的值,计算 。此时
注意到如果 的量级在 , 的量级就在 ,由于 double
的相对误差可以达到 ,此时结果会被直接舍入为 。这样, 的计算结果就是 。这意味着互相抵消的三角与反三角操作可能损失一半的有效数字。因此,在写计算几何时,通常应该避免计算角度。
学过物理实验的同学都知道,减法可能损失有效数字。例如,我们通常这样计算多边形 的面积:
(我们认为 。) 一些人会看出,我们把 随便换成一个点都是可以的,例如换成原点:
但是,此时如果多边形距离原点很远,例如 达到了 量级,则此时叉积的值会达到 量级。如果用 double
表示叉积的值,则绝对误差可能达到 。这时如果多边形的面积小于 ,甚至可能将面积错误地算成 。因此这样随便选一个点是不可取的。
C 语言课本真的应该将浮点数扔到最后一章或者附录,跟现在一样直接放在整数类型后面教简直就是坑人。
由于浮点数本身固有的误差,如果你的题目要求输出浮点数,则必须写 SPJ。绝对不能将浮点数只保留一位或两位小数,然后自欺欺人地认为“没有精度问题”。
通常来说,SPJ 应当将“绝对或相对误差不超过 ” 的结果视为正确,即
建议将这个公式在题目中给出,并将 替换成 或 这样的数值。
注意小数 浮点数,你可以要求选手输出绝对精确的小数,但是此时就必须使用某些手法 (例如在标程中使用分数存储中间结果,并在输出时直接将其转换为正确舍入的小数) 保证输出的精确性。
标程和数据合法性校验程序的算法最好不要依赖任何浮点数比较的结果,除非你能够从数学上严格证明这个比较在题目给定的约束下没有任何精度问题 (这很难证明)。绝对不许自欺欺人地在标程里做个判断然后说“实际测试没有精度问题”,除非你在测试时枚举了所有可能的输入。
反面案例:在 2023 年 ICPC 亚洲区域赛 XX 赛站的命题工作中,某 XX 岁出题人自己不会计算几何还非要出计算几何,于是在数据合法性校验中使用了浮点数。最后测试数据包含若干非法数据没校验出来,导致比赛事故。
可以给你的标程加个 #define double long double
(并适当调整代码),然后进行测试。如果这样就过不了,说明要么你的标程存在严重的精度问题,要么你的 SPJ 的 取太小了。如果需要更严格的话,可以用 MPFR 库提供的任意精度浮点数验证标程。
如果一道题目要输出小数,且没有 SPJ,那么有两种可能的情况:
对于情况 1,要保持高度警惕,不要随便就用浮点数强行写并自我安慰说“我多试几个 eps
的值就能过”;对于情况 2,可以放弃本题 (特别是有些很古老的题目,其答案“正确”性依赖于古早的 x87 协处理器的非标准行为,在当前的评测系统根本没法过),如不得不做则也要保持警惕,此种题目有的只能用 long double
过,而有的只能用 double
过…… 严格来说这属于一种“必须和出题人错得一样才能过”的情况。
如果你的算法需要依赖浮点数比较的结果,那么也有两种可能的情况:
对于情况 1,同样需要考虑不依赖浮点比较的算法。这里特别重要的一种情况是,很多判断可以通过叉积进行,例如判断“两条非退化的线段 和 是否平行”,就可以直接判断 是否是 ,而不是用浮点数去表示斜率然后比较。
对于情况 2,同样必须和出题人错得一样。
对于情况 3,则要注意你的算法在边界情况下能否使得答案连续变化。例如,如果某题要求你输出点 到多边形 的最短距离,如果 在多边形内部就直接输出 ,那么我们确实可能需要用浮点比较判断“点是否在多边形内”。但是这并不会影响结果的正确性,因为 在多边形外但离多边形很近时,距离已经趋于 。
由于多余的运算操作可能放大浮点误差,在针对计算几何题目设计算法和编程时,要注意避免不必要的运算 (特别是三角函数、指数等严重非线性的操作,以及对非常大的值进行相减等臭名昭著的问题)。千万不要以为计算几何题可以当成中学数学的解析几何题强行做。如果你发现榜上有很多人冲一道计算几何题,但是大部分提交都 WA
了,那么要谨慎地决定是否开这个题。如果有别的题做可以先写别的题,同时让你的队友在草稿纸上分析一下精度够不够。
指数位都是 1 则表示 ,无穷大值,或 NaN
,将会在其他浮点问题中讨论;指数位都是 0 则为非标准 (subnormal) 浮点值,在正常情况下只会用于表示非常小的数,我们暂不考虑。 ↩︎
IEEE-754 规定了多种舍入模式,包括向下、向上、向 的方向、四舍五入、四舍六入五成双 (如果大家已经做了物理实验应该对这个很熟悉)。但是在比赛中,我们一般只会用默认的四舍五入模式 (有的 OJ 上改舍入模式会直接返回 Restricted Function
或者 Runtime Error
)。 ↩︎
某些应用中使用十进制浮点数 (就和我们物理实验用的科学计数法很接近了),以防止这种问题。但是比赛里面好像并没有什么人用。 ↩︎