# [2020q3](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 5 週測驗題
###### tags: `sysprog2020`
:::info
目的: 檢驗學員對 [浮點數運算](https://hackmd.io/@sysprog/c-floating-point), [數值系統](https://hackmd.io/@sysprog/c-numerics) 及 [bitwise 操作](https://hackmd.io/@sysprog/c-bitwise) 的認知
:::
==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSfMdc1mXSL4mxLygfMZi7A0XaoBDLZl9gjRpCXpbYD0ITSaIg/viewform)==
### 測驗 `1`
考慮到以下浮點數除法程式: (fdiv.c)
```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` 的整數，而且不超過 `int` 型態能表達的數值上界。請補完程式碼。
==作答區==
`D1` = ?
* `(a)` 4
* `(b)` 3
* `(c)` 2
* `(d)` 1
`D2` = ?
* `(a)` 4
* `(b)` 3
* `(c)` 2
* `(d)` 1
:::success
延伸問題:
1. 解釋上述程式碼運作原理;
2. 以編譯器最佳化的角度，推測上述程式碼是否可透過 [tail call optimization](https://en.wikipedia.org/wiki/Tail_call) 進行最佳化，搭配對應的實驗;
* 搭配閱讀 [C 語言: 編譯器和最佳化原理](https://hackmd.io/s/Hy72937Me) 及 [C 語言: 遞迴呼叫](https://hackmd.io/s/rJ8BOjGGl)
3. 比照 [浮點數運算和定點數操作](https://hackmd.io/@NwaynhhKTK6joWHmoUxc7Q/H1SVhbETQ)，改寫上述程式碼，提出效率更高的實作，同樣避免使用到 FPU 指令 (可用 `gcc -S` 觀察對應的組合語言輸出)，並與使用到 FPU 的實作進行效能比較
:::
---
## 測驗 `2`
延續 [從 $\sqrt{2}$ 的運算談浮點數](https://hackmd.io/s/ryOLwrVtz)，假設 float 為 32-bit 寬度，考慮以下符合 IEEE 754 規範的平方根程式，請補上對應數值，使其得以運作：
```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;
}
```
Reference:
* [Floating point division and square root algorithms and implementation in the AMD-K7/sup TM/ microprocessor](http://ieeexplore.ieee.org/document/762835/)
* [√Square Roots](http://www.azillionmonkeys.com/qed/sqroot.html)
請補完程式碼，使上述程式碼得以運作。
==作答區==
QQ0 = ?
* `(a)` 0x01000000
* `(b)` 0x7ff00000
* `(c)` 0x00800000
* `(d)` 0x3f000000
QQ1 = ?
* `(a)` 0x01000000
* `(b)` 0x7ff00000
* `(c)` 0x00800000
* `(d)` 0x3f000000
QQ2 = ?
* `(a)` 31
* `(b)` 30
* `(c)` 28
* `(d)` 27
* `(e)` 25
* `(f)` 24
* `(g)` 23
* `(h)` 16
* `(i)` 3
:::success
延伸題目:
1. 解釋上述程式碼何以運作
* 搭配研讀 [以牛頓法求整數開二次方根的近似值](http://science.hsjh.chc.edu.tw/upload_works/106/44f6ce7960aee6ef868ae3896ced46eb.pdf) (第 19 頁)
2. 嘗試改寫為更有效率的實作，並與 FPU 版本進行效能和 precision /accuracy 的比較
3. 練習 LeetCode [69. Sqrt(x)](https://leetcode.com/problems/sqrtx/)，提交不需要 FPU 指令的實作
:::
---
## 測驗 `3`
LeetCode [829. Consecutive Numbers Sum](https://leetcode.com/problems/consecutive-numbers-sum/) 給定一個正整數 N，問 N 能寫成多少種連續正整數之和，例如 `9` 可寫成 $4+5$，或者 $2+3+4$。由於要寫成連續正整數之和，則可用等差數列來思考，且差值為 1，這個等差數列不必從 1 開始，假設從 x 開始，且個數共有 k 個，則可寫出該等差數列為：
$$
x, x+1, x+2, ..., x+(k-1)
$$
令其和為 N，根據等差數列的求和公式，可寫出以下等式：
$$
kx + \frac{(k-1)k}{2} = N
$$
整理後可得：
$$
kx = N - \frac{(k-1)k}{2}
$$
對任意 k 值，倘若 x 能得到正整數解，就表示必定會有個對應的等差數列和為 N。由於 k 是等差數列的長度，首先必定大於 0，即為下限。由於 x 也必是正整數，可得:
$$
N - \frac{(k-1)k}{2} > 0
$$
從而得到近似解：
$$
k < \sqrt{2N}
$$
確認 k 的範圍後，即可走訪數值。
參考實作如下:
```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 = ?
* `(a)` i
* `(b)` i + 1
* `(c)` i - 1
* `(d)` 1 - i
* `(e)` 1
:::success
延伸題目:
1. 解釋上述程式碼何以運作
2. 嘗試改寫為更有效率的實作
:::
---
Sign in with Wallet
Connect another wallet