# 2018q3 Homework (quiz2) ###### tags: `bauuuu1021`,`BroLeaf` contributed by <`BroLeaf`,`bauuuu1021`> [2018q1 第 2 週測驗題](https://hackmd.io/s/SJO5LN9_M) --- ### 測驗 `一` ![](https://i.imgur.com/Mp0cHII.jpg) 請完成下方程式碼，依循 IEEE 754 單精度規範，輸出 $2^x$ 的浮點數表達法，而且考慮兩種狀況： * 當 $x$ 過小的時候，回傳 $0.0$ * 當 $x$ 過大的時候，回傳 $+\infty$ 注意：這裡假設 `u2f` 函式返回的浮點數值與其無號數輸入有著相同的位數，也就是至少 32-bit ```Clike #include <math.h> static inline float u2f(unsigned int x) { return *(float *) &x; } float exp2_fp(int x) { unsigned int exp /* exponent */, frac /* fraction */; /* too small */ if (x < 2 - pow(2, Y0) - 23) { exp = 0; frac = 0; /* denormalize */ } else if (x < Y1 - pow(2, Y2)) { exp = 0; frac = 1 << (unsigned) (x - (2 - pow(2, Y3) - Y4)); /* normalized */ } else if (x < pow(2, Y5)) { exp = pow(2, Y6) - 1 + x; frac = 0; /* too large */ } else { exp = Y7; frac = 0; } /* pack exp and frac into 32 bits */ return u2f((unsigned) exp << 23 | frac); } ``` 求 Y0 ～ Y7 使上面程式碼可以正常運作 #### 初步了解 搭配 CS:APP 3/e 80頁 `圖 2-35`來觀看，以單精度浮點數 32-bit 來看 |情況|signed bit|exponent|mantissa| |:-:|:-:|:-:|:-:| |無限大|X|11111111|0000....00| |NaN|X|11111111|XXXX....XX | |denormalized|X|00000000|XXXX....XX| |最小(負的)|1|00000000|0000....01| |$\wr$|1|00000000|1111....11| |-0.0|1|00000000|0000....00| |+0.0|0|00000000|0000....00| |$\wr$|0|00000000|0000....01| |最大(正的)|0|00000000|1111....11| |normalized|X|XXXXXXXX $\neq$ 0 , 255|XXXX....XX| |最小(負的)|1|11111110|1111....11| |最大(正的)|0|11111110|1111....11| 有了上面表格的基本認識，接下來就可以分析程式碼了 ```C /* too small */ if (x < 2 - pow(2, Y0) - 23) { exp = 0; frac = 0; ``` * too small $2^x$ 小到連 float 都不能表示出來，也就是比 float 最小的值還要小 $2^{-126} \times 2^{-23} = 2^{-149}$ 接著就可以得到 $2 - pow(2, Y0) - 23 = -149$ 移項一下 $pow(2,Y0) = 126$ 得到 $Y0 = 7$ ```C /* denormalize */ } else if (x < Y1 - pow(2, Y2)) { exp = 0; frac = 1 << (unsigned) (x - (2 - pow(2, Y3) - Y4)); ``` * denormalized 這裡是處理 non-normalized 的情況，exponent 的部份都是零，數值界於 $2^{-149}$ ～ $2^{-126}$ 經過上一個的 if 條件可以知道 $x > -149$ 所以 $Y1 - pow(2, Y2) = -126$ $pow(2, Y2) = 128$ $Y1 = 2，Y2 = 7$ * 接著來看 `frac = 1 << (unsigned) (x - (2 - pow(2, Y3) - Y4));` frac 就是 float 的 mantissa ，這裡可以直接帶入最小的 denormalize 值來判斷參數 Y3、Y4 x = -149, frac = 1 => (unsigned) (x - (2 - pow(2, Y3) - Y4)) = 0 $Y3 = 7,Y4 = 23$ ```C /* normalized */ } else if (x < pow(2, Y5)) { exp = pow(2, Y6) - 1 + x; frac = 0; ``` * normalized 這一段要看的是 normalized 的最大限制 exponent 的值是 $-126 ～ 127$ 簡單就能看出 $pow(2, Y5) = 128$ $Y5 = 7$ 在這裡要把扣過的偏移值加回來，偏移值可以從 exponent的範圍知道 也可以從 IEEE754 對 單精度浮點數的定義： $2^{k - 1}-1 = 127$ 所以 $pow(2, Y6) = 128$ $Y6 = 7$ ```C /* too large */ } else { exp = Y7; frac = 0; } ``` * too large 根據表格，無限大 exp 部份是 11111111 也就是 0xff $Y7 = 0 \times ff$ Reference: * [Exploration of the IEEE-754 Floating Point Standard](http://blog.ruofeidu.com/exploration-ieee-754-floating-point-standard/) [90] :::info 延伸題: 給定一個單精度的浮點數值，輸出較大且最接近的 $2^x$ 值，需要充分考慮到邊界 ::: >[color=blue]BroLeaf --- ### 測驗 `二` ```Clike typedef unsigned int float_bits; float_bits float_x0_5(float_bits f) { unsigned sig = f >> 31; unsigned rest = f & 0x7FFFFFFF; unsigned exp = f >> 23 & 0xFF; unsigned frac = f & 0x7FFFFF; /* NaN or INF */ if (exp == A0) return f; /* round to even. Last 2 bits of frac are considered: * 00 => 0 just >> 1 * 01 => 0 (round to even) just >> 1 * 10 => 1 just >> 1 * 11 => 1 + 1 (round to even) just >> 1 and plus 1 */ int addition = (frac & 0x3) == 0x3; /* Denormalized */ if (exp == 0) { frac >>= A1; frac += addition; /* Normalized to denormalized */ } else if (exp == 1) { rest >>= A2; rest += addition; exp = rest >> A3 & A4; frac = rest & 0x7FFFFF; /* Normalized */ } else { exp -= A5; } return sig << A6 | exp << 23 | frac; } ``` * 根據 IEEE754 對 float 的規範 * sign 為第 31 位 * exp 為第 23~30 位 * frac 為 0~22 位 * 將數值改寫為 $(-1)^{sign}*M*2^{exp}$，normalize 時 M 為 1+0.(frac)，denormalize 時 M 為 0.(frac) * A0 = ? ``` /* NaN or INF */ if (exp == A0) return f; ``` 根據 IEEE754 定義，當 exp 為 0xFF 時為 NaN 或 INF；`A0 = 0xFF` * A1 = ? ``` /* Denormalized */ if (exp == 0) { frac >>= A1; frac += addition; } ``` f 為 Denormalized 時 exp 為 0，與數值大小有關的剩下 frac 。 因此將 frac 往右一位即可將數值 $*0.5$ ，`A1 = 1` * A2 = ? A3 = ? A4 = ? ``` /* Normalized to denormalized */ else if (exp == 1) { rest >>= A2; rest += addition; exp = rest >> A3 & A4; frac = rest & 0x7FFFFF; } ``` 因為 exp 只有 1，而 exp 直接與 frac 相連，因此 `rest >>= A2;` 可以直接視為 denormalized 的情況做運算。`A2=1` <br> 在 exp 為 1 的狀況下 *0.5 後一定是 denormalized ，也就是 exp = 0 。因此先將 rest 右移到使 exp 在最低位，再用一個 mask 讓 exp 只有 8 位。`A3=23 A4=0xFF` * A5 = ? ``` /* Normalized */ else { exp -= A5; } ``` f 為 Normalized 時透過 exp-1 即可將數值 $*0.5$，`A5 = 1` * A6 = ? ``` return sig << A6 | exp << 23 | frac; ``` 將數值的每個部分透過 `|` 連結起來， sig 在最高位元，`A6=31` Reference: * [Floating Point Multiplication](https://www.doc.ic.ac.uk/~eedwards/compsys/float/) [95] >[color=blue]bauuuu1021 --- ### 測驗 `三` 考慮到某些實數的二進位表示形式如同 $0.yyyyy...$ 這樣的無限循環小數，其中 $y$ 是個 $k$ 位的二進位序列，例如 $\frac{1}{3}$ 的二進位表示為 $0.01010101...$ (y = `01`)，而 $\frac{1}{5}$ 的二進位表示為 $0.001100110011...$ (y = `0011`)，考慮到以下 y 值，求出對應的十進位分數值。 * y = `010011` => $\frac{19}{X1}$ * y = `101` => $\frac{5}{X2}$ * y = `0110` => $\frac{2}{X3}$ X1 = ? X2 = ? X3 = ? :::success Reference: * [Binary Fractions](https://www.electronics-tutorials.ws/binary/binary-fractions.html) [83] ::: * 令循環小數的一組循環有 k 位，則 $0.yyyy...$ 可以想成 0.y, 0.y * $2^{-k}$, 0.y * $2^{-2k}$,.....無窮等比數列之和。其中首項為 0.y ，公比為 $2^{-k}$。 * 無窮等比和的公式為 $\frac{首項}{1-公比}$，帶入後答案為 $\frac{0.y}{1-2^{-k}}$。 * 第一小題 y = 010011，$0.y$ 為 $\frac{19}{64}$，k 為 6 ，帶入公式得 $\frac{19}{63}$ 。因此答案選`(c)63`。 * 第二小題 y = 101，$0.y$ 為 $\frac{5}{8}$，k 為 3 ，帶入公式得 $\frac{5}{7}$ 。因此答案選`(f)7`。 * 第三小題 y = 0110，$0.y$ 為 $\frac{3}{8}$，k 為 4 ，帶入公式得 $\frac{2}{5}$ 。因此答案選`(g)5`。 :::warning 接著你可以繼續思考：「如何一般化 (generalize) 呢？」 給定的分數 (即 N/M 形式，當 N 和 M 都是正整數)，如何轉換成二進位，而且在表達 bit 數量限制的狀況，轉換的誤差是多少？(對比看 CS:APP 提及的愛國者導彈的誤差議題) :notes: jserv ::: * 一般化 * 先將分數寫為整數與小於 1 的分數 : int+frac * int 部份可以直接轉換成二進位 * frac 部份先乘以 2 ，判斷是否 >1 * \>1 : frac=(frac-1)*2，寫下 1 * <1 : frac=frac*2，寫下 0 * 重複此步驟直到完成或找出規律<br> * eg : 求 $\frac{12}{7}$ 之二進位表示 * $\frac{12}{7}=int+frac=1+\frac{5}{7}$ * 先將 frac * 2 再開始運算 * | Current | >1? | 小數點 | Next | | :-: | :-: | :-: | :-:| | $\frac{10}{7}$ | T | 1 | $(\frac{10}{7}-1)*2$ | | $\frac{6}{7}$ | F | 0 | $\frac{6}{7}*2$ | | $\frac{12}{7}$ | T | 1 | $(\frac{12}{7}-1)*2$ | | $\frac{10}{7}$ | T | 1 | $(\frac{10}{7}-1)*2$ | | $\frac{6}{7}$ | F | 0 | $\frac{6}{7}*2$ | | $\frac{12}{7}$ | T | 1 | $(\frac{12}{7}-1)*2$ | * binary = 1.[101][101][101]... * bit 數量限制 * 用上面的例子做延伸，觀察可發現 $\frac{12}{7}$ 是每 3 bits 為一循環，以下討論不同小數點位數下誤差大小 * $誤差=\frac{轉分數-實際值}{實際值}=\frac{轉分數-\frac{12}{7}}{\frac{12}{7}}$ | 限制位數 | 轉分數 | 誤差 | | :-: | :-: | :-: | | 3 | $1+\frac{5}{8}$ | 5.208% | | 6 | $1+\frac{45}{64}$ | 0.651% | | 9 | $1+\frac{365}{512}$ | 0.081% | | 12 | $1+\frac{2925}{4096}$ | 0.071% | | ... | ... | ... | | 24 | $1+\frac{11983725}{117440512}$ | 0.00000248% | * 24 bits 接近 float 可儲存的位數範圍，可發現對一般運算來說誤差已經不大。但如果是要應用在距離長的運算如火箭等，隨著距離增加誤差也會拉大 :::warning 從上表不難發現，這種數值轉換的誤差值較高，實務上如何縮減呢？ :notes: jserv ::: --- ### 測驗 `四` 在 [你所不知道的C語言: 遞迴呼叫篇](https://hackmd.io/s/rJ8BOjGGl) 提到以下程式碼: ```Clike= #include <stdio.h> int p(int i, int N) { return (i < N && printf("%d\n", i) && !p(i + 1, N)) || printf("%d\n", i); } int main() { return p(1, 10) && printf("\n"); } ``` 預期會得到以下輸出: ``` 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> ``` * 開始前要先講解很重要的觀念，在 C 語言裡面，邏輯運算如下： `(A && B && C) || D` * 若 A 為 false 則會直接跳過 BC 去看 D 的結果，同理 A true 且 B 為 false 也會跳過 C ，若 ABC 為 true 則不會去看 D 的結果。 * 先觀察第一個程式，直接帶入 1, 10 trace 一遍就可以得到結果。 |次數|1|2|3|~|9|10|9|~|2|1| |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| |i|1|2|3|~|9|10|9|~|2|1 |N|10|10|10|10|10|10|10|10|10|10 |print|1|2|3|~|9|10|9|~|2|1 * 要注意的是第 10 次在終止條件 i < N 這邊就是 False 了，所以根據上面提過的運算，會直接跑到第 4 行的 printf 印出 10，且回傳 true * 但是第 3 行呼叫 recusion call 有一個 not 所以實際上 `(i < N && printf("%d\n", i) && !p(i + 1, N))` 的結果一直都是 False ，所以遞迴回傳到前面時會跑到第 4 行的 printf ，再印一次當前的 i * 總結來說，**print 出來的前面 1 ～ 9 是呼叫第 3 行印的，後面的 10 ～ 1 是呼叫第 4 行印的**。 * 因為 printf 回傳印出的 character 數，其結果一直都是 true ，最後回傳 true 到 main 裡面，再執行最後一個 printf ，所以結果會再多一行。 注意 `10` 只會出現一次。請填補下方程式碼，使得輸出為 `1 -> 2 -> 3 -> 4 -> 5 ->`，並且包含換行符號 (`\n`) ```Clike #include <stdio.h> int p(int i, int N) { return (i < N && printf("%d -> ", i) && Q1(i + Q2, N + Q3)); } int main() { return p(1, 10) && printf("\n"); } ``` 提示: Q1 是函式名稱，可能包含 `~` (bitwise NOT) 操作，Q2 和 Q3 是有號整數 * 因為只要輸出一半的結果，等同於只呼叫一半次數的遞迴，用等差級數的概念去判斷，相較於上面的程式是相差 1 ，這裡呼叫的參數要相差 2 ，根據輸出結果是 12345 所以一邊一定會是 i + 1，另一邊則是 N - 1 得出，Q2 = 1， Q3 = -1。 * 最後要能執行到 main 裡面的 printf ，也就代表著 `return p(1, 10)` 一定要是 true |次數|1|2|3|4|5|6 |:-:|:-:|:-:|:-:|:-:|:-:|:-: |i|1|2|3|4|5|6 |N|10|9|8|7|6|5| |print|1|2|3|4|5| * 第 6 次遞迴呼叫 Q1(5 + 1, 6 - 1)，很明顯結果會回傳 false ，所以我們在這邊使用 ~ (bitwise NOT) 強制把結果轉成 true ，所以最後回傳 main true ，就會執行後面的 printf 了。Q1 = ~p :::info 為了得到使回傳值回傳相反的結果而使用 ~ (bitwise NOT)，我認為並不恰當。 根據本題回傳值有可能是 int ，例如：000111 (true)，在使用 ~ 後，會變成111000，結果還是 true，只有在回傳 false 也就是 0 的時候用 ~ 才會得到相反的結果，有可能造成邏輯上的 bug 。 直接改用 ! Logical negation (NOT)，可以得到相同 output ，也比較恰當。 ::: >[color=blue]BroLeaf > ### 參考資料 * [2018q1 Homework2 (作業區)](https://hackmd.io/s/BykAwRuKz) * [bauuuu1021](https://hackmd.io/s/Bkmr6V6tM) 共筆內容 * [raygoah](https://hackmd.io/s/HyCc94IKM#Week-2) 共筆內容 * [BroLeaf](https://hackmd.io/s/B1QbUVz9G) 共筆內容 * [Bitwise operators (NOT)](https://en.wikipedia.org/wiki/Bitwise_operation#NOT)