# 2020q3 Homework5 (quiz5)
contributed by < `chi-ming5566` >
> [測驗題](https://hackmd.io/@sysprog/2020-quiz5)
---
### `測驗一`
```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;
}
```
* 首先假設 divop() 的第二個參數必大於 0 ,且為整數。
* 而當 `dividend=0` 或 `1` 時,則直接回傳結果。
* 第七行`od = slots & 1`是用來判斷 divisor 是奇數還偶數:
* 如果是偶數,那麼我們可以將 dividend 、 divisor都除以 2,結果不變,且可以看到當`od=0`時`slots >> 1`,所以`D1 = 2`。
* 如果是奇數,則需要其他操作,因為`od=1`時會使用`(slots + D2) >> 1`,可以猜想到`D2`的目的是要把 divisor 變為偶數,先假設`D2 = 1`:
* 原先我們預期的結果是 $A ÷ B$,但這裡先將 `divisor + 1`來得到 $A ÷ (B+1)$這個數字,因此,我們需要補上 $A ÷ (B+1)$ 及 $A ÷ B$ 這兩數之間的誤差。
* 再來看誤差值的計算:
$A ÷ B$ ${ - }$ $A ÷(B+1)$
$=$ $\dfrac{A}{B}$ - $\dfrac{A}{B+1}$
$=$ $\dfrac{A(B+1)}{B(B+1)}$ - $\dfrac{AB}{(B+1)B}$
$=$ $\dfrac{A}{B(B+1)}$
可以發現到$\dfrac{A}{B+1}$就是執行第 8 行的結果,也就是`result`,並且`slots`就是 B,因此`divop(result,slot)`就等於$\dfrac{A}{B+1}$。
---
### `測驗二`
```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;
}
```
```cpp
#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)
```
`INSERT_WORDS` 是用來將`int`型態的 ix0 轉換成 `float` 的 d ,`EXTRACT_WORDS` 則是用來將 `float` 型態的 d 轉換成`int`的 ix0 。
```cpp
if (ix0 <= 0) {
if ((ix0 & (~sign)) == 0)
return x; /* sqrt(+-0) = +-0 */
if (ix0 < 0)
return (x - x) / (x - x); /* sqrt(-ve) = sNaN */
}
```
判斷 `ix0` 是否為 0 或負數,如果是 0 則回傳 0,負數則回傳 NAN。
```cpp
if ((ix0 & 0x7f800000) == 0x7f800000) {
/* sqrt(NaN) = NaN, sqrt(+INF) = +INF,*/
return x;
}
```
Exponent 全為 1 的時候,如果 fraction 全為 0 是 INF,fraction 不全為 0 則是 NAN。
---
### `測驗三`
```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;
}
```
首先討論連續的數字各數 k 的情況:
* `k=1`,每個數字都可以看成 1 個連續的數字,因此 `ret` 初始值設為 1。
* `k=2`,ex : 1+2, 2+3, 3+4。
* `k=3`,ex : 1+2+3, 2+3+4, 3+4+5。
再來透過以下表格,整理連續 k 個數字有可能對應的 N 值,而且
` n>=0 && n is a integer` :
| k | N | func(n)|
| :--- | :----: | ----: |
| 1 | 1, 2, 3, 4, 5, 6 | 0+1*n |
| 2 | 3, 5, 7, 9, 11, 13 | 1+2*n |
| 3 | 6, 9, 12, 15, 18, 21 | 3+3*n |
| 4 | 10, 14, 18, 22, 26, 30| 6+4*n |
| 5 | 15, 20, 25, 30, 35, 40| 10+5*n |
由此可知, 每個 "k 個連續數字總和的結果",都是一個等差數列,因此我們可以對 " k 個連續數字總和的數列" 歸納出一個公式為$N$ $=$ $c + k*n$ 。