# 2020q3 Homework5 (quiz5)
[toc]

## 測驗 1

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

double divop(double orig, int slots) {
    if (slots == 1 || orig == 0)
        return orig;

除數為 1 或被除數為 0 直接回傳被除數

    int od = slots & 1;
    double result = divop(orig / 2, od ? (slots + 1) >> 1 : slots >> 1);

除數為偶數則兩者一起除 2 ，為奇數則加 1 後除 2，之後再將加一導致變小的商補回

    if (od)
        result += divop(result, slots);

$$
\begin{align}
\frac{orig}{slots} =& \frac{orig}{slots+1}\frac{slots+1}{slots} \\
=& \frac{orig}{slots+1}(1+\frac{1}{slots}) \\
=& \frac{orig}{slots+1}+\frac{orig}{slots+1} \times \frac{1}{slots} \\
\end{align}
$$
也就是要加上再除以 slots 的 result

    return result;
}

## 測驗 2

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

typedef union 方便我們可以在同一塊記憶體空間使用不同讀取方式，本題用來 f32 與 int 的轉換

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

上面的 if 應該可以用 ix0 == 0
下面的 if 應該回傳 0 / 0 即可

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

shift right 23 是為了將 23 個 fraction bits 去除，因為負數前面已經處理完了，這邊不需考慮 sign bit
以 signed int32 m 紀錄 exponent
m 等於 0 表示為 denormal ，處理方式為強制轉為 normal 並以 m 紀錄轉換後的 exponent ，為負數

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

將 m 扣除 bias 呈現出真實的 exponent
讓 ix0 只保留 fraction 並在 fraction 左側補上 1 代表 normalized number 預設小數點前一位的 1
將 m 除以 2 就可達到開根號，但要避免 m 為奇數的情況，對於奇數的 m ，將 ix0 乘二，如次一來當 m >> 1 時，不用擔心奇數 m 會損失 LSB 的 1

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