# 2018q3 Homework (quiz2)
###### tags: `bauuuu1021`,`BroLeaf`
contributed by <`BroLeaf`,`bauuuu1021`>
[2018q1 第 2 週測驗題](https://hackmd.io/s/SJO5LN9_M)
---
### 測驗 `一`
請完成下方程式碼，依循 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)
Sign in with Wallet
Connect another wallet