引擎技術漫遊指南:有理數與編碼


3樓貓 發佈時間:2023-10-21 04:32:22 作者:TirelessKoriel Language

我們先從一個簡單的問題入手。

1. 什麼是科學計數法?

假設,我們現在要記錄一個數字:317464826129。這是我們老闆的私人戶頭上存款金額。
這個金額比較大,足足有十二位數,大約在三千億左右。
為了防止我們忘記這個數字,我們打算把它記錄下來,但是我們手頭只有一張很小很小的紙片,大約只能記錄六個字符。這個時候我們該怎麼做呢?
幸好我們中間有個聰明人,他提議我們可以使用科學計數法,記下 317e11 這串字符。按照科學計數法的規則,其中 e 就代表 10 的次方,e 後面的數字表示冪數,首位數字後面要加一個小數點。那麼這串字符等同於 3.17 x 10^11 。
這樣我們就用有限的空間存儲了一個超級大的數字。不僅如此,如果還有差不多數量級的金額加進來,我們要計算的數字也比原來的數字小得多。我們雖然丟失了精度,但是三千一百七十億三千一百七十零幾億對於老闆來說區別不大。
就這樣我們完成了一次對超大金額的記錄,這可是好大一筆錢。
從上面這個例子我們可以看出,科學計數法雖然在一定程度上(取決於有效數字位數)丟失了精度,但是換來的是更小巧的存儲空間和更便捷的計算過程。而且科學計數法不僅對很大的數字有效,對於那些很小的數字(絕對值無限接近於零),同樣有效。例如:317e-11 = 0.00000000000317。這是一個很小的數字,科學計數法一樣以便捷的方式記錄了它。
那麼,說了這麼多,科學計數法與有理數的編碼又有什麼關係呢?
讓我們來做一個小小的嘗試。

2. 創造一套有理數的編碼規則吧

首先,我們就以常見的 32 位二進制數來存儲我們的有理數。之後以我們樸素的想法,我們可能會直接想到就將有理數分為整數和小數部分,然後分別用二進制表示它們,再將它們組合到一起。
我們可以用一個具體的例子來嘗試一下,比如 32.16 這個數字,按照上面我們定下的規則,表示為二進制就是 100000.10000。這只是比較直觀的形式,計算機實際存儲這個數字的時候,要將 32 位二進制全部補滿。32位二進制中我們要預留一位用來表示正負,剩下的31位分為兩半,整數部分各佔15位,小數部分佔16位,那麼 32.16 這個數字在計算機中實際的存儲形式應該是:
100000000010000000000000000010000
這種做法非常簡單,而且看起來好像還不錯。
那我們可以試著計算一下在這種方式下,有理數在精度方面表現如何。
整數部分是 15 位二進制,精度即為 2^15 = 32768
小數部分是 16 位二進制,精度即為 2^16 = 65536
這麼一看這種有理數的編碼方式在精度方面的問題很大:它的整數部分能表示的最大值太小,小數部分能表示的最小值又太大。
而且由於整數部分與小數部分所包含的二進制位數是固定的,所以在實際使用中,有很大可能導致數位的浪費,例如我們想用這個規則存儲圓周率,3.1415926,這時我們的規則將導致小數部分不夠用(1415926 > 65536),而整數部分只用到了兩位(3 二進制即為 11)。小數部分不夠用,而整數部分卻還有餘,這種情況下我們可以說整數位有 12 位被“浪費”了。
我們還可以從其他角度來進一步理解這種所謂“浪費”。例如,在航天工程中,地月距離 384403 千米,從行星與衛星的角度來看,這種數值已經可以算是精確的了,我們不會在意這個數字後面的小數部分。但是在航天相關的計算機程序中,從計算或各種算法的角度出發來考慮,你不能保證這個數值的存儲就一定能用整形(int)。如果用有理數存儲,那麼上面提到過的“浪費”就又發生了。
這種例子在各種工程中不勝枚舉。
那麼,從上面這次失敗的嘗試中,我們或許能得到一條關於有理數編碼規則的重要啟迪:在對有理數進行編碼時,如果整數與小數部分所佔的位數可以動態的浮動就好了 。
也就是說,當我們的有理數足夠小(絕對值接近零),那麼小數部分所佔位數就會增加,這樣就能保證小數部分的精度;當我們的有理數足夠大(絕對值遠離零),我那麼整數部分的所佔位數就會增加,這樣就能保證整數部分的精度。這種“浮動”能給我們的編碼規則更強的適應性。
對,浮動,整數與小數佔位比例能浮動的數。

3. 那我們就叫它浮點數吧

我們以數字 19.625 為例,我們先來處理整數部分。
我們要將整數部分 19 轉換位二進制數,用“除二取餘”法來計算,即,首先將目標整數除以二,得到的商作為新的目標數繼續除以二,重複上述過程,直到商為零。將此過程得到的所有餘數,依次從右到左(從低位到高位)排列,就得到了該整數的二進制表示形式,我們來演示一下計算過程:
19 ÷ 2 = 9 餘 1;
9 ÷ 2 = 4 餘 1;
4 ÷ 2 = 2 餘 0;
2 ÷ 2 = 1 餘 0;
1 ÷ 2 = 0 餘 1;
19 的二進制表示即為:10011
接下來我們以類似的方法,來將小數部分的數值轉化為二進制,小數部分的處理叫做“乘二取整”法,即將目標小數乘以二,再取結果小數部分繼續乘以二,重複以上過程,直到小數部分消失。將此過程中產生的整數部分(非 1 即 0)依次從右到左(從低位到高位)排列,就得到了該小數的二進制形式:
0.625 x 2 = 1.25 ,整數部分為 1;
0.25 x 2 = 0.5 ,整數部分為 0;
0.5 x 2 = 1 ,整數部分為 1;
0.625 的二進制表示即為:0.101
我們可以觀察到,小數部分轉為二進制時,與整數部分的方法是對稱的,鏡像的。一個是除二取餘,一個是乘二取整。我們可以通過一個數軸,來進一步的感受這種對稱:
圖中最上方綠色數值組成了一個簡單的橫向數軸,最大值為 4,最小值為 -4 。
觀察數軸下方白色數字可以看出,數軸的值表示 2 的冪數,數軸下方藍色數字表示相應的冪數下的值。我們可以通過這個數軸來快速對整數部分進行二進制轉換:
因為,16 + 2 + 1 = 19,所以 16,2,1位置處的二進制為 1,即 19 的二進制表示為 10011。
同樣的,這個數軸還可以用相同的方法來快速轉換小數部分的值:
因為 0.625 = 0.5 + 0.125,所以 0.5 ,0.125 位置處的二進制為1,即 0.625 的二進制表示為 0.101
這兩個結果與前面我們計算得到的值是一致的,同時我們還能從數軸上看到兩種方法的對稱性。
這種方法與我們自己創造的有理數編碼非常不同,雖然看起來和處理整數部分的方法如此對稱,但是給我們的最直觀的感受是這種方式更加複雜,那麼我們為什麼要這麼處理呢?
原因就是這種處理方式與我們前面提到的所謂浮動更加契合。我們可以用一個例子來展示其中的原理。
假設我們現在有一個很大的數字,它的整數部分為 134217728。為了能保證整數部分的數字保存完整,我們給整數部分分配了 28 位二進制。那麼也就是說,我們只有 4 位二進制可以用來表示小數了。
4 位二進制用來表示小數的精度又如何呢?我們來計算一下。
0.0001 = 0.0625
0.0001 + 0.0001 = 0.0010 = 0.125
0.0010 + 0.0001 = 0.0011 = 0.1875
……
觀察上述計算過程我們能夠發現,按照這種編碼規則,只有 4 位二進制的小數能表達的值都是 0.0625 的倍數,也就是說,這個小數的值不僅不是連續的,能表示的連續的兩個數字之間的間隔甚至非常大!我們甚至無法表示 0.0626。這種精度看起來是無法接受的。
但是,我們的整數部分整整有 134217728 這麼大,從工程的角度來說,這個時候我們還會在意小數部分的大小嗎?可以說這種精度的浮動,正是我們想要的結果!
讓我們再進一步,我們將小數部分的位數增加到 5,再來看一下精度:
0.00001 = 0.03125
0.00001 + 0.00001 = 0.00010 = 0.0625
0.00010 + 0.00001 = 0.00011 = 0.09375
……
觀察可以發現,當我們提升了小數部分所佔位數,這種編碼方式下的小數精度也提升了。所佔位數為 4 時,小數間的間隔為 0.0625,所佔位數為 5 時,小數間的間隔為 0.03125,提升了一倍。我們不難推測,隨著小數部分所佔位數提升,小數間的間隔也會更小,更小的小數間隔代表著更加連續(雖然還是離散的)小數排列,同時也代表著精度的提高。
上面的計算過程說明了浮動機制在這種編碼規則下,是如何保證精度平衡的(整數與小數部分)。
那麼接下來我們要面臨的問就是,我們該如何浮動呢?
我們最開始討論過的科學計數法,就是用來解決這個問題的。
還是以上面提到過的數字 19.625 為例,我們上面計算得到的整數部分與小數部分結合起來即為:10011.101
我們嘗試用十進制的科學計數法來類比二進制的科學計數法,我們能得到 10011.101 科學計數表達形式:1.0011101 x 2^4,注意!這個地方很重要,2 的 4 次冪表示我們將小數點向左移動了 4 位(與十進制的科學計數法規則一致,只不過這裡是二進制,所以是 2 的指數),此時我們原本數字的正數部分與小數部分共同組成了科學計數法表達後的小數部分!
想要保存這個形式的數字,我們只需要三個關鍵值:一是數字的正負號,簡稱符號;二是記錄這個形式下的小數部分,即 0011101,我們可以把它稱為尾數;三是 2 的冪數,即 4,它代表了我們的小數點移動了幾位,所以我們可以把它稱為偏移指數。有了這三個關鍵值我們就能回溯出原始的二進制值。
那麼為了保存這三個關鍵值,我們可以將 32 位二進制,做以下這種分隔:
結合上圖所示與我們的例子,我們可知:
首位是符號位,19.625 位正數,所以此位為1;
後 8 位是偏移指數位,1.0011101 x 2^4 中 2 的指數為 4,即小數點偏移了 4 位,所以此位補滿 8 位後為:00000100;
後 23 位是尾數位,1.0011101 x 2^4 中尾數為 0011101,所以此位補滿 23 位後為:00111010000000000000000。
正如我們上面提到過的,科學計數法導致我們的小數點發生了偏移,就本例來說,我們的小數點向左偏移了 4 位,也就是說我們的整數部分與小數部分共同組成了尾數,尾數位部分的位數有限,所以整數部分與小數部分在組合的同時,也完成了對尾數位的分配。整數部分越大,它在尾數位中所佔位數就越高,小數部分所佔位數就越小。
這還沒完,在我們為 10011.101 做科學計數法表達時,小數點是向左移動的,這是因為我們的目標值 19.125 是一個帶有整數位的數字,如果我們是一個比較小的小數呢?
例如,我們現在有一個數字 0.15625,二進制轉換後為 0.00101,科學計數法表達為 1.01 x 2^-3。該科學計數的尾數為01,這很簡單;問題是指數為 -3 ,我們該如何在指數位中表達負數呢?
我們只需要模仿現有的符號位,將偏移指數位的首位作為指數位的符號位即可。當偏移指數位的首位變為偏移指數的符號位時,我們原本的 8 位二進制就縮減為 7 位,最大值為 1111111 = 127。那麼如果偏移指數為正數時,我們就將偏移指數加上 127 ,得到的結果轉為二進制時,便自然會變成8 位,並且首位為 1 ,這就自動完成了首位表示符號位的操作。
我們展示一下過程。
十進制:127 + 1 = 128
二進制:01111111 + 0000001 = 10000000
這就免除了其他附加操作,只需要以 127 為基礎做加法,就能自動完成符號位的匹配。
所以 0.15625,科學計數位 1.01 x 2^-3,用我們的編碼方式編碼後,在計算機中的二進制表示就是:
1 01111100 01000000000000000000000
其中偏移指數為的計算為,127 + (-3)= 124 = 01111100,可見偏移指數為首位為 0,與偏移指數值 -3 符號匹配。
同理,因為我們重新定義了指數位,所以我們也要修改 19.125 在計算機中的二進制表示:
1 10000011 10010010000000000000000
其中偏移指數為的計算為,127 + 4 = 131 = 10000011,可見偏移指數為首位為 1,與偏移指數值 4 符號匹配。
其實通過對偏移指數位的理解,我們還會發現一個問題。偏移指數位共有 8 位,拋開符號位還剩 7 位,也就是說,小數點向整數偏移時,最多能偏移 127 位,加上整數位的1(例如1.01 x 2^-3,整數位必然為1),也就是說,這種編碼方式能保存的值最大為 2^128 = 3.4*10^38,但是我們實際存儲數值的二進制位數只有 23 位,這好像並不合理。
這個問題的答案其實還是我們之前討論過的極大值不在乎極小值的道理。3.4*10^38 尺度的值,不會在意小數,甚至不會在意上億的值,上千億的值上萬億的值它都不在乎,這些值對於它來說,都太小了。當數值巨大時,科學計數法會驅動小數點瘋狂的向整數方向移動,那些被小數點拋棄,並且無法被 23 位二進制容納的數值都會被拋棄。也就是說,這種情況下,不僅小數會被無視,連那些不夠大的整數部分也會被忽略。這麼看來,對於極大的整數來說,我們的編碼規則會捨棄精度來換取對極大值的包容。
對於小數來說正好相反。我們的編碼機制會使得越小的值精度越高。這個機制我們在上面關於數軸的討論中就提到過,總結來說就是在這個編碼規則下,極小數的精度就是極小數本身。
這正是我們想要達到的效果:值越大,精度越低,因為大值不在乎小值;值越小,精度越高,因為越小的值越在乎自己能有多小。
以上所述,就是 IEEE754 標準,它被廣泛適用於浮點數的編碼操作。
最後我們可以再來做兩個試驗,來驗證我們對規則的描述是否正確。
我們可以查詢到,通常 32 位浮點數的精度為:±1.18*10^-38 ~ ±3.4*10^38。
其中 ±3.4*10^38 符合我們對偏移指數做進一步解釋時所提到的最大整數值。
接著我們驗證一下最小絕對值 1.18*10^-38。
由偏移指數位的編碼規則可知,當小數點向小數偏移時,最多能偏移 126 位,即這種情況下最小值為:2^-126 =
驗證成功。

© 2022 3樓貓 下載APP 站點地圖 廣告合作:asmrly666@gmail.com