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

###### tags: `linux2020` `sysprog2020` `quiz`
[題目連結](https://hackmd.io/@sysprog/2020-quiz5)

## :memo: 目錄
[TOC]
## 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 型態能表達的數值上界。請補完程式碼。
* 動作說明:
* 假設除數為 X，被除數為 Y。
* 一開始先決定遞迴函式終止條件,先檢查被除數是否為 '0', 及除數是否為'1',若成立,即返回被除數.
* 接著由於判斷除數為奇術還是偶數:
* 偶數則直接計算 $\dfrac{X}{Y}$ $=$ $\dfrac{X/2}{Y/2}$
* 奇數則依 $\dfrac{X}{Y}$ $=$ $\dfrac{X}{Y+1}$ $+$ $\dfrac{X}{Y(Y+1)}$ 拆成兩部分,分別計算,加總並傳回結果.
* 在此, 選擇 D1 = 2, D2 = 1 以符合結果.

作答:
* D1: 2
* D2: 1
## 2. ieee754_sqrt()
延續從 √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 & 0x7ff00000) == 0x7ff00000) {
        /* 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;
}

QQ0 = 0x01000000

QQ1 = 0x3f000000

QQ2 = 23
* 動作說明:
* 首先使用 union 來做 float 和 int32_t 的型態轉換.
* 接著做一些 exception handling. 包括: +-0, 0.0/0.0 (sNaN), 負浮點數, 以及 +INF 和 NaN.
* 以 int32_t m 的最右 8 個 bit 儲存 x 的 sign 和 exponent 部分(m 的其他 bit 設為 0)。
* 再來若 m 為'0', 則對做正規化: 將 fraction 左移直到 overflow, 並對 m 減掉相對應的值. 再修正 m 的偏移量 (-127)

## 3. Consecutive Numbers Sum
LeetCode 829. 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 + (k-1)k / 2 = N
變形後可得：

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

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

ZZZ = 1 - i