[Math] Office Work - Single Precision Error from Decimal to Floating

電腦是以1、0表示所有資料，基本如數字也是這樣，為了在同樣容量下儲存更多或更準確的數字，便先要指定格式。例如以32Bit的單位下，如果我們想記錄「整數」，先有1 Bit用了表示正負數，餘下的31 Bit就只可以記錄$2^{31}$個數，所以32 Bit最大的正整數是$2^{31}-1 = 2147483647$。如果電腦要紀錄更大的數值，就要指定要其他的儲存容量（例如Long Integer:用多一倍的單位64Bits）或其他的儲存方式（例如Float:$1.0 \times 2^{128}$）。

以印尼银行（Bank Indonesia - 印尼的中央銀行）的印尼盾匯率為例：印行會用當日雅加達時間上午8.00-9.45銀行間同業交易的USD/IDR即期匯率，計算加權平均，然後在上午10.00公佈該這個參考價－雅加達銀行同業即期匯率(JISDOR)，和現時22種貨幣的參考匯率，發佈的數字只有買入價、賣出價，並沒有中間價。

要知道一般大眾看的就是中間價。談到日元歐元下跌又是旅行良機時，你不會分別說買入賣出價是多少。某數據供應商亦合理地有提供中間價 ( =(買入＋賣出)/2 )。只是，數據商預設準確至2個小數位(2 d.p.) ，當我們留意這個數據的準確性時，卻偶然出現細小的誤差，例如：

中國 CNY: （2075.81＋2055.24）／2 ＝2065.525
馬來西亞 MYR：（3177.46＋3213.83）／2  ＝3195.645
但報出來的中間價分別是MYR:3195.65、CNY:2065.52，湊整時對0.005的處理一個是向下捨去、一個是向上進位，這點並不一致⋯⋯

然後（多次嘗試、詢問、查找後），終於了解到這是小數和浮點數間的誤差所以做成，用這個IEEE 754 Converter：
Ask:2075.81 會儲存為 $1.0135791301727295 \times 2^{11}$，大約是2075.8100585..
Bid:2055.24 會儲存為 $1.0035351514816284 \times 2^{11}$，大約是2055.2399902..
計算中間價時，Mid:2065.525 會儲存為 $1.0085570812225342 \times 2^{11}$，大約是2065.5249023...當提供預定的2個小數位時，就會湊整為2065.52而非2065.53。

這樣的誤差可以有多大呢？會不會當數據商從印尼銀行得到2個小數位的Bid/Ask儲存成Float後，我們直接拿取2個小數位的Bid/Ask也會出現這個錯誤呢？這樣便要再了解一下背後的運作了。

我們開始時提到電腦如何儲存整數，也有一種Float的格式儲存數字。而32Bit Float為例，先有 1 Bit（Sign）用作表示正負數，之後 8 Bit （Exponent）用作表示2的次方[加上127來避免負號]，最後 23 Bit （Mantissa）用作表示1.xxxxxx。

0	10000101	10010 00000 00000 00000 000
Sign (1 Bit)	Exponent (8 Bit)	Mantissa (23 Bit)

例如100， 用10進制表示可以寫成: $+1.5625 \times 2^{6}$ ，用2進制表示可以寫成 $+1.1001 \times 10^{110}$，表示如下：
100 -  | 0 | 10000101 | 10010 00000 00000 00000 000 |
(Sign：+：$0_{2}$ )
(Exponent：$2^{6}$： $2^{(127+6)} = 2^{133}=10000101_{2}$)
(Mantissa：1.05625： $0.5625=1 + 2^{-1} + 2^{-4} = 10010 00000 00000 00000 000_{2}$)

但有些數字用23個位的Mantissa其實不夠記錄，例如0.1用2進制表示可以寫成 ${+1.1001100110011...(0011)... \times 10^{-10}}_2$ （用10進制表示: $+1.600000023841858...\times2^{-4}$），當中0011會不斷重複，十進制下的0.1轉換成二進制就是循環小數$0.0001011\overline{0011}_2$。 但電腦內只會紀錄23個位、第24個位開始被砍掉的部份就會做成微少的誤差。
0.1  -  | 0 | 01111011 | 10110 01100 11001 10011 001 |（...之後的被砍掉了）

0	01111011	10110 01100 11001 10011 001	10011 00110 .....
Sign (1 Bit)	Exponent (8 Bit)	Mantissa (23 Bit)	Error (0 Bit)

這樣紀錄的話，我們可以明白Mantissa 的誤差就是砍掉的部分，這應該少於$0.00000 00000 00000 00000 001 = 2^{-23}$ ，或是用4捨5入(0捨1入)的話，則應該$\le 1/2 \times 2^{-23} =2^{-24}$。然後這誤差會被Exponent所放大，例如0.1的例子中，最後誤差$\le 2^{-24} \times 2^{-4} = 2^{-28} \approx 3.725 \times 10^{-9}$

回到印尼盾兌人民幣的中間價：
2065.525  -  0 | 1001010 | 00000 01000 11000 01100 110 |

用$float()$表示電腦中將Deciaml轉到為Float並儲存成32Bit的函式，以下運算可見誤差應該少於約0.00012。的確我們可以看到 2065.525 - 2065.5249023 = 0.00009... < 0.00012 的。
$$Error = |2065.525-float(2065.525)| \le 2^{-24} \times 2^{\lfloor log_22065.525\rfloor} = 2^{-13} \approx 0.00012$$

對於一般的數字x, 因為上式會包含x的Exponent, 我們可以改為考慮相對誤差：
$$Rel.Error = \frac{|x-float(x)|}{x} \le \frac{2^{-24} \times 2^{exponent}}{1 \times 2^{exponent}} =2^{-24} \approx 5.96 \times 10^{8} $$

這樣可以看到一個簡單的結果：相對誤差少於$2^{-24}$，大約 0.00000596%。
當給定一個2個小數位的數字 x，float(x)的誤差應該$\ge$0.005才可以被四捨五入至另一個數，$x \times 0.00000596 \% \ge 0.005$，也就是說：最少要大於83886.08的數字才有機會「從印尼銀行得到2個小數位的Bid/Ask儲存成Float後，我們直接拿取2個小數位的Bid/Ask也會出現這個錯誤」。

現在匯率數值最大的科威特大約是 1第納爾兌45,000盾，以上界線只是一個保守的Boundary，應該暫時不會出現0.01的誤差吧。


Useful link:
IEEE 754 Convertor
http://www.h-schmidt.net/FloatConverter/IEEE754.html

What Every Computer Scientist Should Know About Floating-Point Arithmetic
https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html

How to correct rounding errors in floating-point arithmetic
https://support.microsoft.com/en-us/kb/214118