Try   HackMD

2024q1 Homework5 (assessment)

contributed by < marsh-fish >

閱讀〈因為自動飲料機而延畢的那一年〉的啟發

我非常喜歡作者引用了《鋼之鍊金術師》的金句,許多老一輩的人都認為看動漫是件幼稚的行為,但動漫裡頭能讓人學習到的東西非常的多(當然會因作品而異),不應該因自身的「刻板印象」對他人的喜好亂下評斷,但人又何嘗不是如此呢?回到文章,作者在專案前期預期著完美的理想成品,但由許多的理想都難以實現,光是自動掉冰塊機就花了相當多的時間才有成品,我一看到作者初期對自動掉冰塊機的想像,就有相當大的疑問,當下一直在思考「如果是我做的話會怎麼做?」,看到作者想用彈簧實現,就讓我想到當初檳榔去鬚機的出代版本也是用彈簧,後來才改成現在常見的形式,不過後來作者是直接購買冰塊分配器就是了。「三折肱為良醫」究竟是折肱三次方能成為良醫,還是幫助過三個「折肱」人即成為良醫呢?當然,字典會告訴你答案是前者,但若折肱這件事能為你帶來啟發,何必是「自己」來折肱呢?《因為自動飲料機而延畢的那一年》最後的結局雖不是最完美,但就如《灌籃高手》、《棋靈王》這樣的故事,往往能帶給人來更多的感觸,我也不禁感動落淚。

想投入的專案

kHTTPd

改進 Linux 核心的 lib/{list_}sort.c

int mul_10(int x)
{
    // return x * 10
    return (x << 3) + x + x;
}
float float_mul10(float x)
{
    // Using bitwise operation; No mul/div
    unsigned sign =  (unsigned)x >> 31;
    unsigned exponent =  ((unsigned)x << 1) >> 23;
    unsigned frac = ((unsigned)x << 9) >> 9;
    
    unsigned frac_re;
    frac_re = frac << 3 + frac + frac;
    
    unsigned re = (sign << 31) | (exponent << 23) | (frac_re);
    return (float)re;
}

https://numeral-systems.com/ieee-754-converter/

4.0 => 01000000100000000000000000000000
4.9 => 01000000100111001100110011001101

classified as

  • power of 2: copy * 2; copy * 8
  • not power2

TODO: 撰寫程式碼、測試,附上分析

TODO: 研究紅黑樹: https://hackmd.io/@sysprog/rJbMiW3S3 紀錄問題並重現實驗 + extra


TODO: 撰寫程式碼、測試,附上分析

sign, exponent, frac 的值分別以二進制印出,會發現最初程式碼的型別轉換並不能達到我所期望的結果(轉成 IEEE 754 的格式)。

    x = 4.0
    sign = 0
    exponent = 0
    frac = 100

經過嘗試發現可以藉由 unsigned 指標強制轉成 IEEE 754 的格式

    unsigned* p = (unsigned*)&x;
    x = 4.0
    p = 0100 0000 1000 0000 0000 0000 0000 0000
    sign = 0
    exponent = 1000 0001
    frac = 000 0000 0000 0000 0000 0000

將三個區塊個別取出

    unsigned sign = *(unsigned*)&x >> 31;
    unsigned exponent = (*(unsigned*)&x << 1) >> 24;
    unsigned frac = (*(unsigned*)&x << 9) >> 9;
    sign = 0
    exponent = 1000 0001
    frac = 000 0000 0000 0000 0000 0000

可以將乘十分解成乘八加乘二,這裡必須注意的是在 IEEE 754 浮點數的格式中分數 (fraction) 部分最高有效位 (即整數位) 是 1 ,因此在做加法運算的時候需將 1 補上,如下

    frac = (frac << 3) + ((frac | 0x00800000) << 1);

接下來會有兩種情況,進位與無進位,因為兩者要做的位移數不同因此用 if 判斷是否進位,無進位的情況比較簡單,只要補齊指數部分和位移分數部分。進位的情況下,進位的發生是由於我們在先前多加了一個整數一,所以這個整數一必須把他移除,所以對第 23 個 bit 做 AND 運算。

    if(frac >> 26){
        exponent = exponent + 4;
        frac = (frac >> 4) & 0xffbfffff;
    }
    else{
        exponent = exponent + 3;
        frac = (frac >> 3);
    }

最後將 IEEE 754 的格式用與第一步反向的方式轉回浮點數便會得到乘十的結果

    float re;
    unsigned *pre = (unsigned*)&re;
    *pre = ((sign << 31) | (exponent << 23) | (frac));
    return re;

實驗看看各式各樣的值是否正確

x:4.9
49.000000
49.000000

x:3.9
39.000000
39.000000

x:6.4
64.000000
64.000000

x:127.9
1279.000000
1279.000000

在進一步探討會發現使用 x*10 得出的結果會較貼近 x 在程式裡的近似值再去乘十,而用我的函式在大多數的情況會得到較貼近實數乘十的結果,例如 x = 13.4 的時候,印出 x 會得到 13.400015 ,而 x*10 會得到 134.000153 ,我的函式會得到 134.000137,底下列出部分結果。 後來發現此實驗方式有誤,但我認為可以記錄一下,往後在做浮點數的要避免使用浮點數的加法,避開不可預期之事。

在進一步探討會發現在僅有小數第一位有值的大多數情況,我的函式的結果會略少於實數乘十的結果

x:2.300000
23.000000
22.999998

x:2.600000
26.000000
25.999998

x:2.800000
28.000000
27.999998

x:3.100000
31.000000
30.999998

x:23.400000
234.000000
233.999985

也有發現在小數位數較多的情形下,我的函數可能會較貼近實數乘十的結果(應當只有少數的 x 會成立)

x:3.14159265
31.415928
31.415926

x:2.589847
25.898472
25.898470