# 2020q3 Homework5 (quiz5)
contributed by < `ChongMingWei` >
## Outline
[TOC]
## 環境
```shell
$ uname -a
Linux cmw-System-Product-Name 5.4.0-47-generic #51~18.04.1-Ubuntu SMP Sat Sep 5 14:35:50 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```
## 測驗1
```c=
#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 / 2, od ? (slots + 1) >> 1 : slots >> 1);//D1 D2
if (od)
result += divop(result, slots);
return result;
}
```
- 判斷除數為1或是被除數為0的時候直接返回被除數
```c=5
if (slots == 1 || orig == 0)
return orig;
```
- `od` 為1表示為奇數
```c=5
int od = slots & 1;
```
- Line8: 如果除數 `slots` 是偶數，那麼就將被除數 `orig` 除以2，除數 right shift 一位；
如果除數 `slots` 是奇數，那麼就將被除數 `orig` 除以2，除數+1後再 right shift 一位。
最後將新的被除數和除數做為下一個遞迴呼叫的 argument。
- Line9-10: 如果除數是奇數，那麼要將商 `result` 再加上 `divop(result, slots)` 的結果。
```c=8
double result = divop(orig / 2, od ? (slots + 1) >> 1 : slots >> 1);//D1 D2
if (od)
result += divop(result, slots);
```
> Reference: [YLowy](https://hackmd.io/@YLowy/HJkXHWCIv)
>
關於上述，可以理解到這個程式碼的想法就是在除數是偶數的時候，同時對被除數以及除數做除以2的運算；
或者是當除數為奇數時，使用近似值 `(slots+1)` 作為除數，然後在得到返回值之後，使用 `op` 來控制是否要進行差值的補償。
有關除數為奇數時的差值補償，可以用以下數學式來解釋:
$Original\ result = \dfrac{orig/2}{slots/2} = \dfrac{orig}{slots} (除數 slots 限於 int 的資料型態無法這麼做，除數直接除以2會得到錯誤的結果)$
$Modified\ result = \dfrac{orig/2}{(slots+1)/2} = \dfrac{orig}{(slots+1)}(得到比較小的結果，必須要再補回和 Original 的差)$
$\begin{split}Original\ result- Modified\ result=& \dfrac{orig}{slots}-\dfrac{orig}{(slots+1)}\\
=&\dfrac{orig}{slots*(slots+1)}\\
=&\dfrac{\dfrac{orig}{slots+1}}{slots}\\
=&\dfrac{Modified\ result}{slots}\end{split}$
$Original\ result = Modified\ result+\dfrac{Modified\ result}{slots}$
Replace the symbol by code:
$Original\ result = divop(orig / 2, (slots + 1) >> 1) + divop(result, slots);$
所以，我們的演算法就先遞迴計算得到近似值，接著再遞迴計算補償值。
:::success
2. 以編譯器最佳化的角度，推測上述程式碼是否可透過 [tail call optimization](https://en.wikipedia.org/wiki/Tail_call) 進行最佳化，搭配對應的實驗;
搭配閱讀 C 語言: [編譯器和最佳化原理](https://hackmd.io/@sysprog/c-compiler-optimization?type=view) 及 C 語言: [遞迴呼叫](https://hackmd.io/@sysprog/c-recursion?type=view)
:::
## 測驗2
> 使用牛頓法找近似值
```c=
#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 & 0x7ff00000) == 0x7ff00000) {
/* 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 */ //QQ0
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) + 0x3f000000;//QQ1 把127加回來
ix0 += (m << 23);//QQ2 把 exponential 移回正確位置
INSERT_WORDS(z, ix0);
return z;
}
```
- 資料結構以及 `uint_32` 和 `float` 之間的轉換
- 使用 union 架構，讓 value 和 v_int 共用同一塊的記憶體，可以藉由指定和操作 `uint_32` 型態的值，來得到==其二進位表示法==所對應的 `float` 型態的值；或是指定`float` 型態的值，來得到==其二進位表示法==(以 `uint_32` 的資料型態儲存)
```c=2
/* 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;
```
E.g.
```c=
ieee_float_shape_type example;
example.v_int = 0x7f800001;
printf("%x\n",example.v_int);
printf("%f\n",example.value);
```
Output
```
7f800001
nan
```
```c=
ieee_float_shape_type example2;
example2.value = 0.5;
printf("%x\n",example2.v_int);
printf("%f\n",example2.value);
```
Output
```
3f000000
0.500000
```
-
## 測驗3
LeetCode [829. Consecutive Numbers Sum](https://leetcode.com/problems/consecutive-numbers-sum/) 給定一個正整數 N，問 N 能寫成多少種連續正整數之和
> 參考 [LeetCode 829. Consecutive Numbers Sum](https://blog.csdn.net/zhangpeterx/article/details/100735382)
s 表示起始的數字，i 表示等差數列中的數字個數
$\begin{split}N &= s + (s+1) + (s+2) + ... + (s+i-1)\\
&= \dfrac{(s+s+i-1)\times s}{2}\\
&= sk+\dfrac{(i-1)\times s}{2}
\end{split}$
$N - \dfrac{(i-1)\times i}{2} = si$
$\begin{split}
s &= \dfrac{N - \dfrac{(i-1)\times i}{2}}{i}\\
&= \dfrac{N-(1+2+...+i-1)}{i}
\end{split}$
- E.g. N = 9
$Number\ of\ arithmetic\ sequence(i) = 1$
$s=\dfrac{9-(0)}{1}=9,\ represents\ that\ the \ arithmetic\ sequence\ is:[9]$
$Number\ of\ arithmetic\ sequence(i) = 2$
$s=\dfrac{9-(1)}{2}=4,\ represents\ that\ the \ arithmetic\ sequence\ is:[4,5]$
$Number\ of\ arithmetic\ sequence(i) = 3$
$s=\dfrac{9-(1+2)}{3}=2,\ represents\ that\ the \ arithmetic\ sequence\ is:[2,3,4]$
$Number\ of\ arithmetic\ sequence(i) = 4$
$s=\dfrac{9-(1+2+3)}{4}=0.75,\ represents\ that\ the \ arithmetic\ sequence\ not\ exists.$
也就是說，我們要測試哪些 `i` (也就是這個等差數列有幾個數)可以讓我們得到整除的結果，來能得到整除的結果 `s` 。
根據以上，我們可以寫出以下的程式:
```c=
int consecutiveNumbersSum(int N)
{
if (N < 1)
return 0;
int ret = 1;//每個輸入一定可以寫成只含自己的數列
int x = N;
for (int i = 2; i < x; i++) {//因為前面已經把等差數列有一個數的情形考慮完了，所以i從2開始
x += 1-i;
if (x % i == 0)
ret++;
}
return ret;
}
```
- 做判斷是否存在元素個數為 i 的等差數列
```c=8
x += 1-i;
if (x % i == 0)
ret++;
```
- 然而程式中還有一個重點就是==for 迴圈到底要執行幾次==才結束，以這邊來說，是設定當 i 大於等於 x 時結束，什麼意思呢？
```c=7
for (int i = 2; i < x; i++)
```
- 回想我們剛剛的計算公式：
$s = \dfrac{N-(1+2+...+i-1)}{i}$
x 就相當於上述右式的分子，將 i > x 和 i = x 分開討論:
- 如果此次迴圈中 i 大於 x ，那麼在做此次判斷前的減法後(Line 8)，右式的分子一定會小於分母，也就是說不可能得到一個整數的 s ，之後也不可能得到整數 s。
- 如果此次迴圈中 i 等於 x ，那麼在做此次判斷前的減法後(Line 8)，右式的分子一定會等於1，也就是說不可能得到一個整數的 s ，下一個迴圈會落到 i > x 的情況。
- E.g. N = 15
|i| x before Line8| i < x | x after Line8|
| -------- | -------- | -------- | -------- |
|2| 15 | True |14|
|3| 14 |True |12|
|4| 12 | True |9|
|5| 9 | True |5|
|6| 5 | False ||
Sign in with Wallet
Connect another wallet