# 2020q3 Homework5 (quiz5)
contributed by < `Sisker1111` >
###### tags: `進階電腦系統理論與實作`
> [測驗題](https://hackmd.io/@sysprog/SJvxlt0vv)
>
## 測驗 1
考慮到以下浮點數除法程式: (fdiv.c)
假設 divop() 的第二個參數必為大於 0 的整數，而且不超過 int 型態能表達的數值上界。

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

double divop(double orig, int slots) {
    if (slots == 1 || orig == 0)
        return orig;
    int od = slots & 1;
    double result = divop(orig / D1, od ? (slots + D2) >> 1 : slots >> 1);
    if (od)
        result += divop(result, slots);
    return result;
}

+ 首先，當`dividend=0` or `divisor=1`時，直接回傳結果.
+ 第七行`od = slots & 1`是用來判斷 divisor 是奇數還偶數:
+ 如果是偶數，那麼我們可以將 dividend 、 divisor都除以 2，結果不變，我們可以看到當`od=0`時`slots >> 1`，因此很明顯的`D1 = 2`.
+ 如果是奇數，我們需要其他操作，因為`od=1`時會使用`(slots + D2) >> 1`，可以猜想到`D2`的目的應該是要把 divisor 變為偶數，先假設`D2 = 1`，接著討論最關鍵的部分.
1. 原先我們預期的結果是 $A ÷ B$，但這裡我們會先將 `divisor + 1`來得到 $A ÷ (B+1)$這個數字，因此，我們需要補上 $A ÷ (B+1)$ 及 $A ÷ B$ 這兩數之間的誤差.

* 誤差值計算:
$A ÷ B$ ${ - }$ $A ÷(B+1)$
$=$ $\dfrac{A}{B}$ - $\dfrac{A}{B+1}$
$=$ $\dfrac{A(B+1)}{B(B+1)}$ - $\dfrac{AB}{(B+1)B}$
$=$ $\dfrac{A}{B(B+1)}$
可以發現到$\dfrac{A}{B+1}$就是執行程式第 8 行的結果，也就是`result`，並且`slots`就是 B，因此`divop(result,slot)`就等於$\dfrac{A}{B+1}$.

## 測驗 2
假設 float 為 32-bit 寬度，考慮以下符合 IEEE 754 規範的平方根程式，請補上對應數值，使其得以運作：

#include <stdint.h>

/* A union allowing us to convert between a float and a 32-bit integers.*/
typedef union {
    float value;
    uint32_t v_int;
} ieee_float_shape_type;

/* Set a float from a 32 bit int. */
#define  INSERT_WORDS(d, ix0)	        \
    do {                                \
        ieee_float_shape_type iw_u;     \
            iw_u.v_int = (ix0);         \
        (d) = iw_u.value;               \
    } while (0)

/* Get a 32 bit int from a float. */
#define EXTRACT_WORDS(ix0, d)        \
    do {                             \
        ieee_float_shape_type ew_u;  \
        ew_u.value = (d);            \
        (ix0) = ew_u.v_int;          \
    } while (0)

static const float one = 1.0, tiny = 1.0e-30;

float ieee754_sqrt(float x)
{
    float z;
    int32_t sign = 0x80000000;
    uint32_t r;
    int32_t ix0, s0, q, m, t, i;
	
    EXTRACT_WORDS(ix0, x);
	
    /* take care of zero */
    if (ix0 <= 0) {
        if ((ix0 & (~sign)) == 0)
            return x; /* sqrt(+-0) = +-0 */
        if (ix0 < 0)
            return (x - x) / (x - x); /* sqrt(-ve) = sNaN */
    }
    /* take care of +INF and NaN */
    if ((ix0 & 0x7f800000) == 0x7f800000) {
        /* sqrt(NaN) = NaN, sqrt(+INF) = +INF,*/
        return x;
    }
    /* normalize x */
    m = (ix0 >> 23);
    if (m == 0) { /* subnormal x */
        for (i = 0; (ix0 & 0x00800000) == 0; i++)
            ix0 <<= 1;
        m -= i - 1;
    }
    m -= 127; /* unbias exponent */
    ix0 = (ix0 & 0x007fffff) | 0x00800000;
    if (m & 1) { /* odd m, double x to make it even */
        ix0 += ix0;
    }
    m >>= 1; /* m = [m/2] */
	
    /* generate sqrt(x) bit by bit */
    ix0 += ix0;
    q = s0 = 0; /* [q] = sqrt(x) */
    r = QQ0;       /* r = moving bit from right to left */

    while (r != 0) {
        t = s0 + r;
        if (t <= ix0) {
            s0 = t + r;
            ix0 -= t;
            q += r;
        }
        ix0 += ix0;
        r >>= 1;
    }

    /* use floating add to find out rounding direction */
    if (ix0 != 0) {
        z = one - tiny; /* trigger inexact flag */
        if (z >= one) {
            z = one + tiny;
            if (z > one)
                q += 2;
            else
                q += (q & 1);
        }
    }
	
    ix0 = (q >> 1) + QQ1;
    ix0 += (m << QQ2);
	
    INSERT_WORDS(z, ix0);

    return z;
}

首先逐一了解程式的各個部分在做什麼:

這邊定義了一個 macro 的擬函式，`INSERT_WORDS`用來將`int`型態的 ix0 轉換成`float`的 d ，`EXTRACT_WORDS`則相反，用來將`float`型態的 d 轉換成`int`的 ix0 .

#define  INSERT_WORDS(d, ix0)	        \
    do {                                \
        ieee_float_shape_type iw_u;     \
            iw_u.v_int = (ix0);         \
        (d) = iw_u.value;               \
    } while (0)

/* Get a 32 bit int from a float. */
#define EXTRACT_WORDS(ix0, d)        \
    do {                             \
        ieee_float_shape_type ew_u;  \
        ew_u.value = (d);            \
        (ix0) = ew_u.v_int;          \
    } while (0)

判斷`ix0`是否為 0 或負數，如果是 0 則回傳 0，負數則回傳 NAN.

if (ix0 <= 0) {
        if ((ix0 & (~sign)) == 0)
            return x; /* sqrt(+-0) = +-0 */
        if (ix0 < 0)
            return (x - x) / (x - x); /* sqrt(-ve) = sNaN */
    }

Exponent 全為 1 的時候，如果 fraction 全為 0 是 INF，fraction 不全為 0 則是 NAN.

 if ((ix0 & 0x7f800000) == 0x7f800000) {
        /* sqrt(NaN) = NaN, sqrt(+INF) = +INF,*/
        return x;
    }

## 測驗 3
對應LeetCode [829. Consecutive Numbers Sum](https://leetcode.com/problems/consecutive-numbers-sum/)
個人認為這周的測驗真的很難，很多細節都是參考別人的說明才得到啟發.

int consecutiveNumbersSum(int N)
{
    if (N < 1)
        return 0;
    int ret = 1;
    int x = N;
    for (int i = 2; i < x; i++) {
        x += ZZZ;
        if (x % i == 0)
            ret++;
    }
    return ret;
} 

首先討論連續的數字各數 k 的情況:
* `k=1`，每個數字都可以看成 1 個連續的數字，因此 ret 初始值設為 1.
* `k=2`，ex : 1+2, 2+3, 3+4
* `k=3`，ex : 1+2+3, 2+3+4, 3+4+5.

我們可以透過以下表格，整理連續 k 個數字有可能對應的 N 值，其中
` n>=0 && n is a integer`:

| k | N | func(n)|
| :--- | :----: | ----: |
| 1 | 1, 2, 3, 4, 5, 6 | 0+1*n |
| 2 | 3, 5, 7, 9, 11, 13 | 1+2*n |
| 3 | 6, 9, 12, 15, 18, 21 | 3+3*n |
| 4 | 10, 14, 18, 22, 26, 30| 6+4*n |
| 5 | 15, 20, 25, 30, 35, 40| 10+5*n |

可以發現，每個 `k 個連續數字總和的結果`，都是一個等差數列，因此我們可以對` k 個連續數字總和的數列`歸納出一個公式為$N$ $=$ $c + k*n$

對應回程式碼:

int consecutiveNumbersSum(int N)
{
    if (N < 1)
        return 0;
    int ret = 1;
    int x = N;
    for (int i = 2; i < x; i++) {
    /*判斷是否為 k 個連續數字總和的數列*/
        x += 1-i;     /* 把常數 c 值扣掉*/
        
        if (x % i == 0) /* 判斷是否能夠整除 k */
            ret++;    
    }
    return ret;
}