# 2020q3 Homework (quiz5)
###### tags: `embedded_master`
###### Contributed by < `huang-me` >

[quiz5 題目](https://hackmd.io/@sysprog/2020-quiz5)

# 測驗1 Floating point division
## 程式碼運作原理

#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 / 2, od ? (slots + 1) >> 1 : slots >> 1);
    if (od)
        result += divop(result, slots);
    return result;
}

- 將輸入的數字一直除以2，同時如果 slot 為奇數則應該加一之後再除以2，反之則直接除2即可，最後把結果一路累積回到一開始的值就可以得到正確的結果。
## 是否可以透過 tail call optimization 最佳化
因為程式的最後一個動作並不是 call 完就直接 return 而是還有對 result 進行一個加法的計算，因此不能作 tail call optimizaiton。

---

# 測驗2 square root

#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 = 0x01000000;       /* 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) + 0x3f000000;
    ix0 += (m << 23);
	
    INSERT_WORDS(z, ix0);

    return z;
}

- 如果輸入的數字為 0 或者負數的話，分別 return 0 以及 nan。
- 如果輸入的數字指數部分為 255 則代表此數字的值為 NaN 或者 INF，這種情況直接 return 輸入的數即可。
- 剩下的都是可以計算的正數
1. 一開始先處理次方的部分，如果次方本身為偶數的話直接把次方除2，反之則先把 IEEE754 的 Mantissa 部分乘二之後再將次方除2。
2. 因為前面使用有可能將 Mantissa 乘以二，因此 Mantissa 最多可能占據 26 個 bit。
3. 使用牛頓法，利用漸進的方法比較並且處理 Mantissa 使得越來越逼近結果。

## Leetcode 69.sqrt(x)

int mySqrt(int x){
    if (x <= 1)
        return x;
        
    uint32_t t=0, s0=0;
    int r = 1 << ((31 - __builtin_clz(x)) & (~1));
    
    while(r) {
        t = s0 + r;
        if(t <= x) {
            s0 = t + r;
            x -= t;
        }
        r >>= 2;
        s0 >>= 1;
    }
    return s0;
}

- 採取與老師一樣的策略，如果輸入的值小於1就直接 return 輸入的值本身。
- r 的值則是輸入值的最高位元或者下一位元（取決於何者為偶數 bit）
- 接下來都跟老師的一樣

# 測驗3 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 -= (i - 1);
        if (x % i == 0)
            ret++;
    }
    return ret;
} 

把 N 分成 i 等分，並且因為必須是連續的整數，所以後面的數字並定比前面的大 1，也利用此特性，在 for 迴圈裡面我們將 x 減 i-1(其中 i 是給每個 element 加一，1 則是把最小數的 1 拿回來)

> e.g. $N = 9$
> $i=2$: 先分配 0、1 再把剩下的 8 平分給兩個，如果整除的話就代表可以平均分配
> $i=3$: 先分配 0、1、2 再把剩下的 6 平分給三個數字
> 後面原理不變

## Leetcode 829. Consecutive Number Sum

int consecutiveNumbersSum(int N){
    if(N <= 1)
        if(N < 1) return 0;
        else return 1;
    
    int count = 0;
    
    for(int i=1; i<=N; i++) {
        N -= i;
        if(N % i == 0)
            count++;
    }
    
    return count;
}


經過了長時間的思考我還是沒有想出更好的方法，畢竟老師給的實做方式已經幾乎沒有使用過多的除法也沒有使用到多餘的迴圈，不過個人比較喜歡 `N -= i` 感覺比較直覺，因此修改了一下程式碼，意外得到 0ms 的執行成績，不過應該是因為 leetcode 的執行時間測試不凖所造成 :cry: 。

:::warning
試著觀察數值間的關聯，移去 modulo (`%`)

:notes: jserv
:::