# 2020q3 Homework5 (quiz5)
contributed by < `fwfly` >

## 測驗1

### 答案

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);
    if (od)
        result += divop(result, slots);
    return result;
}

### 想法
:::info
想看解法可以直接跳到 [程式說明](https://hackmd.io/QIY8ZRyQQN-SpKnb7sq-FQ?both#%E7%A8%8B%E5%BC%8F%E8%AA%AA%E6%98%8E)
:::

一開始是從答案開始了解題目，
後來找到了這篇，應該是以前同學做的說明而知道程式碼的運作
- https://hackmd.io/@billsun/B1gii716N

但是單純這樣並沒有辦法去解釋為什麼要 "除 2" 這樣的問題
所以又再去翻找了怎麼從整數轉換成浮點數．
從中知道了 IEEE754 浮點數表示法(怎麼用 binary 去表示服點數)
但是在 wiki 上有說
https://en.wikipedia.org/wiki/IEEE_754
:::info
base (also called radix) b, which is either 2 (binary) or 10 (decimal) in IEEE 754
:::

意思是浮點數的 base 可以為 2 跟為 10，
`原則上` c 語言應該是用 base 2 `感覺上` base 2 也比較符合 binary 的操作，不過這樣無法保證所以去翻了 C99 規格書．
在 [C99](http://www.dii.uchile.cl/~daespino/files/Iso_C_1999_definition.pdf) 規格書 (5.2.4.2.2, p25) 跟原始碼中可以得知，兩種 base 都是有實作

FLT_RADIX 2 # base 2
https://github.com/gcc-mirror/gcc/blob/master/gcc/ginclude/float.h#L33

DECIMAL_DIG 10 # base 10
https://github.com/gcc-mirror/gcc/blob/master/gcc/ginclude/float.h#L209

由於兩種都有實作，因此最簡單的方法是直接印出 binary．至少可以知道目前的 gcc 是跑哪一種 base.

static void printme(void *c, size_t n)
{
  unsigned char *t = c;
  if (c == NULL)
    return;
  while (n > 0) {
    int q;
    --n;
    for(q = 0x80; q; q >>= 1)
      printf("%x", !!(t[n] & q));
  }
  printf("\n");
}

void fpp(float f)
{
  printf("%f\n", f);
  printme(&f, sizeof f);
}

結果

3.600000 # input
01000000011001100110011001100110

在跟以下網站比對
- [IEEE 754 Converter](https://www.h-schmidt.net/FloatConverter/IEEE754.html) (這個網站是以 base 2 去跑浮點數)

可以知道在我的筆電上的 gcc 是 base 2 的浮點數．

**base 2 浮點數的 2 的除法跟乘法**
如果是 base 2 的浮點數，做 2/2的次方 的乘除法就會變得很簡單，只需要對 Exponent 的部分做加減法的運算就好．
不過這一部分依然無法確定是否 "除2" 是否會對浮點數運算有幫助

以下解釋都是以 base 2 浮點數為基礎

### 程式說明
這題是透過**分子分母共同除以 2** 去逼近答案．
比方說 1/8 跟 1/16
$$
\dfrac{1}{8} -> \dfrac{0.5}{4} -> \dfrac{0.25}{2} -> \dfrac{0.125}{1}(答案)
$$
$$
\dfrac{1}{16} -> \dfrac{0.5}{8}->\dfrac{0.25}{4}->\dfrac{0.125}{2}->\dfrac{0.625}{1}(答案)
$$
...以此類推
因此當分母為 **1** 的時候就可以得到答案

問題是如果分母不是 2 的倍數時要怎麼處理？
像是 1/3 或者 1/5 或者是 1/10 ?

### 處理不是 2 的倍數的分母

#### 處理奇數
變成偶數，
如何計算誤差值 ?

#### 處理非 2 的倍數的分母

### 精準度
什麼時候程式結束?

### 思考
1. 如果 `orig / 2` 本身就是 double 除以 int 為什麼還要特別寫一個 divop 去處理浮點數除法 ?
* 實驗: 拿一般浮點數除法跟 divop 去做比較 : 記憶體跟時間使用

### reference:

- https://hackmd.io/@billsun/B1gii716N
- https://www.h-schmidt.net/FloatConverter/IEEE754.html
- https://hackmd.io/@sysprog/c-floating-point
- [Convert a Number from Decimal to IEEE 754 Floating Point Representation](https://www.wikihow.com/Convert-a-Number-from-Decimal-to-IEEE-754-Floating-Point-Representation)

## 測驗3

根據題目提供的公式
$$
kx = N - \dfrac{(k - 1)k}{2}
$$
可以得到當以下式子為整數時可以找到一組連續數字表示 N
$$
x = \dfrac{N - \dfrac{(k - 1)k}{2}}{k}
$$
換成程式碼可以變成

if ((N - (k*(k-1)/2)) % k == 0)
   ret++;

剩下的就是 k 的範圍要怎麼跑
透過以下式子可以知道 k 的最大值
$$
k<√2N
$$
所以換成程式碼可以得到

   k < sqrt(2*N)

組合起來就會是以下這樣

    int ret = 1;
    double max = sqrt(2*N);
    for (int k = 2; k < max; k++ ){
        if ( (N - (k*(k-1)/2)) % k == 0)
           ret++;
    }
    return ret;

但是這樣子跟答案其實有很大的差異

int consecutiveNumbersSum(int N)
{
    if (N < 1)
        return 0;
    int ret = 1;

    int x = N;
    for (int k = 2; k < x; k++) {
    
        x += 1-k;
        
        if (x % k == 0)
            ret++;
    }
    return ret;
} 

To do .....