# 2024q1 Homework5 (assessment)
contributed by < `marsh-fish` >

## 閱讀〈[因為自動飲料機而延畢的那一年](https://blog.opasschang.com/the-story-of-auto-beverage-machine-1)〉的啟發

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

## 想投入的專案

### 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