# 2018q1 第 3 週測驗題
---
### 測驗 `1`
延續 [從 $\sqrt{2}$ 的運算談浮點數](https://hackmd.io/s/ryOLwrVtz),假設 double 為 32-bit 寬度,考慮以下符合 IEEE 754 規範的平方根程式,請補上對應數值,使其得以運作:
```cpp
#include <stdint.h>
/* A union allowing us to convert between a double and two 32-bit integers.
* Little-endian representation
*/
typedef union {
double value;
struct {
uint32_t lsw;
uint32_t msw;
} parts;
} ieee_double_shape_type;
/* Set a double from two 32 bit ints. */
#define INSERT_WORDS(d, ix0, ix1) \
do { \
ieee_double_shape_type iw_u = { \
.parts.msw = ix0, \
.parts.lsw = ix1, \
}; \
(d) = iw_u.value; \
} while (0)
/* Get two 32 bit ints from a double. */
#define EXTRACT_WORDS(ix0, ix1, d) \
do { \
ieee_double_shape_type ew_u; \
ew_u.value = (d); \
(ix0) = ew_u.parts.msw; \
(ix1) = ew_u.parts.lsw; \
} while (0)
static const double one = 1.0, tiny = 1.0e-300;
double ieee754_sqrt(double x)
{
double z;
int32_t sign = 0x80000000;
uint32_t r, t1, s1, ix1, q1;
int32_t ix0, s0, q, m, t, i;
EXTRACT_WORDS(ix0, ix1, x);
/* take care of INF and NaN */
if ((ix0 & KK1) == KK2) {
/* sqrt(NaN) = NaN, sqrt(+INF) = +INF, sqrt(-INF) = sNaN */
return x * x + x;
}
/* take care of zero */
if (ix0 <= 0) {
if (((ix0 & (~sign)) | ix1) == 0)
return x; /* sqrt(+-0) = +-0 */
if (ix0 < 0)
return (x - x) / (x - x); /* sqrt(-ve) = sNaN */
}
/* normalize x */
m = (ix0 >> 20);
if (m == 0) { /* subnormal x */
while (ix0 == 0) {
m -= 21;
ix0 |= (ix1 >> 11);
ix1 <<= 21;
}
for (i = 0; (ix0 & 0x00100000) == 0; i++)
ix0 <<= 1;
m -= i - 1;
ix0 |= (ix1 >> (32 - i));
ix1 <<= i;
}
m -= KK3; /* unbias exponent */
ix0 = (ix0 & 0x000fffff) | 0x00100000;
if (m & 1) { /* odd m, double x to make it even */
ix0 += ix0 + ((ix1 & sign) >> 31);
ix1 += ix1;
}
m >>= 1; /* m = [m/2] */
/* generate sqrt(x) bit by bit */
ix0 += ix0 + ((ix1 & sign) >> 31);
ix1 += ix1;
q = q1 = s0 = s1 = 0; /* [q,q1] = sqrt(x) */
r = 0x00200000; /* 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 + ((ix1 & sign) >> 31);
ix1 += ix1;
r >>= 1;
}
r = sign;
while (r != 0) {
t1 = s1 + r;
t = s0;
if ((t < ix0) || ((t == ix0) && (t1 <= ix1))) {
s1 = t1 + r;
if (((t1 & sign) == sign) && (s1 & sign) == 0)
s0 += 1;
ix0 -= t;
if (ix1 < t1)
ix0 -= 1;
ix1 -= t1;
q1 += r;
}
ix0 += ix0 + ((ix1 & sign) >> 31);
ix1 += ix1;
r >>= 1;
}
/* use floating add to find out rounding direction */
if ((ix0 | ix1) != 0) {
z = one - tiny; /* trigger inexact flag */
if (z >= one) {
z = one + tiny;
if (q1 == (uint32_t) 0xffffffff) {
q1 = 0;
q += 1;
} else if (z > one) {
if (q1 == (uint32_t) KK4)
q += 1;
q1 += 2;
} else
q1 += (q1 & 1);
}
}
ix0 = (q >> 1) + 0x3fe00000;
ix1 = q1 >> 1;
if ((q & 1) == 1)
ix1 |= sign;
ix0 += (m << KK5);
INSERT_WORDS(z, ix0, ix1);
return z;
}
```
==作答區==
KK1 = ?
* `(a)` 0x1ff00000
* `(b)` 0x2ff00000
* `(c)` 0x3ff00000
* `(d)` 0x4ff00000
* `(e)` 0x5ff00000
* `(f)` 0x6ff00000
* `(g)` 0x7ff00000
* `(h)` 0x8ff00000
* `(i)` 0x9ff00000
* `(j)` 0xaff00000
KK2 = ?
* `(a)` 0x1ff00000
* `(b)` 0x2ff00000
* `(c)` 0x3ff00000
* `(d)` 0x4ff00000
* `(e)` 0x5ff00000
* `(f)` 0x6ff00000
* `(g)` 0x7ff00000
* `(h)` 0x8ff00000
* `(i)` 0x9ff00000
* `(j)` 0xaff00000
KK3 = ?
* `(a)` 31
* `(b)` 63
* `(c)` 127
* `(d)` 255
* `(e)` 511
* `(f)` 1023
* `(g)` 2047
KK4 = ?
* `(a)` 0xffffffff
* `(b)` 0xfffffffe
* `(c)` 0xfffffffd
* `(d)` 0xfffffffc
* `(e)` 0xfffffffb
* `(f)` 0xfffffffa
* `(g)` 0xfffffff9
* `(h)` 0xfffffff8
KK5 = ?
* `(a)` 40
* `(b)` 30
* `(c)` 20
* `(d)` 10
* `(e)` 0
* `(f)` -10
* `(g)` -20
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)
:::info
延伸題目: 解釋上述程式碼何以運作,並且改為 float (單精度) 版本,注意應該用更短的程式碼來實作
:::
---
### 測驗 `2`
考慮到下方函式 `shift_right_arith` 和 `shift_right_logical` 分別表示算術右移和邏輯右移,請嘗試補完程式碼。可由 `sizeof(int) * 8` 得知整數型態 `int` 的位元數 `w`,而位移量 `k` 的有效範圍在 0 到 `w - 1`。
```cpp
#include <stdio.h>
int shift_right_arith(int x, int k) {
int xsrl = (unsigned) x >> k;
int w = sizeof(int) << P1;
int mask = (int) -1 << (P2);
if (x < 0)
return xsrl P3 mask;
return xsrl;
}
unsigned shift_right_logical(unsigned x, int k) {
unsigned xsra = (int) x >> k;
int w = sizeof(int) << P4;
int mask = (int) -1 << (P5);
return xsra P6 P7;
}
```
==作答區==
P1 = ?
* `(a)` 1
* `(b)` 2
* `(c)` 3
* `(d)` -1
* `(e)` -2
* `(f)` -3
* `(g)` 0
P2 = ?
* `(a)` 1
* `(b)` k
* `(c)` k - w
* `(d)` w + k
* `(e)` w
* `(f)` w - k
P3 = ? (為某種 operation)
* `(a)` ^
* `(b)` &
* `(c)` <<
* `(d)` |
* `(e)` >>
* `(f)` +
* `(g)` -
P4 = ?
* `(a)` 1
* `(b)` 2
* `(c)` 3
* `(d)` -1
* `(e)` -2
* `(f)` -3
* `(g)` 0
P5 = ?
* `(a)` 1
* `(b)` k
* `(c)` k - w
* `(d)` w + k
* `(e)` w
* `(f)` w - k
P6 = ? (為某種 operation)
* `(a)` ^
* `(b)` &
* `(c)` <<
* `(d)` |
* `(e)` >>
* `(f)` +
* `(g)` -
P7 = ?
* `(a)` mask
* `(b)` ~mask
Reference:
* [Arithmetic Shift Operations](http://www-mdp.eng.cam.ac.uk/web/library/enginfo/mdp_micro/lecture4/lecture4-3-3.html)
(63)
:::info
延伸題目: 在 x86_64 和 Aarch32/Aarch64 找到對應的指令,並說明其作用和限制
:::
---