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)$ .....的概念。
Sign in with Wallet
Connect another wallet