Try   HackMD

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

最簡單和常見的數學歸納法是證明當_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 代表 22n 也就是 ：1, 4, 16, 64…這些數共同的特色是 3pi+1
偶數位的 1 代表 22n+1 也就是 ：2, 8, 32, 128…這些數共同的特色是 3qi-1

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

延伸問題

  • 為什麼上述程式碼可運作呢？上列已解釋並證明。
  • 將 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 的倍數，其餘則非。

說來慚愧，會有以上的概念並不是我突然靈光一閃，是在搜尋的過程中看到了一篇國小科展…才讓我想起 11 倍數判斷的原理並加以推廣。

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

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

第 2 週測驗題_測驗1

題目如下：

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

  • 當 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 輸出 2x 的浮點數值。

想法 & 思考

這段 code 註解清楚的將整個程式依照輸入的 x 值，分成 4 個範圍（與浮點數表示法相呼應）：

  • too small
    單精度浮點數表示法，能表現的最小正值為
    0 0…0 0…1
    也就是 signed bit 為零;
    exponent bits 全為零;
    fraction 為 2-23
    對應到的 2x ，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) × 2127 < 2128 因此 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

延伸問題

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

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

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

從測試結果可看出，當給定一個單精度的浮點數值，輸出的較大且最接近的 2x 值其實與原輸入的浮點數值有不小差異。若移除命題中 較大 的限制，只找出最接近的 2x 值，可使誤差減少。

TODO:
此議題可討論的面向還有很多，例如：

  • 因我們只要找出最接近的整數 x 值，可以不必使用 log2 函式，改以遞迴呼叫或迴圈的方式找出 x < float < x+1 的 x ，應可提高不少效能。
  • 移除 x 必須為 int 的限制，以求更精準的表示所輸入的 float 值。雖然這樣等同於以另一 float 去表示這個 float 值，看似沒有意義，但可能在某些應用場景能以花費空間來換取時間也說不定。

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

很好！有幾點可刺激思考:

  1. 現代處理器許多具備 clz (count leading zero) 指令，能加速類似 log2 的運算;
  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
Learn More →
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/X1
  • y = 101 => 5/X2
  • y = 0110 => 2/X3

請分別選出最接近的X1、X2、X3

想法 & 思考

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

  • y = 010011 ==> y = 19, k = 6 得到 X1 = 26-1 = 63
  • y = 101 ==> y = 5, k = 3 得到 X2 = 23-1 = 7
  • y = 0110 ==> y = 6, k = 4 得到 0.yyyy.. = 6 / (16 - 1) 約分後得 X3 = 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
= 0.2 + (2 - 0.2*7) / 7
= 0.28 + (0.6 - 0.08*7) / 7
…
上列程式碼做的事就是
2 / 7
= 1/10 *(20/7)
= 1/10 *(2 + 6/7)
= 1/10 * 1/10 *(20 + 60/7)
= 1/10 * 1/10 *(28 + 4/7)
…
不斷使被除數進位，直到大於除數，得到一個整數商值後，再重頭做這些動作。而又因為二進位只有 0 與 1 的特性，因此只要做 Shift 與 Sub 就行了，不必考慮 被除數 - 商數 *除數。
程式碼的核心概念如上所述，接下來只要注意以下幾個小細節就好了：

  1. i 的 leftmost bit 用來判斷商數 bits 達到指定長度與否，達到則停止，否則會產生 overflow。
  2. 在還未達指定商數長度前就 x - Q*y 就等於 0 的話，則會依照 i 的 leftmost bit 向左 Shift 直到達指定長度。
  3. 此法理論上可無限拓展商數長度（藉由分次計算後串接）

TODO:
將二進位的商數轉換回浮點數，並與浮點數除法比較誤差值。

Last changed by 
 
Lai Dong
0
903
Published on HackMD