# 2018q1 第 3 週測驗題 --- ### 測驗 `1` 延續 [從 $\sqrt{2}$ 的運算談浮點數](https://hackmd.io/s/ryOLwrVtz),假設 double 為 32-bit 寬度,考慮以下符合 IEEE 754 規範的平方根程式,請補上對應數值,使其得以運作: ```Clike #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`。 ```Clike #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 找到對應的指令,並說明其作用和限制 ::: ---