＃ 2025q1 Homework5 (assessment

# 2025q1 Homework5 (assessment) contributed by < `qianzsh` > ## 閱讀〈[因為自動飲料機而延畢的那一年](https://www.opasschang.com/docs/the-story-of-auto-beverage-machine-1)〉的啟發 - 人不付出犧牲，就得不到任何回報。如果要得到什麼，就必須付出同等的代價，這就是鍊金術的基本原則，等價交換。當時我們深信著，這就是這世界的真理。------《鋼之鍊金術師》回顧這堂課程中所學，我發現跟文章中的故事有所相似，都是注重細節以及在解決真實世界發生的問題。目前為止，我讀完 linux 書的第一章，以及完成部份 lab0-c。 :::danger 為何你宣稱閱讀後，僅列出隻字片語呢？你沒有其他收穫嗎？ ::: ## 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) = log_{2}(2) + log_{2}(2) + log_{2}(2) + log_{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}) = \dfrac{1}{2}\log_{2}(b^2) = \dfrac{1}{2}\log_{2}(c)$ ，若 $c >2$ 則可以用上述的方法取得整數與小數部份，否則 $c = (c^2)^\frac{1}{2} = (d)^\frac{1}{2}$ ，以此往復循環直到遞迴深度達到停止條件。 :::danger 不用列出參考題解，專注在程式碼本體和你的認知上。 ::: 程式碼先是透過判斷式 num >= base 判斷是否還有整數部份，若判斷為是則結果加一並對 num/base 繼續遞迴計算，累加出整數部分，反之則透過 for 迴圈以及遞迴來取得 log 後的小數部份，而變數 acc 決定遞迴深度。 ### 用 Tail recursion 方式改寫 ```c 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 語言：遞迴呼叫篇](https://hackmd.io/@sysprog/c-recursion)」後，用 Tail recursion 這一種特殊形式的遞迴對原程式進行改寫，需要注意的是，GCC／Clang 要編譯器開啟最佳化才會做 tail recursion。 :::danger 注意精準的用語，參見[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) ::: ### 用定點數改寫用 Q16.16 改寫，在過程中我注意到從浮點數變換到定點數是不能直接做位元位移; 在 C99 規格書 6.5.7 Bitwise shift operators 第 2 節指出 > Each of the operands shall have integer type. 限制只有整數型別能進行 bitwise 操作; :::danger 為何不能對浮點數進行 bitwise 操作？列出相關 C 語言規格書的描述。 ::: 考量 IEEE 754 浮點數的儲存格式包含符號位元、指數與尾數，進行位元操作的方式與整數不同，且 c語言並沒有對浮點數的位元操作進行定義，因此以下實做使用浮點數的乘除法進行運算。 ```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); } ``` :::danger 應探討誤差和其修正。 ::: ### 探討誤差來源 **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 等能表示更多小數點後位數的格式 ### [牛頓法](https://en.wikipedia.org/wiki/Newton%27s_method)