浮點數誤差 - NTUCPC Guide

初見浮點數

這個世界可不是只有整數而已，像是在計算平均值、想要量出精確的長度、計算圓周長等等的狀況，生活中有數不清的地方需要用到不是整數的數字。在電腦當中，這些數字就是以像是 float 和 double 這些浮點數型態儲存，當要使用小數運算時，我們就只要把數字的型態改成 float 或 double 就可以了，相當方便。不過，也不難發現浮點數會有一些問題，最直觀的問題就是電腦是不可能存下無限位數的小數的，所以像是 $\pi$ 這樣的無理數，就不可能被精確的用浮點數儲存在電腦裡。

cpp

#include <bits/stdc++.h>

int main() {
    const double PI = std::numbers::pi;
    std::cout << (long long)(PI * 1'000'000'000'000'000'000) << "\n";
    // 3141592653589793280
}

$\pi$ 是 $3.141592653589793238\ldots$ 所以這個程式碼應該要輸出 3141592653589793238 才對，然而實際的輸出的最後是 ...93280，在對應到小數點後第 17 位的位數開始就出現了誤差，這正是因為電腦無法存下精確的 $\pi$ 的數值，只能存下一個差不多的數字。要是將 PI 改用精度比較差的型態 float 存，這個誤差還會更嚴重，輸出變成了 3141592792602509312，從小數點後第 7 位開始就不對了。

雖然 float 造成的誤差聽起來非常悲慘，但 double 聽起來好像滿準確的？感覺應該不會造成太大的問題吧？計算結果也只會跟正確答案差一點點而已。然而，微小的誤差也可以帶來非常巨大的影響，以下是一個很著名的例子：

cpp

std::cout << (0.1 + 0.2 == 0.3 ? "true" : "false") << "\n";

這個程式碼竟然輸出了 false！不僅微小的誤差會讓我們在比較數字是否相同時發生問題，微小的誤差還可能會累積成巨大的誤差，像是：

給定整數 $A, B, C, D$，計算 $\frac{A}{B} - \frac{C}{D}$。

如果我們選擇用 double 直接硬算出兩個分數在進行相減的話，會撰寫出下面這隻程式碼：

cpp

#include<iostream>
#include<iomanip>
using namespace std;
int main(){
    double A, B, C, D;
    cin >> A >> B >> C >> D;
    cout << fixed << setprecision(20) << A / B - C / D << '\n';
    return 0;
}

如果我們試著對這段程式碼輸入以下測資：

$A = 999999000$
$B = 99998$
$C = 1000000000$
$D = 99999$

那麼，我們便會得到 9.90298069614800624549 的結果。這與正確的答案 9.90298069614923015535... 相差了超過 $10^{-12}$，聽起來沒有很多，但要是問題變成了

給定 $N$ 組整數 $A_i,B_i,C_i,D_i$，計算 $\sum_{i=1}^N (\frac{A_i}{B_i} - \frac{C_i}{D_i})$。

要是每次計算 $\frac{A_i}{B_i}-\frac{C_i}{D_i}$ 我們都會多出 $10^{-12}$ 的誤差，最後加總起來時，這個誤差就會滾雪球般地疊起來，要是 $N$ 是 $10^6$，那可能就會有高達 $10^{-12} \times 10^6 = 10^{-6}$ 的誤差，已經比我們剛剛用 float 存下的 $\pi$ 還要不準了！

了解浮點數

在學習怎麼面對浮點數誤差帶來的問題之前，我們先簡單暸解一下浮點數到底是怎麼儲存在電腦裡的。和整數一樣，浮點數也是以二進位儲存的。我們平常要在紙上寫下一個十進位的小數時，可能會選擇用形如 $a \times 10^b$ 這樣的科學記號來記錄一個數字，而電腦則是使用了形如 $a \times 2^b$（$1 \leq a < 2$）的二進位科學記號。

如果我們試著用 sizeof(float) 和 sizeof(double) 來得知它們的大小，會得到它們分別有 4 個 byte 和 8 個 byte。一個浮點數在儲存的時候，它會被分成三段：

sign：只有 1 個 bit，表示這個數字是正的還是負的。
exponent：科學記號裡面寫在 $2$ 上面的指數，也就是以上的 $b$。
- 這個數字並不是用二補數之類的方法存的，它本身是一個 unsigned 整數，每個浮點數型態都會有一個指數的偏移量，存在這裡的數字減去這個偏移量後才是真正的指數、真正的指數加上這個偏移量才是存在這裡的數字。
- 例如 double 的 exponent 有 11 bits，偏移量是 $1023$，所以在 double 想要儲存指數是 $-1000$ 的時候，會儲存 $-1000+1023=23$，也就是二進位的 $000\,0001\,0111$。
- exponent 是最大值或最小值的時候（所有 bit 全部都是 $0$ 或全部都是 $1$）會被用來表示這是一個特別的浮點數，像是 $0$ 是以 exponent 存 $0$、fraction 也存 $0$ 來表示的，而 sign 決定了這是 $+0$ 還是 $-0$。（$0$ 竟然有分正負，酷吧！）
fraction：以上的 $a$ 的小數點以後的位數（因為 $1 \leq a < 2$ 時小數點以前總是 $1$，也就沒有必要存下來了）。
- double 的 fraction 有 52 bits，所以如果 fraction 存了 $x$，實際表示的意義是 $1+ \frac{x}{2^{52}}$。

所以說，一個 double 的 exponent 可以表示 $-1022 \sim 1023$ 之間的數字，而 fraction 的精度最多到二進位的小數點後第 $52$ 位，當一個數字無法精準的被如此表示時，電腦就只能存下一個差不多的、可以被這樣表示的數字了。這也告訴了我們為什麼 0.1 + 0.2 不等於 0.3，就是因為 $0.1$、$0.2$ 和 $0.3$ 在二進位中都是無限小數，微小的誤差就造成了這個結果。double 大約會帶來 $2^{-52} \approx 2 \times 10^{-16}$ 的精度誤差。

這一切的規則是在一個叫作 IEEE 754 的標準中規定的，事實上它遠不只我們所講的這麼單純，例如還有 nan、inf 之類的特殊浮點數存在，不過在程式競賽中通常不會用到它們。

浮點數誤差怎麼辦

相信讀者已經意識到了浮點數誤差會帶來不少問題，那我們應該要怎麼辦呢？

使用高精度的浮點數

大多數的浮點數誤差都是儲存精度的上限造成的，因此我們可以用更高精度的浮點數來解決這個問題。首先就是除非特殊狀況，不然不要使用 float，它的精度保證直接低於大多數的題目容許的誤差範圍。一般來說，double 就已經相當夠用了，但有時候還是會遇到 double 不夠用的狀況，像是 double 的 fraction 只有 52 bits，比 long long 的 64 bits 來得少很多，所以要是想精準存下一個 long long 範圍的數值，double 是不夠用的。C++ 中更高精度的浮點數型態還有 long double 跟 __float128。

long double 在 C++ 標準中只被要求至少跟 double 一樣精確，不過多數的編譯器和環境下它總共有 80 bits 的長度，fraction 有 63 bits，是足夠存下 long long 範圍的數字的。
__float128 顧名思義就是有 128 bits，fraction 有高達 112 bits 這麼多。要注意的是它不在 C++ 標準之中，C++23 起才新增了 std::float128_t 這個型態。

在非常誇張的要求精準浮點數的題目，才會用到 __float128。

不要用浮點數

既然浮點數問題很多，不僅有誤差而且運算還比較慢，那不如能避免就避免。事實上，很多情況下浮點數運算是可以被避免的，例如

有四個整數 $A,B,C,D$，請問是否 $\frac{A}{B} > \frac{C}{D}$。

我們可以移項一下，改成判斷：
\[ A \times D > C \times B \]
有兩個整數 $A,B$，請問是否 $A > \sqrt{B}$。

把兩邊平方，就只需要判斷：
\[ A^2 > B \]

像這樣移項或是把兩邊平方之類的，不改變大小關係、卻能讓需要的數字都變成整數的方法，是可以避免浮點數運算的好用技巧。

除此之外，STL 裡面有一些陷阱，例如不要用 pow(x, 整數)，就算 x 也是整數它也還是一個浮點數函數。還有在把浮點數取整（上下高斯、四捨五入）時常常會有差 1 的問題，這個時候也可以想辦法避免，例如要對一個整數 $x$ 算 $\lfloor\sqrt{x}\rfloor$ 時，可以自己寫一個

cpp

long long sqx = sqrt(x);
while ((sqx + 1) * (sqx + 1) <= x) sqx += 1;

來迴避浮點數。

容許誤差

在逼不得以要使用浮點數的時候，我們可以透過在比較時容許微小誤差來解決比較浮點數的問題，例如

x == y 可以改寫成 abs(x - y) <= eps。
x < y 可以改寫成 x < y - eps。
x <= y 可以改寫成 x < y + eps。

這裡，eps 是一個很小的數字，例如 1e-9。要取多少取決於要比較的數字本身會有多少誤差、題目的保證下可以容許多大的誤差等等，需要仰賴仔細的分析和經驗，將來的章節中我們會學到如何更精準的分析浮點數誤差，以及估計 eps 要取多少。

小結

本篇文章最大的目的，還是希望讀者能夠在各種情況都能夠盡量避免使用浮點數。作為程式競賽的選手，相信或多或少都知道浮點數誤差的存在，但往往，都只有在真正切身體會去踩了一次雷以後，才能真正體會他的可怕。

不過這也不代表我們總是需要對浮點數感到畏懼，文章中介紹了浮點數誤差的原理、以及各種避免的技巧，就是希望讀者能夠學會小心的使用浮點數，並在遇到值域小、運算量少的題目時，靠著自己對浮點數的熟悉大膽使用下去。

在未來的有需要使用浮點數的章節中，我們也會有機會學到該如何好好的應對，讀者在這邊可以先有一個初步的認識、並對浮點數誤差有基本的戒心就好。