# 2020q3 Homework5 (quiz5)

contributed by < `blueskyson` >

###### tags: `linux2020`

## 測驗 `1`

考慮到以下浮點數除法程式: (fdiv.c)

#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;
}

假設 divop() 的第二個參數必為大於 0 的整數，而且不超過 int 型態能表達的數值上界。請補完程式碼。

### 解題

第 5 行，如果 `slots` 等於 1 或 `orig` 等於 0 則直接回傳 `orig` 的值。
第 7 行判斷 `slots` 是否為奇數。
第 8 行，若 `slots` 為偶數，則將 `orig` 和 `slot` 同除以 2 再相除； 否則將 `orig` 和 `(slot + 1)` 同除以 2 再相除，所以得到 ==D1== = 2, ==D2== = 1

閱讀 `sammer1107` 的作業，得知 9 和 10 行的作用，就是將 `(slot + 1)` 多除的部分加回去:
\begin{align}
\frac{a}{b} =& \frac{a}{b+1}\frac{b+1}{b} \\
=& \frac{a}{b+1}(1+\frac{1}{b}) \\
=& \frac{\frac{a}{2}}{\frac{b+1}{2}} + \frac{\frac{a}{2}}{\frac{b+1}{2}} \frac{1}{b} \\
=& \ result \ + \ result/slots
\end{align}

## 測驗 `2`
延續 [從 $\sqrt{2}$ 的運算談浮點數](https://hackmd.io/s/ryOLwrVtz)，假設 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;
}

Reference:

- [Floating point division and square root algorithms and implementation in the AMD-K7/sup TM/ microprocessor](http://ieeexplore.ieee.org/document/762835/)
- [√Square Roots](http://www.azillionmonkeys.com/qed/sqroot.html)

請補完程式碼，使上述程式碼得以運作。

### 解題

==QQ0== = 0x01000000

## 測驗 `3`

[LeetCode 829. Consecutive Numbers Sum](https://leetcode.com/problems/consecutive-numbers-sum/) 給定一個正整數 N，問 N 能寫成多少種連續正整數之和，例如 9 可寫成 $4+5$，或者 $2+3+4$。由於要寫成連續正整數之和，則可用等差數列來思考，且差值為 1，這個等差數列不必從 1 開始，假設從 x 開始，且個數共有 k 個，則可寫出該等差數列為：

$$x, x+1, x+2, ..., x+(k-1)$$

令其和為 N，根據等差數列的求和公式，可寫出以下等式：

$$kx + \frac{(k-1)k}{2} = N$$

整理後可得：

$$kx = N - \frac{(k-1)k}{2}$$

對任意 k 值，倘若 x 能得到正整數解，就表示必定會有個對應的等差數列和為 N。由於 k 是等差數列的長度，首先必定大於 0，即為下限。由於 x 也必是正整數，可得:

$$N - \frac{(k-1)k}{2} > 0$$

從而得到近似解：

$$k < \sqrt{2N}$$

確認 k 的範圍後，即可走訪數值。

參考實作如下:

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;
} 

請補完程式碼，使上述程式碼得以運作。

### 解題

閱讀 `sammer1107` 的作業， `i` 對應 $kx = N - \frac{(k-1)k}{2}$ 的 $k$ ，將 $k=2,3,4,5,...$ 代入 $\frac{(k-1)k}{2}$ 會得到 $1,3, 6,10,...$ ，正好就是 `1 - i` 累加的值。

所以， `x += ZZZ` 正是對應到 $N - \frac{(k-1)k}{2}$ 這個式子，下一行 `x % i == 0` 便是驗證是否存在 $kx$。因此 ==ZZZ== = 1 - i