# 2019q3 Homework1(review)
contributed by < `YenHengLin` >
>作業系統:Ubuntu 18.04 LTS
>作業系統類型：64 位元
## 課前測驗第二題
### 問題

考慮以下 C 程式可取得以 `sizeof(int)` 為 alignment 基礎的整數空間，也就是說，當 `sizeof(int)` 為 `4` 的時候:
* 給定 `char arr[13];`，`INT_SIZE_OF(arr)` 要得到 `16`;
* 給定 `short int s;`，`INT_SIZE_OF(s)` 要得到 `4`

#include <stdint.h>
#define INT_SIZE_OF(n) \
    ((sizeof(n) + sizeof(int) + X) & ~(sizeof(int) + Y))

* 請求出 X 、 Y
* 參考資訊: [Memory access and alignment](https://lwn.net/Articles/260832/)

:::success
延伸題目: 解釋運作原理並在 GitHub 找出實際應用的程式碼
:::

### 想法&解題

#### 4 的倍數

* 本題題目要求為 alignment 4，也就是 INT_SIZE_OF(n) 得到的値要是 4 的倍數，並且這個數要大於等於 sizeof(n)
* 在 2 進為底下如果這個數為 4 的倍數，則它的最後兩位 bit 必為 0
* 4~10~ = 00000100~2~
* 8~10~ = 00001000~2~
* 12~10~ = 00001100~2~
* 16~10~ = 00010000~2~
* 透過 [bitwise operation](https://hackmd.io/@sysprog/By0MltO_m?type=view) ,我們可以知道想要清除某個 bit 我們可以用

    unsigned char b &= ~(1 << n);

的方式將某個 bit 的位元清空
* 將以上的概念整合起來我們就可以知道，為了要得到 4 的倍數我們所要做的就是讓這個數的最後兩位 bit 要是 0，也就是清空最後兩位 bit 的値，寫成 bitwise operation 為

    unsigned char b &= ~(3);

* 3~10~ = 00000011~2~
* ~(3 ~10~) = 11111100~2~
* 由於 ==(0 or 1) & 0=0==，==(0 or 1) & 1 =自己==，所以我們可以透過 ==&=~(3)==，將最後兩位 bit 清空，而不動到其它位的 bit

所以我們最後推得 ==Y = -1==
#### 大於等於 sizeof(n)
* 4 的倍數可以透過清空 bit 解決這個問題，那還有一個問題沒解決，也就是我們要得到的値要大於等於 sizeof(n)，這一段比較難思考，所以我一開始是先用列舉法將 sizeof(n)= 1, 2, 3, 4
* 找出最小且大於等於 1 2 3 4 的數字會發現數字 4 會滿足上述列舉的 4 個數字。將最小的數字 1 加上 3 在去掉這個數的最後 2 位 bit，就會發現值為 4
* 將 2 3 4 數字都套入跟 1 一樣的操作 ==f(x)=(x+3)&~(3)==，將會發現都得到一樣的數字 4，這樣我們可以假定為了要得到大於等於 sizeof(n)的數，必須要加 3
* ==加上 3== 為我們的猜測，所以我們來看看加數字 3 在二進位底下到底是在做甚麼事
* 00000001~2~ + 00000011~2~ = 00000100~2~
* 00000010~2~ + 00000011~2~ = 00000101~2~
* 00000011~2~ + 00000011~2~ = 00000110~2~
* 00000100~2~ + 00000011~2~ = 00000111~2~

透過上面的觀察我們終於了解到加數字 3 到底是甚麼樣的操作，它實際的操作就是只要它加上的數字的二進位碼在最後兩位 bit 有 1，它就會讓這個數字二進位碼的第二位 bit 加 1，也就是加上 4~10~。這樣確保在清掉最後兩位 bit 時，得到的值既是 4 的倍數又不會小於 sizeof(n)，而已經是 4 的倍數的值由於最後兩位 bit 是 0 所以加 3 後不會改變這個數的第二位 bit，當然清完後面兩位 bit 後就等於原本的值。所以最後我們可以確認說 ==X的值為 -1==

## 課程簡介和注意須知 page 9~10
### code

#include <stdio.h>
int main() {
    float sum = 0.0f;
    for (int i = 0; i < 10000; i++) sum += i + 1;
    printf("Sum: %f\n", sum);
    return 0;
}

#### 想法
* 依照小學學的高斯求和公式得到 (1+10000)*10000/2=50005000 ，然而實際透過電腦跑就會發現得到的結果為 `Sum: 50002896.000000`，跟我們所想的不一樣
* 參考 [浮點數 float 累加方式求解](https://www.itread01.com/content/1501405444.html?utm_source=https://www.itread01.com/content/1501405444.html) 我們了解到為何會發生這樣的事，因為浮點數的讀取的方式跟我們一般的直觀的二進位系統不太一樣，它的數值讀取方式為底下所示
* 1 bit sign
* 8 bits exponent
* 23 bits fraction
* 圖示:
* 而這樣的讀取方式使得 float 值的加減法要進行底下的操作
* 兩數的 exponent 值必須先對齊，比較 exponent 大小，小的向大的對齊
* 如果 exponent 有變動，那 fraction 必須跟著改變，以符合原來的數值
* 改動完後的 fraction 做定點相加(減)
* 將相加(減)的結果規則化，以符合 float 的儲存方式
* fraction 右移時丟式的數值位做 round
* 判斷結果是否溢出
* 由於 exponent 必須要對齊的緣故，所以我們很可能會面臨一種情況，那就是數值相差很大的數在做相加(減)時由於小的數字要提升 exponent 以符合大的數字的 exponent ，而把 fraction 右移，結果就是失去了尾數部份的值，例如底下的 code

    #include <stdio.h>
    int main() {
        float sum = 0;
        sum+=1;
        sum+=50000000;
        printf("Sum: %f\n", sum);
        return 0;
    }

照理來說執行的結果應該要為 50000001，然而實際的程式碼結果為 `Sum: 50000000.000000`，沒錯 1 的值就在 exponent 對齊的時候被丟棄了，現在我們可以理解到為何浮點數相加會產生誤差，因為我們在做兩個相差大的數字的加法。

### 改進辦法(一)
* 將一層 for 迴圈改成兩層 for 迴圈，內層先計算得到比較小的總和，再將這些總和加總起來
* code

#include <stdio.h>
int main()
{
    float sum = 0.0f;
    float temp = 0.0f;
    for (int i = 0; i < 100; i++)
    {
        temp = 0.0f;
        for (int j = i * 100; j < 100 * (i + 1); j++)
        {
            temp += 1 + j;
        }
        sum += temp;
    }
    printf("Sum: %f\n", sum);
    return 0;
}

得到輸出結果為 `Sum: 50004968.000000` ，說明準確度有明顯的上升，然而還是錯的答案，代表在做加法時兩數的差還是有點大，所以我作了以下的修正
* code 修正版

#include <stdio.h>
int main()
{
    float sum = 0.0f;
    float tempa = 0.0f;
    float tempb = 0.0f;
    for (int i = 0; i < 10; i++)
    {
        tempb = 0.0f;
        for (int j = i * 10; j < (i + 1) * 10; j++)
        {
            tempa = 0.0f;
            for (int k = j * 100; k < 100 * (j + 1); k++)
            {
                tempa += k + 1;
            }
            tempb += tempa;
        }
        sum += tempb;
    }
    printf("Sum: %f\n", sum);
    return 0;
}

讓兩數相加時的差更少，終於得到對的輸出 `Sum: 50005000.000000`，然而這樣做有個缺點，就是邊界的判斷變得複雜，且不適用所有的情況，所以我們開始來思考有沒有其它更直觀的方式，來修正 float 所造成的誤差。

### 改進辦法(二)-[Kahan's Summation algorithm](https://en.wikipedia.org/wiki/Kahan_summation_algorithm)