---
# System prepended metadata

title: 2020q3 Homework5 (quiz5)
tags: [進階電腦系統理論與實作]

---

2020q3 Homework5 (quiz5)
===
contribute by `Liao712148`
*    1.從新回答[第5周測驗題](https://hackmd.io/@sysprog/2020-quiz5)
###### tags: `進階電腦系統理論與實作` 

## 測驗1
```cpp=
#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;
}
```
透過第`8`行我們想要將除數和被除數中的`2`的因式都先約掉，如果`slots`是奇數則會有小數點的情況出現，但是`slots`是`int`的形式會將小數點省略，導致計算上的誤差。所以透過將奇數的`slots`+`1`轉為偶數，可避免誤差發生
所以`D1`選`2` ,`D2`選`1`
但會造成==除數變大==，使得算出來的答案會略小，所以要透過`9,10`行將誤差補回去。
舉例來說:
$\dfrac{orig}{slots}$，$slots$為奇數
$K=\dfrac{orig/2}{(slots+1)/2}$v.s$\dfrac{orig/2}{slots/2}=N$其中 $N$為理想解
因為$N=K+(N-K)$，所以$K$要再藉由加上$N-K$來補償，將上式代入可得
$\dfrac{orig/2}{slots/2}-\dfrac{orig/2}{(slots+1)/2}=$$\dfrac{orig}{(slots+1)(slots)}=\dfrac{K}{slots}$，所以$K$要再加上$\dfrac{K}{slots}$才會等於$N$
因此對應到` result += divop(result, slots)`



### 延伸題目:




---

## 測驗2
```cpp=
#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;
}
```
由`EXTRACT_WORDS(ix0, d)`可以將輸入`float`轉成`32 bit int`的形式，透過的是`union`的特性，`union`結構中的各變數是共用記憶體位置，其內部成員的數值會由最後一個`assign`的值決定，如果`type`不同會依據成員的`type`做一個`type`的轉換。
所以現在`ix0`相當於是`int32_t ix0=(int32_t)d`作了一個`cast`。而`INSERT_WORDS(d, ix0)`則是轉回`float`的形式。


### 延伸題目:
*    練習 [LeetCode 69. Sqrt(x)](https://leetcode.com/problems/sqrtx/submissions/) ，提交不需要 FPU 指令的實作
利用[以牛頓法求整數開二次方根的近似值](https:// "http://science.hsjh.chc.edu.tw/upload_works/106/44f6ce7960aee6ef868ae3896ced46eb.pdf")求整數開根號，因為用牛頓法解題時，初始位子影響到了收斂到解的次數，所以先根據$N$大概的大小給定較接近的初始值，再利用[goto 和流程控制篇](https://hackmd.io/@sysprog/c-control-flow?type=view)提到的`goto`來實現跳躍的動作。
方法如下:
```cpp=
int mySqrt(int x){
    if(x==0)
        return(0);
    double a=0;
    int temp;
    if(0x70000000&x) {a=65536;goto label;}
    if(0x0F000000&x) {a=16384;goto label;}
    if(0x00F00000&x) {a=4096;goto label;}
    if(0x000F0000&x) {a=1024;goto label;}
    if(0x0000F000&x) {a=256;goto label;}
    if(0x00000F00&x) {a=64;goto label;}
    if(0x000000F0&x) {a=16;goto label;}
    if(0x0000000F&x) {a=4;goto label;}
    label:do
    {double b=(a+(x/a))/2.0;
    temp=a-b;
    a=b;
    }while(temp);
    return a;
}
```
`todo`:用float的型態初始化a,b的時候，在遇到$N=2147395599$到會有overflow的情況，使得回傳值為$46340$而非預期的$46339$，需探討overflow發生的原因。


## 測驗3
```cpp=
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`:
根據題目的引導可以知道$kx=N-\dfrac{(k-1)k}{2}$，$N<\sqrt{2N}$，試著將$N=9$代入
$k=4: 4x=9-\dfrac{(4-1)4}{2}$
$k=3: 3x=9-\dfrac{(3-1)3}{2}$
$k=2: 2x=9-\dfrac{(2-1)2}{2}$
$k=1: 1x=9-\dfrac{(1-1)1}{2}$
其中只有$k=1,2,3$得$x$為正整數，但以上的描述跟程式碼有以點落差，難以選出答案。
所以再作一些修改
$k=4: 4x=9-\dfrac{(4-1)4}{2}=9-6=9-3$ ==-3==
$k=3: 3x=9-\dfrac{(3-1)3}{2}=9-3=9-1$ ==-2==
$k=2: 2x=9-\dfrac{(2-1)2}{2}=9-1=9-0$ ==-1==
$k=1: 1x=9-\dfrac{(1-1)1}{2}=9-0$
由上式可以知道在算$k=2$時可以利用$k=1$已經算出來的部分，以此類推。所以整個程式就變成
`x =x(來自前一個)+ZZZ(實現hightlight的部分)`。
所以`ZZZ`要選`1-i`。


### 延伸問題
*    嘗試改寫更有效率的實作
參考至[[Java/C++/Python] Fastest, Count Odd Factors, O(logN)](https://leetcode.com/problems/consecutive-numbers-sum/discuss/128947/JavaC%2B%2BPython-Fastest-Count-Odd-Factors-O(logN))
```cpp=
int consecutiveNumbersSum(int N)
{
     int res = 1, count;
        while (N % 2 == 0) N /= 2;
        for (int i = 3; i * i <= N; res *= count + 1, i += 2)
            for (count = 0; N % i == 0; N /= i, count++)
        return N == 1 ? res : res * 2;
} 
```
以下是他的演算法
因為根據$N\times2=k(2x+k+1),where\ x>=0,\ k>=1$
N要是整數，所以$k$ or $(2x+k+1)$要是奇數，
*    假設兩者都是偶數則$2k$為偶數，且$k$也為偶數，則$2x+k$必為偶數，造成$2x+k+1$為奇數，與假設產生矛盾。
*    假設兩者都是奇數，則兩個奇數相乘$k(2x+k+1)$為奇數，不能被2整除，使得N不為整數

所以現在的目標是找出$N$的奇數的因子。
因為$N/2$的奇數因子與$N$一樣，所以可以先將 $N$的2的因數都先除掉，得到奇數因數的數量後即為所求，要特別注意的是==如果$N$本身是質數==，最後算出的$N$還是等於$N$，因為第二個`for`的條件不會滿足(質數只會被自己和1整除，但`i`最小等於3)所以$N$不會等於$1$，因此要透過`return N == 1 ? res : res * 2;`來處理。

第`5`行:
算出$N$包含那些質數的因數。
第`6`行:
計算該質數因數在$N$中出現幾次。
以`5,6`行實現
If $N = 3^a \times 5^b \times 7\times c \times 11\times d ....$, the number of factors that $N$ has equals
$N\_ factors = (a + 1) \times (b + 1) \times (c + 1) \times (d + 1)$ .....的概念。