2025q1 Homework5 (assessment)

contributed by < qianzsh >

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

• 人不付出犧牲，就得不到任何回報。如果要得到什麼，就必須付出同等的代價，這就是鍊金術的基本原則，等價交換。當時我們深信著，這就是這世界的真理。–––《鋼之鍊金術師》

回顧這堂課程中所學，我發現跟文章中的故事有所相似，都是注重細節以及在解決真實世界發生的問題。目前為止，我讀完 linux 書的第一章，以及完成部份 lab0-c。

為何你宣稱閱讀後，僅列出隻字片語呢？你沒有其他收穫嗎？

2025q1 第 6 週測驗 2

數學理解

程式碼將

${\log }_2(a)$ 的

$a$ 拆解成多個

$2$ 的相乘，再乘以一個小於

$2$ 的數

$b$ ，可以寫成：

$$a=2^1\times 2^1\times 2^1\times b$$
之後改寫

${\log }_2(a)$ 裡的

$a$ ，再利用

$\log$ 特性，寫成：

$${\log }_2(a)={\log }_2(2^1\times 2^1\times 2^1\times b)=lo{g}_2(2)+lo{g}_2(2)+lo{g}_2(2)+lo{g}_2(b)$$

我們可以透過以上的等式操作得到

$a$ 取

${\log }_2$ 後的整數部份加上

${\log }_2(b)$，

${\log }_2(b)$ 是

$a$ 取

${\log }_2$ 後的小數部份，這裡可以把

$b$ 替換成

$b=(b^2{)}^{\frac{1}{2}}=(c{)}^{\frac{1}{2}}$ ，所以

${\log }_2(b)={\log }_2((b^2{)}^{\frac{1}{2}})={\displaystyle \frac{1}{2}}{\log }_2(b^2)={\displaystyle \frac{1}{2}}{\log }_2(c)$ ，若

$c>2$ 則可以用上述的方法取得整數與小數部份，否則

$c=(c^2{)}^{\frac{1}{2}}=(d{)}^{\frac{1}{2}}$ ，以此往復循環直到遞迴深度達到停止條件。

不用列出參考題解，專注在程式碼本體和你的認知上。

程式碼先是透過判斷式 num >= base 判斷是否還有整數部份，若判斷為是則結果加一並對 num/base 繼續遞迴計算，累加出整數部分，反之則透過 for 迴圈以及遞迴來取得 log 後的小數部份，而變數 acc 決定遞迴深度。

用 Tail recursion 方式改寫

double logarithm(double base, double num, double result, double weight,int acc)
{
    /* Stop recursion once we have reached the desired depth */
    if (acc <= 0)
        return result;

    /* If num is large enough to "remove" one whole unit of log at once */
    if (num >= base){
        result += weight;
        return logarithm(base, num / base, result, weight, acc - 1);
    }
    /* Otherwise, multiply 'num' by itself 'base' times
     * (which is effectively num^base).
     */
    double tmp = 1.0;
    for (int i = 0; i < (int) base; i++)
        tmp *= num;
    weight /= base;
    return logarithm(base, tmp, result, weight, acc - 1);
}  

閱讀「你所不知道的 C 語言：遞迴呼叫篇」後，用 Tail recursion 這一種特殊形式的遞迴對原程式進行改寫，需要注意的是，GCC／Clang 要編譯器開啟最佳化才會做 tail recursion。

注意精準的用語，參見資訊科技詞彙翻譯

用定點數改寫

用 Q16.16 改寫，在過程中我注意到從浮點數變換到定點數是不能直接做位元位移;
在 C99 規格書 6.5.7 Bitwise shift operators 第 2 節指出

Each of the operands shall have integer type.

限制只有整數型別能進行 bitwise 操作;

為何不能對浮點數進行 bitwise 操作？列出相關 C 語言規格書的描述。

考量 IEEE 754 浮點數的儲存格式包含符號位元、指數與尾數，進行位元操作的方式與整數不同，且 c語言並沒有對浮點數的位元操作進行定義，因此以下實做使用浮點數的乘除法進行運算。

#include <stdio.h>
#include <stdint.h>

#define FIXED_SHIFT 16
#define TO_FIXED(x) ((int32_t)((x) * (1 << FIXED_SHIFT)))
#define TO_DOUBLE(x) ((double)(x) / (1 << FIXED_SHIFT))

double logarithm(double base, double num, double result, double weight,int acc)
{
    /* Stop recursion once we have reached the desired depth */
    if (acc <= 0)
        return result;

    /* If num is large enough to "remove" one whole unit of log at once */
    int32_t num_fixed = TO_FIXED(num);
    int32_t base_fixed = TO_FIXED(base);

    if (num_fixed >= base_fixed){
        int32_t result_fixed = TO_FIXED(result);
        int32_t weight_fixed = TO_FIXED(weight);
        result_fixed += weight_fixed;

        double result_new = TO_DOUBLE(result_fixed);
        double weight_new = TO_DOUBLE(weight_fixed);
        
        int64_t tmp_fixed = ((int64_t)num_fixed << FIXED_SHIFT) / base_fixed;
        double tmp = TO_DOUBLE(tmp_fixed);
        
        return logarithm(base, tmp, result_new, weight_new, acc - 1);
    }
    /* Otherwise, multiply 'num' by itself 'base' times
     * (which is effectively num^base).
     */
    int32_t tmp_fixed = TO_FIXED(1.0);
    for (int i = 0; i < (int) base; i++){
        tmp_fixed = ((int64_t)tmp_fixed *(int64_t)num_fixed) / (1 << FIXED_SHIFT);
        printf("%d\n", (int) base);
        printf("%d\n", num_fixed);
        printf("%d\n", tmp_fixed);}
    double tmp = TO_DOUBLE(tmp_fixed);
    
    int32_t weight_fixed = TO_FIXED(weight);
    int64_t weight_scaled = ((int64_t)weight_fixed << FIXED_SHIFT) / base_fixed;
    double weight_new = TO_DOUBLE(weight_scaled);
    
    return logarithm(base, tmp, result, weight_new, acc - 1);
} 

應探討誤差和其修正。

探討誤差來源

Q16.16 格式，保留 16 位小數部分，單層的精度為

$2^{-16}=0.0000152587890625$ 。
程式碼在迭代的過程， weight 不斷除 2 ，最後在 weight = 2^{-16} 之後的運算 weight 都為 0 ，導致 result 沒辦法加到後續的值。

int64_t weight_scaled = ((int64_t)weight_fixed << FIXED_SHIFT) / base_fixed;

上述程式碼，當 weight = 2^{-16} ，也就是 weight_fixed = 1 時， weight_fixed 再除 2 ， weight_scaled = 0 。
而且，後續 weight 的累積也不會超過 Q16.16 的最小刻度，

$2^{-16}$ ，所以這裡不考慮用另外的變數紀錄誤差
那目前計算出來的值

${\log }_2(10)\approx 3.321914672852$ 與真實的值

${\log }_2(10)\approx 3.3219280948873626$ 相差在 Q16.16 的最小刻度內，所以若要更為精準的表示，要用 Q8.24 等能表示更多小數點後位數的格式

牛頓法