---
# System prepended metadata

title: 2020q3 Homework5 (quiz5)

---

# 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     ||

