新博客pppppkun

寫(xiě)在前面

在PA_2019fall中有一項(xiàng)任務(wù)是完成CPU中的浮點(diǎn)數(shù)運(yùn)算，這也是我第一次認(rèn)真的思考了一下真實(shí)的計(jì)算機(jī)中CPU是如何進(jìn)行的浮點(diǎn)數(shù)運(yùn)算

在寫(xiě)PA的過(guò)程中一頭霧水，從迷茫，到困惑，到弄懂，到完成，中間經(jīng)歷了各種坎坷，又無(wú)奈于手上的資料僅僅只有一個(gè)Guide和i386，剩下不會(huì)的地方全靠百度

于是就誕生了這一篇博客，把其中的過(guò)程給大家講的明明白白的！

預(yù)備知識(shí)

什么是浮點(diǎn)數(shù)？浮點(diǎn)數(shù)表示的是一個(gè)數(shù)字，其小數(shù)點(diǎn)所在的位置是不確定的，也就是浮動(dòng)的，因此稱(chēng)之為浮點(diǎn)數(shù)

在IEEE 754標(biāo)準(zhǔn)中，單精度的浮點(diǎn)數(shù)由3部分組成

符號(hào)位，在首位，用1表示負(fù)數(shù)，0表示正數(shù)
階碼 $exponent$ 部分，一共八位，采用移碼形式，偏置常數(shù)為127
尾數(shù)部分，一共23位。

規(guī)格化于非規(guī)格化

規(guī)格化的數(shù)表示階碼部分不是全都為0，其23位的尾數(shù)實(shí)際上表示了24位，最高缺省位為1。而非規(guī)格化的數(shù)沒(méi)有缺省位。

尾數(shù)加上最高位可能存在的缺省的1后構(gòu)成的有效數(shù)字稱(chēng)為 $significand$

實(shí)現(xiàn)之前的思考

排除特殊情況

Simple

根據(jù)表格我們可以先把邊界條件排除掉，比如 $+0,-0, +\infty, -\infty,NaN$

加減

如何讓兩個(gè)浮點(diǎn)數(shù)相加？根據(jù)上面的知識(shí)我們知道兩個(gè)浮點(diǎn)數(shù)的形式基本可以這樣給出 $1.ababab*2^{exponent}$ ，我們很容易就能想到兩個(gè)浮點(diǎn)數(shù)是不能直接相加的，應(yīng)該讓他們同階后再將尾數(shù)相加，這個(gè)操作我們叫對(duì)階

對(duì)階

對(duì)階有兩種方式，小階往大階對(duì)齊和大階往小階對(duì)齊，該如何選擇呢？

不妨考慮一下這樣的事情，在IEEE754表示的浮點(diǎn)數(shù)中，對(duì)于相同的階數(shù)來(lái)說(shuō)，尾數(shù)中越靠后面的1對(duì)最后結(jié)果的影響越小。

在對(duì)階中，如果大階向小階看齊，那么實(shí)際上是將尾數(shù)左移，小階向大階看齊的話(huà)就是尾數(shù)右移。

如果我們選擇大階向小階看齊，那么我們很容易就將尾數(shù)中靠前的1給左移沒(méi)了，因?yàn)槲矓?shù)一共只有23位，這樣對(duì)計(jì)算造成的誤差相當(dāng)大，所以我們選擇小階向大階看齊

注：考慮如何減小誤差是浮點(diǎn)數(shù)運(yùn)算中非常重要的一環(huán)

對(duì)階中的特殊情況

在處理非規(guī)格化浮點(diǎn)數(shù)的時(shí)候，它們的階碼全都是0，但是尾數(shù)并非是0，其表示的真實(shí)值為 $0.f*2^{-126}$ ，不能將階碼理解成-127，在后面會(huì)講為什么會(huì)有這樣的結(jié)果。

`shift`的計(jì)算

在此，我們已經(jīng)可以給出右移的位數(shù) $shift$ 了，在這里我們假設(shè) $fb.exponent>fa.exponent$

shift = (fb.exponent==0 ? fb.exponent+1:fb.exponent) - (fa.exponent==0? fa.exponent+1:fa.exponent)

最后我們得到的臨時(shí)的階碼就是 $fb.exponent$

流程圖

先讓我們把目前的東西總結(jié)一下，后面結(jié)合實(shí)際栗子來(lái)講也會(huì)更加清晰

流程圖

在這個(gè)圖中，我們可以看到在對(duì)階之前先判斷了 $X,Y$ 的值是否為0，如果不是那就開(kāi)始對(duì)階

在對(duì)階的過(guò)程中，小階慢慢變大，這會(huì)導(dǎo)致尾數(shù)右移（前面已經(jīng)提到過(guò)），在尾數(shù)右移的過(guò)程中，我們有可能把尾數(shù)移為23個(gè)0，如果是這樣，我們簡(jiǎn)單的判斷為是階數(shù)小的數(shù)實(shí)在是太小了，就像10億+1，那個(gè)1加不加我們可能都沒(méi)有直觀(guān)的體驗(yàn)

再接下來(lái)，我們對(duì)尾數(shù)進(jìn)行相加，這個(gè)過(guò)程中要考慮符號(hào)位，如果是做減法，那就對(duì)減數(shù)的尾數(shù)位采用廣義上的 取反加一

相加完后，如果尾數(shù)變成0，那結(jié)果就是0，如果不是0，那就考慮一下尾數(shù)有沒(méi)有溢出（尾數(shù)溢出指相加后最高位缺省位達(dá)到了2）。如果溢出了，那我們就右移一次，然后判斷一下階數(shù)的情況即可

要是沒(méi)有溢出，那當(dāng)然萬(wàn)事大吉，但是我們接下來(lái)還需要將我們的浮點(diǎn)數(shù)規(guī)格化一下，意思是規(guī)格化的浮點(diǎn)數(shù)為 $1.ababab*2^{exponent}$ ，但是我們計(jì)算出來(lái)的浮點(diǎn)數(shù)可能是 $0.0000ab*2^{exponent}$ ，那么我們需要小數(shù)點(diǎn)移位，降低階數(shù)，將最高缺省設(shè)置成1

當(dāng)然，規(guī)格化的過(guò)程中階數(shù)也有可能等于0，這里需要一次特判。

小小的總結(jié)

到這里浮點(diǎn)數(shù)的加減基本上已經(jīng)介紹完了，對(duì)于乘除法就很簡(jiǎn)單了，只需要將指數(shù)相加，尾數(shù)相乘就行了，當(dāng)然，其中涉及到的一些溢出情況都需要單獨(dú)判斷，在這里不多做討論

附加位與舍位

一個(gè)貼近生活的栗子

加入你是億萬(wàn)富翁，你的銀行卡中有1000億元，你每天穩(wěn)定收入1000元，但是由于銀行的計(jì)算機(jī)用的是上面的實(shí)現(xiàn)方法，這1000塊錢(qián)在放進(jìn)你的卡中的過(guò)程中需要進(jìn)行對(duì)階，對(duì)著對(duì)著尾數(shù)變成了0，相當(dāng)于你存進(jìn)去0塊

那么該怎么辦呢？當(dāng)然你可以設(shè)置一些if語(yǔ)句，讓1000加多點(diǎn)，加到足夠影響1000億的時(shí)候再一起加上去，這是目前計(jì)算機(jī)的一個(gè)研究方向之一。

附加位

根據(jù)IEEE754的規(guī)定，所有浮點(diǎn)數(shù)運(yùn)算的中間結(jié)果右邊都必須至少保留兩位的附加位，依次是保護(hù)位(guard,G)和舍入位(round,R)，為了進(jìn)一步提高精度，舍入位的右側(cè)還有一個(gè)粘位(sticky,S)，只要舍入位右邊有任何非0的數(shù)字，粘位就是1，否則為0。

我們簡(jiǎn)稱(chēng)這三位為 $GRS$ ，下面用一個(gè)實(shí)例來(lái)展示一下它的作用

保護(hù)位

x = 1.000..00 * 2^1  y = 1.11...11 * 2^0
// without guard bits
  x = 1.000...00 * 2^1
- y = 0.111...11 * 2^1
  z = 0.000...01 * 2^1
    = 1.000...00 * 2^-22
// with guard bits
  x = 1.000...00 0000 * 2^1
- y = 0.111...11 1000 * 2^1
  z = 1.000...00 0000 * 2^-23

可以很明顯的觀(guān)察到，在多了保護(hù)位后，計(jì)算結(jié)果明顯更精確了

但是解決了一個(gè)問(wèn)題后又出現(xiàn)了第二個(gè)問(wèn)題，那就是我們的尾數(shù)只有23位，就算我們使用了保護(hù)位，也只能保護(hù)計(jì)算過(guò)程中的誤差，那么對(duì)于結(jié)果來(lái)說(shuō)，依然有可能不精確

所以接下來(lái)，我們引入舍位

舍位

為了保證運(yùn)算過(guò)程中的最大精確度，我們會(huì)把23位+3位附加位的浮點(diǎn)數(shù)擴(kuò)展到64位，相加完后再進(jìn)行規(guī)格化，規(guī)格化完后我們要對(duì)這三位進(jìn)行舍入操作。舍入的方法采用就近舍入，中間值4按照奇偶來(lái)舍入，確定舍入后，完成尾數(shù)的后三位右移操作。

缺陷

我們不妨考慮這個(gè)栗子
$652.13+(-7.48)=644.65$

\\省略對(duì)階
 1 010001100       1 010001100 000000
-0 000000111       0 000000111 011110
 1 010000101       1 010000100 100010
   645.0                  644.0

就算有了舍位，在單精度下我們依然很難給出兩個(gè)浮點(diǎn)數(shù)加減的準(zhǔn)確答案。

關(guān)于浮點(diǎn)數(shù)的表示

如果都是規(guī)格化的浮點(diǎn)數(shù)，那么我們很容易知道我們是沒(méi)法表示0的，因?yàn)樽钚【褪?img class="math-inline" src="https://math.jianshu.com/math?formula=2%5E%7B-127%7D" alt="2^{-127}" mathimg="1">，所以為了表示0，我們將 $2^{-127}$ 和 $-2^{-127}$ 的和用來(lái)表示0，那 $2^{-127}$ 該怎么辦呢？

為了填上0到 $2^{-127}$ 這段上的實(shí)數(shù)，我們?cè)O(shè)置了非規(guī)格化的浮點(diǎn)數(shù)，并且將 $2^{-127}$ 到 $2^{-126}$ 的數(shù)擴(kuò)展到了整個(gè)0到 $2^{-126}$ 上，這之間的每個(gè)數(shù)間隔都是一樣的

最大的數(shù)為
$0.1..1*2^{-126} = (1-2^{-23})*2^{-126}$

其中每個(gè)數(shù)的間隔都是
$0.00..1*2^{-126} = 2^{-149}$

$2^{-126}$ 和最大數(shù)之間的距離是
$2^{-126} - (1-2^{-23})*2^{-126} = 2^{-149}$

Summary

Floating-point representation
Operations
- Addition
Precision Consideration