# 2020q3 Homework5 (quiz5)
contributed by < `dalaoqi` >

## 測驗一

考慮到以下浮點數除法程式: (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;
}

如果被除數為 0 或 除數為 1，直接回傳被除數。
`od` 變數為判斷除數是奇數還是偶數：
* 如果 `od` 為 0，表示除數為偶數，因此可以對被除數和除數同時除以 2，所以 `D1` 為 2。
* 如果 `od` 為 1，表示除數為奇數，所以為了將除數變為偶數需要加上奇數所以可能為 `1` 或 `3`。
* 除法可以寫成：\begin{align}\frac{orig}{slots}&=\frac{orig}{slots + 1} \times \frac{slots + 1}{slots} \\&=\frac{orig}{slots + 1} \times (1 + \frac{1}{slots}) \\&=\frac{orig}{slots + 1} + \frac{orig}{(slots+1)slots}\end{align}
* 根據上面的式子推斷 `D2` 為 `1`，而最後的 `if` 判斷式則呼應上面式子的第二項。

## 測驗二
假設 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;
}

一開始浮點數 `x` 會先經由 `EXTRACT_WORDS(ix0, x)` 轉成 32 bit 整數以便做後面的操作。

---
**0 與負數的處理**

    /* 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 */
    }

當 `ix0` 為 0 或是 負數的時候，會分別回傳 `0` 和 `NAN`。
* 0 的浮點數表示為 `(0 00000000...000)` 和 `(1 00000000...000)`
* `(~sign)` 為 `(0 11111111...111)`
---
**INF 與 NAN 的處理**

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

當 `ix0` 為 +INF
* sign bit 為 0
* exponent bit 為 `11111111`
* fraction bit 都為 0

當 `ix0` 為 NAN
* sign bit 為 0 or 1
* exponent bit 為 `11111111`
* fraction bit 不為全 0

對應的 mask 為 `0x7f800000` 且 +INF 及 NAN 開平方根為自己本身。

---

## 測驗三
LeetCode [829. Consecutive Numbers Sum](https://leetcode.com/problems/consecutive-numbers-sum/)，給定一個正整數 N，問 N 能寫成多少種連續正整數之和。
參考實作如下：

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

假設等差數列如下：
$$x,x+1,x+2,...,x+(k-1)$$
令其和為 N，根據等差數列的求和公式，可寫出以下等式：
$$
kx+\frac{(k-1)k}{2} = N \\
\Rightarrow kx = N - \frac{(k-1)k}{2} \\
\Rightarrow kx = N - [1+2+...+(k-1)]
$$
推得 $N - [1+2+...+(k-1)] \space mod \space k=0$
所以 `ZZZ` 為 `1-i`