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

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

想法&解題

4 的倍數

• 本題題目要求為 alignment 4，也就是 INT_SIZE_OF(n) 得到的値要是 4 的倍數，並且這個數要大於等於 sizeof(n)

• 在 2 進為底下如果這個數為 4 的倍數，則它的最後兩位 bit 必為 0

  • 4₁₀ = 00000100₂
  • 8₁₀ = 00001000₂
  • 12₁₀ = 00001100₂
  • 16₁₀ = 00010000₂

• 透過 bitwise operation ,我們可以知道想要清除某個 bit 我們可以用

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

  的方式將某個 bit 的位元清空

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

  ​​​​unsigned char b &= ~(3);
  

  • 3₁₀ = 00000011₂
  • ~(3 ₁₀) = 11111100₂
  • 由於 (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₂ + 00000011₂ = 00000100₂
  • 00000010₂ + 00000011₂ = 00000101₂
  • 00000011₂ + 00000011₂ = 00000110₂
  • 00000100₂ + 00000011₂ = 00000111₂

  透過上面的觀察我們終於了解到加數字 3 到底是甚麼樣的操作，它實際的操作就是只要它加上的數字的二進位碼在最後兩位 bit 有 1，它就會讓這個數字二進位碼的第二位 bit 加 1，也就是加上 4₁₀。這樣確保在清掉最後兩位 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 累加方式求解 我們了解到為何會發生這樣的事，因為浮點數的讀取的方式跟我們一般的直觀的二進位系統不太一樣，它的數值讀取方式為底下所示
  • 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