contributed by < Hlunlun >
實作 ldexpf
: https://man7.org/linux/man-pages/man3/ldexp.3.html
在 Linux kernel 中可能無法使用 FPU 做運算,所以需要將浮點數轉成二進位制做運算
The function returns the result of multiplying the floating-point number x by 2 raised to the power exp.
一開始想法
先將 float
轉成 unsigned
然後再去取 sign
、exponent
、mantissa
根據 https://www.h-schmidt.net/FloatConverter/IEEE754.html 表示法去嘗試當 x
是 -1.2345 印出 sign
、exponent
、mantissa
但除了 sign
其他都不對,如下
檢討
關於浮點數和整數的轉換可以看到以下 C99 的說明,如果浮點數轉換成整數時會捨棄小數點的部分
C99 [6.3.1.4] Real floating and integer
When a finite value of real floating type is converted to an integer type other than _Bool, the fractional part is discarded (i.e., the value is truncated toward zero).
所以,當我用 cast operator 直接將 x
轉為 unsigned
時,x
就會只剩整數位的 ,雖然可以取到正確的 sign
,但根本取不到正確的 exponent
和 mantissa
expression | 十進位表示 | 二進位表示 |
---|---|---|
x |
||
(unsigned)x |
分析
了解浮點數和整數轉換的問題後,我們知道不行直接將浮點數用 cast operator 轉換成整數,而是用 union
對同一塊記憶體取不同型態的數值,這種 type punning 類別重疊 的說明如下
C99 [6.5.2.3] Structure and union members 底下的補充說明
If the member used to read the contents of a union object is not the same as the member last used to store a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type as described in 6.2.6 (a process sometimes called "type punning"). This might be a trap representation.
此處提及的 trap representation 在 C99 [6.2.6.1] 有解釋到:
問題
出自 C99 [6.2.6.1]
Certain object representations need not represent a value of the object type. If the stored value of an object has such a representation and is read by an lvalue expression that does not have character type, the behavior is undefined. If such a representation is produced by a side effect that modifies all or any part of the object by an lvalue expression that does not have character type, the behavior is undefined.41) Such a representation is called a trap representation
unsigned
去 cast 浮點數後輸出的 是代表 還是未定義 NaN
?TODO: 所以是怎麼取值的
所以將浮點數轉為二進位數的方式如下
取出 sign
, exp
, frac
;
轉換為二進位置後,就可以來看要怎麼進行相乘運算
浮點數的二進位制運算
更多浮點數的運算可以看到教材 CS:APP 第 2 章重點提示和練習,所以取得 sign
、exp
、frac
就可以進行單精度浮點數和 的乘法運算了,以下使用 為例
首先浮點數編碼成二進位的方式為
也就是我們只要找到 (sign) 、 、 就可以運算浮點數和 的乘法, 已經知道是 ,將 轉換成二進位制會是無限循環,由於是單精度浮點數,所以就取到 位即可
Significand:
Exponent
Result
現在回到題目,我們這個時候會取得需要相乘的 2 的 次方,而 2 的次方 2 的冪 之間的相乘就是將次方數直接相加,如下
而此時的 會變成
那其實剛剛已經取出 sign
、exp
、frac
,所以可以直接將 n
加到 exp
那最後的答案就會是這三個值的 logical or
完全不會動到 frac
和 sign
,只要處理 exp
的部份,其實只要理解浮點數在電腦中的編碼模式就能解這題了
最後回傳 val.f
就是答案
測試
CS:APP 第二章 有提到浮點數編碼後會有三種狀態
在運算 new_exp
之前可以先檢查 x
是否為有效值
x
是 NaN
,其實就是在檢查 exp
的部份
x
是無限大或無限小
x
是 0
再來需要檢查 new_exp
是否為有效值
new_exp
overflow
因為 只有 8 個位元,所以需要檢查 new_exp
是否超過 也就是二進位制的
new_exp
underflow
x
是 normal 但輸出為 denormal
完整程式碼
參考
my_ldexpf
改進驗證不夠,且需要更精簡
因為我們可以取得的有意義的值就是 normalized的部分,在單經度浮點數的世界的話就是
所以可以在最後算完 exp
後直接和 0xff
用 logical and 取出有效範圍,然後再
幾何平均數
定點數
在 維基百科 介紹中描述了定點數表示法中,整數和小數的部分會用相同底數 來表示(就是會是一樣是十進位或是二進位),如果此有禮數的小數的部分到第 位,此有理數會是 的整數倍
In the fixed-point representation, the fraction is often expressed in the same number base as the integer part, but using negative powers of the base b. …Thus, if n fraction digits are stored, the value will always be an integer multiple of .
乍看之下,其實跟浮點數很相似,都是表示有理數的一種方式,但是可以看到,定點數會有 scaling factors 可以讓數值表示成整數在運算,如下:
假設我們現在要將 和 相乘,我們可以想成這兩個定點數相乘
縮放因子在此次運算中即為
此時就可以不用用到 FPU 的將兩個整數相乘
最後再去乘上縮放因子即可得到結果
回到 linux kernel 中的浮點數相乘,我們如果可以用定點數的概念,那麼就可以用以下步驟得到結果
浮點數相乘
CMU CS:APP 課程中 Floating Point 講義第 27 頁提到 有關於浮點數編碼成二進位的乘法運算
開根號
因為浮點數是轉換成二進位制,所以需要轉換成底數為 2 的冪,算出指數的部分 ,就可以直接和 做運算
運算 的部分則可以透過以下時做完成
參考
作者 Opass 的在開發自動手搖飲料機的過程就如同 Linux Torvalds 的那句話:「我是看著地面的人,我想修補就在我面前的坑洞,以免跌進去。」