# 2018q1 Homework2
contributed by <`e94046165`>
重做前三周測驗題

## 第 1 週測驗題_測驗`1`
題目如下：

- [ ]考慮以下程式碼:

#include <stdlib.h>
int isMultN(unsigned int n) {
    int odd_c = 0, even_c = 0; /* variables to count odd and even SET bits */
    
    if (n == 0)    // return true if difference is 0.
        return 1;
    if (n == 1)    // return false if the difference is not 0.
        return 0;
    
    while (n) {
        if (n & 1)   // odd bit is SET, increment odd_C
            odd_c++;
        n >>= 1; 
    
        if (n & 1)   // even bit is SET, increment even_c
            even_c++;
        n = n >> 1;
    }
    
    /* Recursive call till you get 0/1 */
    return(isMultN(abs(odd_c - even_c)));
}

其作用為檢查輸入整數是否為 N 的倍數，那麼 N 為多少？

### 想法 & 思考
最一開始看到這段程式碼時，腦海中第一個浮現的念頭是 N = 11，會有這樣的想法是因為看到程式碼中比對 __奇偶數位__ ，而在十進位中，判斷某數是否為11的倍數方法如下：
將奇偶數位數字分別相加後，兩者相減mod11 == 0 則為11 的倍數，下面是舉例。

例:
1221 是否為 11 的倍數？
奇數位總和 = 1+2 = 3
偶數位總和 = 1+2 = 3
(3-3) % 11 = 0 ---> 1221 為 11的倍數

顯然我忽略了要以二進位的角度去思考，所以這題在第一次作答的時候我選錯了。這題的答案應該是 N = 3 ，但答對此題同學在上台講解的時候說了：

因為 3 以二進位表示是 011 所以所有 3 的倍數必定符合：
奇數位元為 1 的個數與偶數位元為 1 的個數相等，這個條件。

我認為這樣的講法是不夠嚴謹的，接著我將試著以數學歸納法作證明。
### 數學歸納法
這邊先簡單的解釋數學歸納法：
__定義__ from [wiki](https://zh.wikipedia.org/zh-tw/%E6%95%B0%E5%AD%A6%E5%BD%92%E7%BA%B3%E6%B3%95)

最簡單和常見的數學歸納法是證明當_n_等於任意一個自然數時某命題成立。證明分下面兩步：
1.  證明當 n  = 1時命題成立。
2.  證明如果在 n  =  m 時命題成立，那麼可以推導出在 n  =  m +1
    時命題也成立。（ m 代表任意自然數）

而更容易理解的解釋方法是

假設有一列骨牌，我們只要證明
1.第一張骨牌會倒
2.假設在已知第 m 張骨牌會倒的情況下，證明第 m + 1 張骨牌也會倒
  (m 為 ！= 1 的任意自然數)
則我們可以說，整列骨牌都會倒。（即證明成立）

__證明__
試證：所有 3 的倍數，以二進位表示時奇偶位`1`數量相等
1. 第一張骨牌：
3 = 011 奇偶數位皆有一個 1，3 為 3 的倍數
假設成立
2. 假設 m 為一個非 3 的 3 的倍數，且奇偶數位的 `1` 個數相等，分別考慮以下兩種情況：(以下進位皆以二進位為主)
* m + 3 無進位：
m = ...00 奇偶數位的 `1` 數量相等
m + 3 = ...11 奇偶數位的 `1` 數量仍相等
---->符合命題：m + 3 是三的倍數且奇偶位 `1` 數量相等
* m + 3 有一次進位：
m = ...0001
m + 3 = ...0100 奇偶數`1`個數與原來相同，命題成立
* m + 3 有兩次進位：
m = ...0101
m + 3 = ...1000 奇偶數`1`個數改變，命題不成立...?

由上列證明可得知，
命題：所有 3 的倍數，以二進位表示時奇偶位`1`數量相等
是有缺陷的，但這個缺陷來在於我沒有看懂程式碼，還是程式碼寫錯了呢？

### 測試&重讀程式碼

root@acnes-X550JX:~/test#./test
165
165 是三的倍數
168
168 是三的倍數
1
1 不是三的倍數

若是程式碼錯了，那麼應該沒辦法判斷 168 是三的倍數，理由如下：
165 = 10100101
168 = 10101000 奇偶數 `1`個數不相等
但由上面的測試結果可發現，這個 function 可以正確的判斷

在重新檢視程式碼後，才發現是我忽略了最後那行遞迴呼叫：

 /* Recursive call till you get 0/1 */
    return(isMultN(abs(odd_c - even_c)));

當奇偶數位 `1` 不相等時，會遞迴呼叫，直至得到 0 或 1 為止。也就是說，如果奇偶數位的 `1` 個數差是三的倍數，依然能判斷出它是三的倍數。

因此，原假設應修正成：
所有奇偶數位 `1` 個數相等的數，皆為三的倍數
但三的倍數，可能為奇偶數位 `1` 個數差為 0 或 3n 的數

現在又遇到同樣的問題，要怎麼證明這個假設在所有情況下都成立呢？

__證明__
試證：三的倍數，皆為奇偶數位 `1` 個數差為 0 或 3n 的數
基數位的 `1` 代表 2^2n^ 也就是 ：1, 4, 16, 64...這些數共同的特色是 3p~i~+1
偶數位的 `1` 代表 2^2n+1^ 也就是 ：2, 8, 32, 128...這些數共同的特色是 3q~i~-1

因此可得到，
奇偶數位 `1` 的個數相等時：代表 3(P+Q) 為三的倍數
奇偶數位 `1` 的個數相差3的倍數：代表 3P+3 or 3Q-3皆為三的倍數
p.s. P = Σp~i~ , Q = Σq~i~
得證假設成立。

### 延伸問題
- 為什麼上述程式碼可運作呢？上列已解釋並證明。
- 將 N 改為其他質數再改寫為對應的程式碼，一樣使用遞迴

試著將 N 改為 5

#include <stdio.h>

int isMultN(unsigned int n)
{
    if (n == 5)    // return true if only 5 is left
        return 1;
    if (n < 5 )    // return false if the number left is less than 5
        return 0;
	//for number which is larger than 5
    
    if(n&1)
	n = n - 5;
    else
	n >>= 1;
    
    /* Recursive call till you get 5 or less */
    return(isMultN(n));
}

__解釋程式碼__
因為 5 的倍數有此特性: 尾數非 0 即 5
因此重複
n 為偶數則 n = n / 2
n 為奇數則 n = n - 5
由最後 n == 5 or n < 5 可判斷 n 是否為 5 的倍數

由於上列解法實在太平庸了，連我自己都覺得跟發廢文沒兩樣，所以決定丟掉再寫些新的。

#include <stdlib.h>
#include <stdio.h>

int isMultN(unsigned int n)
{
    if ( (n == 5) || (n == 0) )    // return true if only 5 is left
        return 1;
    if ( (n >> 2) < (n & 3) )    // return false if the number left is less than 5
        return 0;
	//for number which is larger than 5
    
  	n = (n >> 2) - (n & 3);
    
    /* Recursive call till you get 5, 0 
        or a special terminate condition */
    return(isMultN(n));
}

這段 code 一樣用來判斷輸入 n 是否為 5 的倍數，但是因為這次一次處理兩個 bits 所以速度應該會較前一個快上一些。而且這個概念應該也可以拓展到其他的質數。
概念如下：

假設 n = (abcde)~2~
則 n = (abc00)~2~ + (000de)~2~
= ( (abc)~2~ << 2 ) + (000de)~2~
= ( (abc)~2~ * (5-1)~10~ ) + (000de)~2~
= ( (abc)~2~ * 5 - (abc - de)~2~

因為(abc)~2~ * 5 必定為 5 的倍數，所以只要判斷(abc - de)~2~是否為 5 的倍數就好，這部份可以交給遞迴呼叫來解決，直到得到結果為止。

現在試著將上面的概念拓展到 N = 7

假設 n = (abcde)~2~
= (ab000)~2~ + (00cde)~2~
= ( (ab)~2~ << 3 ) + (00cde)~2~
= = ( (ab)~2~ * 7 + (ab + cde)~2~

依照上列概念寫出的程式碼如下：

#include <stdlib.h>
#include <stdio.h>

int isMultN(unsigned int n)
{
    if(n <= 7){
        if ( (n == 7) || (n == 0) )  
            return 1;
        else    
            return 0;
	//for number which is larger than 7
	}
	else n = (n >> 3) + (n & 7);
  	
    
    /* Recursive call till you get 7 or less */
    return(isMultN(n));
}

~~真舒服XD~~
可以看到判斷式有些不一樣，不過應該挺好理解的。
遞迴呼叫至 n <= 7 ，若 n 等於 0 或 7，則為 7 的倍數，其餘則非。

說來慚愧，會有以上的概念並不是我突然靈光一閃，是在搜尋的過程中看到了一篇[國小科展](http://ccjh.tc.edu.tw/manasystem/Files/download1/9805121042411_48%E5%B1%86%E7%A7%91%E5%AD%B8--%E4%BD%B3%E4%BD%9C--%E6%9D%8E%E7%91%9E%E6%BA%90%E8%80%81%E5%B8%AB.pdf)...才讓我想起 11 倍數判斷的原理並加以推廣。

:::info
太好了，接著你可以繼續想，上面遞迴和 bit-wise 操作可對應到數位邏輯電路是怎麼組合，來練習吧！
:notes: jserv
:::

## 第 2 週測驗題_測驗`1`

題目如下：

請完成下方程式碼，依循 IEEE 754 單精度規範，輸出 2^x^的浮點數表達法，而且考慮兩種狀況：

- 當 x 過小的時候，回傳 0.0 0.0
- 當 x 過大的時候，回傳 +∞ +∞

注意：這裡假設 `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 填入相對應的數值，使得該函式依輸入的 x 輸出 2^x^ 的浮點數值。

### 想法 & 思考
這段 code 註解清楚的將整個程式依照輸入的 x 值，分成 4 個範圍（與浮點數表示法相呼應）：
* too small
單精度浮點數表示法，能表現的最小正值為
0 0...0 0.......1
也就是 signed bit 為零;
exponent bits 全為零;
fraction 為 2^-23^
對應到的 2^x^ ，x = 1 -(128 -1) - 23 = 2 - pow(2, Y0) - 23 ==> Y0 = 7
當 x < 這個值時，則使所有 bits 全為 0
* denormalize
這個範圍介於 too small 與 normalized 之間，也就是 exponent bits 全為零，但 fraction 部份不為零的情況。
因此，x 被限制在 x < Y1 - pow(2, Y2) = 2 - pow(2, 7)
在此範圍內 exp 設定成 0;
而 frac 則依照 x 大小被位移
frac = 1 << (unsigned) (x - (2 - pow(2, Y3) - Y4));
這裡可以依最小的 denormalize 值來判斷參數 Y3、Y4
最小值 x = -149 ==> frac = 1
==> -149 - (2 - pow(2, Y3) - Y4)) == 0
==> Y3 = 7, Y4 = 23
* normalized
單精度浮點數能表示的最大值為 (2−2^−23^) × 2^127^ < 2^128^ 因此 x 值必須小於 128 = pow(2, Y5), Y5 = 7
exp = pow(2, Y6) - 1 + x; 為 x 加上 Bias 127
==> Y6 = 7
* too large
最後則是輸入的 x 大於單精度能表示的範圍，在此情況下，
exp 被設定為 8 bits 全為 1 ，Y7 = 0xff

### 延伸問題
- 給定一個單精度的浮點數值，輸出較大且最接近的 2^x^ 值，需要充分考慮到邊界

延伸題是原本命題的反向，由輸入的浮點數值決定 x。這個功能與原來的程式相比難上不少...原來是想這麼說的，不過突然想起好像一個工具叫作 log?

以下是偷渡 log2 (以二為底) 求 x 的方法，由於題目要求**輸出較大**且最接近的 2^x^，所以在得到 log2 的值後，若 x >= 0 則需要加上 1 以符合此要求。
得到 x 值後再進一步用上面的函式測驗 2^x^ 與輸入的 float 的差距。

int main()
{
    float a;

    while(1) {
        printf("Please input a number : ");
        scanf(" %f", &a);
        printf("\n");
        
        int x = log2(a);
        if((x >= 0) && (x < log2(a))) x++;
        
        printf("THe log value = %f\n", log2(a));    
        printf("x = %d\n", x);
        printf("2^%d = %.20f\n", x, exp2_fp(x));
        printf("2^%d = %.20f\n", x-1, exp2_fp(x-1));
    }

}

以下為簡易的測試結果，此結果不考慮使用者輸入過大或過小的正值，或輸入值為負的 error。

Please input a number : 0.111111

THe log value = -3.169926
x = -3
2^-3 = 0.12500000000000000000
2^-4 = 0.06250000000000000000

Please input a number : 0.222222

THe log value = -2.169926
x = -2
2^-2 = 0.25000000000000000000
2^-3 = 0.12500000000000000000

Please input a number : 0.5555555555555

THe log value = -0.847997
x = 0
2^0 = 1.00000000000000000000
2^-1 = 0.50000000000000000000

Please input a number : 1.5

THe log value = 0.584963
x = 1
2^1 = 2.00000000000000000000
2^0 = 1.00000000000000000000

Please input a number : 0.018521

THe log value = -5.754694
x = -5
2^-5 = 0.03125000000000000000
2^-6 = 0.01562500000000000000

Please input a number : 0.000068

THe log value = -13.844106
x = -13
2^-13 = 0.00012207031250000000
2^-14 = 0.00006103515625000000

從測試結果可看出，當給定一個單精度的浮點數值，輸出的較大且最接近的 2^x^ 值其實與原輸入的浮點數值有不小差異。若移除命題中 **較大** 的限制，只找出最接近的 2^x^ 值，可使誤差減少。
:::info
TODO:
此議題可討論的面向還有很多，例如：
- 因我們只要找出最接近的整數 x 值，可以不必使用 log2 函式，改以遞迴呼叫或迴圈的方式找出 x < float < x+1 的 x ，應可提高不少效能。
- 移除 x 必須為 int 的限制，以求更精準的表示所輸入的 float 值。雖然這樣等同於以另一 float 去表示這個 float 值，看似沒有意義，但可能在某些應用場景能以花費空間來換取時間也說不定。

這些額外的議題可能得等我完成其他作業再說...
:::

:::danger
很好！有幾點可刺激思考:
1. 現代處理器許多具備 clz (count leading zero) 指令，能加速類似 log2 的運算;
2. 輸入數值的範圍對正確性影響很大，[形式化驗證](https://hackmd.io/s/H1xxp3pF0) 本質上就是做數學層面到工程的探索;

:notes: jserv
:::

## 第 2 週測驗題_測驗`3`
題目如下：

考慮到某些實數的二進位表示形式如同 0.y y y y y ... 0.yyyyy... 這樣的無限循環小數，其中 y 是個 k 位的二進位序列，例如 1 / 3 的二進位表示為 0.01010101... 0.01010101... (y = `01`)，而 1./ 5 的二進位表示為 0.001100110011... 0.001100110011...(y = `0011`)，考慮到以下 y 值，求出對應的十進位分數值。

- y = `010011` => 19/X~1~
- y = `101` => 5/X~2~
- y = `0110` => 2/X~3~

請分別選出最接近的X~1~、X~2~、X~3~

### 想法 & 思考
這題在第一次課堂上作答的時候，因為沒想到適當的解法，所以都是用 **估計** 的：先手算出 y 的十進位小數值，再看和選項中哪個數最接近。
事後回想起來，若將 1~2~ >> 1 = 0.1~2~ 、 010~2~ >> 3 = 0.010~2~ 這樣的概念引入，這題解起來就會快很多。
由於0.yyyy...代表無窮循環小數 ==>
0.yyyy... = (y >> k) + (y >> 2k).... = y * (1 / 2^k^ + 1 / 2^2k^...)公比為 2^k^無窮級數
= y * (1 /(2^k^ - 1)) k 取決於 y 是幾個 bits

- y = `010011` ==> y = 19, k = 6 得到 X~1~ = 2^6^-1 = 63
- y = `101` ==> y = 5, k = 3 得到 X~2~ = 2^3^-1 = 7
- y = `0110` ==> y = 6, k = 4 得到 0.yyyy.. = 6 / (16 - 1) 約分後得 X~3~ = 5

### 延伸問題
給定的分數 (即 N/M 形式，當 N 和 M 都是正整數)，如何轉換成二進位，而且在表達 bit 數量限制的狀況，轉換的誤差是多少？
由於個人覺得浮點數運算十分麻煩，可以的話能不碰就不碰，因此過去 12 小時一直在想，若我們要算 N/M 並且以二進位表示，可不可以不要跟 float 扯上關係。

以下是我得出的結論：

#include <stdlib.h>
#include <stdio.h>

long int frac(unsigned int x, unsigned int y) {
	long int i;

	i = 1;
	int j;
	while((i & 0x80000000) != 0x80000000){
		
		if(x == 0){//shift i till we get enough bits
			while((i & 0x80000000) != 0x80000000) i = i << 1;
		}
		else if(x < y){
			if((x<<1)< 0xffffffff) x = x<<1;
			i = i << 1;
		}
		else{
			x = x - y;
			i++;
		}
	}
	return i;
}

int main()
{
    unsigned int a, b;
	unsigned int Q;//quotient
	int j;
	
    while(1) {
        printf("Please input two numbers : \n");
        scanf(" %u", &a);
		scanf(" %u", &b);
        Q = frac(a, b);
		printf("0.");
		for(j=1; j<31; j++){
			if((Q & (0x80000000 >> j)) != 0) printf("1");
			else printf("0");
		}
		printf("\n");
		printf("\n");
	}
	
	return 1;
}

測試結果

Please input two numbers : 
1
5
0.001100110011001100110011001100

Please input two numbers : 
19
63
0.010011010011010011010011010011

Please input two numbers : 
5
7
0.101101101101101101101101101101

Please input two numbers : 
2
5
0.011001100110011001100110011001

結果看起來不錯，不過我到底在寫什麼鳥呢?
以十進位為例：
若本來 2 / 7 的過程是
2 / 7
= <font color= "red">0.2</font> + (2 - <font color= "red">0.2</font>*7) / 7
= 0.2<font color= "red">8</font> + (0.6 - <font color= "red">0.08</font>*7) / 7
...
上列程式碼做的事就是
2 / 7
= 1/10 *(20/7)
= 1/10 *(<font color= "red">2</font> + 6/7)
= 1/10 * 1/10 *(20 + 60/7)
= 1/10 * 1/10 *(<font color= "red">28</font> + 4/7)
...
不斷使被除數進位，直到大於除數，得到一個整數商值後，再重頭做這些動作。而又因為二進位只有 0 與 1 的特性，因此只要做 Shift 與 Sub 就行了，不必考慮 被除數 - **商數** *除數。
程式碼的核心概念如上所述，接下來只要注意以下幾個小細節就好了：
1. i 的 leftmost bit 用來判斷商數 bits 達到指定長度與否，達到則停止，否則會產生 overflow。
2. 在還未達指定商數長度前就 x - Q*y 就等於 0 的話，則會依照 i 的 leftmost bit 向左 Shift 直到達指定長度。
3. 此法理論上可無限拓展商數長度（藉由分次計算後串接）
:::info
TODO:
將二進位的商數轉換回浮點數，並與浮點數除法比較誤差值。
:::