2018q3 Homework (quiz2)

tags: `bauuuu1021`,`BroLeaf`

contributed by <BroLeaf,bauuuu1021>
2018q1 第 2 週測驗題

測驗 `一`

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

請完成下方程式碼，依循 IEEE 754 單精度規範，輸出

2^{x}

的浮點數表達法，而且考慮兩種狀況：

當
$x$ 過小的時候，回傳
$0.0$
當
$x$ 過大的時候，回傳
$+ \infty$

注意：這裡假設 u2f 函式返回的浮點數值與其無號數輸入有著相同的位數，也就是至少 32-bit

#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
$≀$	1	00000000	1111…11
-0.0	1	00000000	0000…00
+0.0	0	00000000	0000…00
$≀$	0	00000000	0000…01
最大(正的)	0	00000000	1111…11
normalized	X	XXXXXXXX $\neq$ 0 , 255	XXXX…XX
最小(負的)	1	11111110	1111…11
最大(正的)	0	11111110	1111…11
有了上面表格的基本認識，接下來就可以分析程式碼了

/* 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 - p o w (2, Y 0) - 23 = - 149$
移項一下
$p o w (2, Y 0) = 126$
得到
$Y 0 = 7$

/* 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$
所以
$Y 1 - p o w (2, Y 2) = - 126$

$p o w (2, Y 2) = 128$

$Y 1 = 2 ， Y 2 = 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

$Y 3 = 7, Y 4 = 23$

/* normalized */
    } else if (x < pow(2, Y5)) {
        exp = pow(2, Y6) - 1 + x;
        frac = 0;

normalized
這一段要看的是 normalized 的最大限制
exponent 的值是
$- 126 ～ 127$
簡單就能看出
$p o w (2, Y 5) = 128$

$Y 5 = 7$
在這裡要把扣過的偏移值加回來，偏移值可以從 exponent的範圍知道
也可以從 IEEE754 對單精度浮點數的定義：
$2^{k - 1} - 1 = 127$
所以
$p o w (2, Y 6) = 128$

$Y 6 = 7$

/* too large */
    } else {
        exp = Y7;
        frac = 0;
    }

too large
根據表格，無限大 exp 部份是 11111111 也就是 0xff

$Y 7 = 0 \times f f$

Reference:

Exploration of the IEEE-754 Floating Point Standard
[90]

延伸題: 給定一個單精度的浮點數值，輸出較大且最接近的

2^{x}

值，需要充分考慮到邊界

BroLeaf

測驗 `二`

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)^{s i g n} * M * 2^{e x p}$ ，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

在 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
[95]

bauuuu1021

測驗 `三`

考慮到某些實數的二進位表示形式如同

0. y y y y y . . .

這樣的無限循環小數，其中

y

是個

k

位的二進位序列，例如

\frac{1}{3}

的二進位表示為

0.01010101 . . .

(y = 01)，而

\frac{1}{5}

的二進位表示為

0.001100110011 . . .

(y = 0011)，考慮到以下 y 值，求出對應的十進位分數值。

y = 010011 =>
$\frac{19}{X 1}$
y = 101 =>
$\frac{5}{X 2}$
y = 0110 =>
$\frac{2}{X 3}$

X1 = ?
X2 = ?
X3 = ?

Reference:

Binary Fractions
[83]

令循環小數的一組循環有 k 位，則
$0. y y y y . . .$ 可以想成 0.y, 0.y *
$2^{- k}$ , 0.y *
$2^{- 2 k}$ ,…無窮等比數列之和。其中首項為 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。

接著你可以繼續思考：「如何一般化 (generalize) 呢？」
給定的分數 (即 N/M 形式，當 N 和 M 都是正整數)，如何轉換成二進位，而且在表達 bit 數量限制的狀況，轉換的誤差是多少？(對比看 CS:APP 提及的愛國者導彈的誤差議題)

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

一般化
- 先將分數寫為整數與小於 1 的分數 : int+frac
- int 部份可以直接轉換成二進位
- frac 部份先乘以 2 ，判斷是否 >1
  - >1 : frac=(frac-1)*2，寫下 1
  - <1 : frac=frac*2，寫下 0
  - 重複此步驟直到完成或找出規律
- eg : 求
  $\frac{12}{7}$ 之二進位表示
  - $\frac{12}{7} = i n t + f r a c = 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 可儲存的位數範圍，可發現對一般運算來說誤差已經不大。但如果是要應用在距離長的運算如火箭等，隨著距離增加誤差也會拉大

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$

限制位數	轉分數	誤差
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%

從上表不難發現，這種數值轉換的誤差值較高，實務上如何縮減呢？

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

測驗 `四`

在你所不知道的C語言: 遞迴呼叫篇提到以下程式碼:






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

#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

為了得到使回傳值回傳相反的結果而使用 ~ (bitwise NOT)，我認為並不恰當。
根據本題回傳值有可能是 int ，例如：000111 (true)，在使用 ~ 後，會變成111000，結果還是 true，只有在回傳 false 也就是 0 的時候用 ~ 才會得到相反的結果，有可能造成邏輯上的 bug 。
直接改用 ! Logical negation (NOT)，可以得到相同 output ，也比較恰當。

BroLeaf

2018q3 Homework (quiz2)

tags: bauuuu1021,BroLeaf

測驗 一

初步了解

測驗 二

測驗 三

測驗 四

參考資料

tags: `bauuuu1021`,`BroLeaf`

測驗 `一`

測驗 `二`

測驗 `三`

測驗 `四`