2020q3 Homework6 (quiz6)

contributed by < sammer1107 >

tags: `進階電腦系統理論與實作`

測驗 1





















float fp32tobf16(float x) {
    float y = x;
    int *py = (int *) &y;
    unsigned int exp, man;
    exp = *py & 0x7F800000u;
    man = *py & 0x007FFFFFu;
    if (!exp && !man) /* zero */           
        return x;
    if (exp == 0x7F800000u) /* infinity or NaN */
        return x;

    /* Normalized number. round to nearest */
    float r = x;
    int *pr = (int *) &r;
    *pr &= 0xff800000;
    r /= 256;
    y = x + r;

    *py &= 0xffff0000;
    return y;
}

3: 在 c 語言中，其實是不能夠對 floating point 作bitwise 運算的。所以我們必須先把他強制轉型成 int 。才能直接對浮點數作位元操作。
5~10：這裡我們分別把 exponent 與 mantissa 取出來，來判斷是不是特別的情況
- 如果都為0，那麼數值肯定是
  $\pm 0$ ，這種情況下最低的 16 位已經沒用到，所以可以直結回傳。
- 如果 exp 為全 1，則為 infinity(man == 0) 或 NaN(man != 0)。infinity 的話也可以直接回傳。但 NaN 的部份應該更加小心，因為 mantissa 只要不為 0 就算 NaN
  - 如果要縮成 16 bit，應該也要做 & 0xffff0000 來去除低位的 bit 才對。
  - 但得要確保 bfloat16 的 mantissa 範圍內仍有 1 才行，否則單純去除低位 bit 有可能會讓 NaN 變成 bfloat16 的 infinity
    故這部份應該改成：
```
if (exp == 0x7F800000u) {  /* infinity or NaN */
    // make sure the mantissa is non-zero if NaN
    *py |= ((man != 0) << 16);
    *py &= 0xFFFF0000;
    return y;
}
```
12~17: 這一部份要剩下 normalized 與 denormalized number 要處理
- 做完 15 行後相當於把原本 x 的 mantissa 歸 0 變成 r。e.g.
  $x = 2^{23} \cdot 1.10011011 . . . \to r = 2^{23} \cdot 1.00000000 . . .$
- 再來除以
  $256 = 2^{8}$ 次方的動作是為了作 rounding，如果原本 mantissa 中的第 16 bit 為 1 (對應 0x000080000 這個位置，也就是 bfloat16 範圍外的第一個 bit)，加上 r 之後就會進位。要注意這裡 r 是浮點數型態，所以除以 256 不是單純向右移，而是把 exponent 減 8 。 e.g.
  
  $\begin{aligned} r / 256 & = 2^{23 - 8} = 2^{15} \\ x + r / 256 & = 2^{23} \cdot (1.10011011 + 0.00000001) \\ = 2^{23} \cdot 1.10011100 \end{aligned}$
  如此完成進位。
- denormalized 所獲得的 r 為 0，所以不會變化，相當於直接 truncate。
19~20：這裡再把低位的 16 個 bit 去掉就行了。

測驗 2



#define NEXT_START_INDEX(BUF) \
    (((BUF)->start != (BUF)->size) ? ((BUF)->start + RB1) : 0)
#define NEXT_END_INDEX(BUF) (((BUF)->end != (BUF)->size) ? ((BUF)->end + RB2) : 0)

此 ring buffer 的實作是利用一個大小 size+1 的 array。當 ring buffer 為空時，end 與 start 指向同一個地方。每當放入新元素，就是放在 end 的位置，然後移動 end 到下一個位置。讀取的時候則是從 start 讀取，然後移動 start ㄉ當滿了的時候則是 end 在 start前一個位置，這時 end 沒放東西，所以最大只能放 size 個元素。
NEXT_START_INDEX 的功用在於找到 start 的下一個位置，這其實就是 start+1，除了當 start在最後一格時，要繞回來 0 。NEXT_END_INDEX 同理。所以兩個答案都為 1。

do {…} while(0)

當我們要寫一個由多個 statement 構成的 macro function 時，我們可以利用 do {...} while(0) 來把這些 statement 包起來，來讓整個東西變成一個 regular statement。
在 c 的標準中， do statement while (expression); 放在 iteration statement 的定義當中，這個東西特別的地方他可以夾帶一個 compound statement ({...})而且他是以 ; 作為結尾，這讓他跟 expression statement 很類似，而一般的函式呼叫就是屬於 expression statement。
c 的標準中似乎沒有 regular statement 的定義，但我想 stackoverflow 的回答是要表達上述的意思。

TODO: 用 dangling else 的處置來回覆本題
jserv

測驗 3

這題為一個 singly-linked list 加上對應的 insertion sort 的實作。

先看 llist 與 cons(x,y) 的定義：
```
#define cons(x, y) (struct llist[]){{y, x}}
        
struct llist {
    int val;
    struct llist *next;
};
```
首先這題用到 compound literal 的技巧，根據 c standard:

A postfix expression that consists of a parenthesized type name followed by a brace-
enclosed list of initializers is a compound literal. It provides an unnamed object whose value is given by the initializer list.

也就是長這樣的東西：( type-name ) { initializer-list }
- 在這裡 type-name 就是 struct llist[]，initializer-list 就是 {y,x}，用來初始化這個 array of struct llist 的第0個元素(其中 y 用來初始化 val，x 初始化 next )，而整個 array 也就只有一個元素。
- 整個 cons(x,y) 會成為一個 lvalue，array 會被轉成 pointer，可以再被傳入下一層 cons 作為初始值。
- 弄懂這個原理後，其實也可以把他寫成這樣。雖然比較醜，但是可以確認我對這東西的理解是正確的：
```
#define cons(x, y) (struct llist*){&(struct llist){y, x}}
```
  我們利用 (struct llist){y, x} 來創造一個 struct llist，對他取址，再用這個地址初始化一個 struct llist*。如此同樣可以達成一樣的效果。

void sort(struct llist **head)










void sort(struct llist **head)
{
    struct llist *sorted = NULL;
    for (struct llist *current = *head; current;) {
        struct llist *next = current->next;
        sorted_insert(&sorted, current);
        current = next;
    }
    *head = sorted;
}

這裡為 insertion sort 的主體，迴圈做的事就是逐點走訪 linked list，把每個節點利用 sorted_insert() 來把這個節點加到已排序好的 list。

void sorted_insert(struct llist **head, struct llist *node)













void sorted_insert(struct llist **head, struct llist *node)
{
    if (!*head || (*head)->val >= node->val) {
        node->next = *head;
        *head = node;	
        return;
    }
    struct llist *current = *head;
    while (current->next && current->next->val < node->val)
        current = current->next;
    node->next = current->next;
    current->next = node;
}

第 3 行檢查新的節點是不是最小的，如果是就把頭換成新的節點。所以答案如上。
8~12：如果不是，就逐漸走訪排序好的 list，直到走到合適的地方再插入。

測驗 4

原理

這題的原理與之前 quiz2-測驗6 的概念有點類似。一樣都是分開數每個 bit 出現的次數。
陣列有
$n$ 個數值，數值的範圍是
$1, 2, \dots, n - 1$ ，只有
$n - 1$ 種，所以根據鴿籠原理一定會有至少一個數字重複，而根據題目，只會有一個數字重複，且出現次數不定。
我們先看一個例子。假設
$n = 5$ ，且每個數字都會出現，也就是重複的數字只會出現兩次的情況。

數字 binary

1 001

2 010

3 011

4 100

各位置 1 出現的次數 122
- 現在如果我們選擇讓 1 重複，則最後的總和會變成 123，藉由比對
  $2 < 3$ 可以輕易得知多出來的是 1。
- 同理若是其他數字重複，我們只要看哪個位置比起全部只出現一次的總和多，就知道多出來的那個數字的二進位表示法。
假如並沒有每個數字都出現過呢？
- 這種情況下，重複的數字可能出現了更多次。延續上面的例子，假如 1 重複了兩次，我們可以知道是答案是 1 。但當 1 重複了 3 次，我們要選一個數字被 1 取代，這個數字將不會出現在陣列當中。
- 若我們選擇讓 2 被 1 取代，則總和變為 114。選擇 3 被取代，則結果變為 113。
- 我們可以整理出一個規律：當重複的數字重複更多次時，在這個數字為 1 的位置，總和只可能會增加，不會變少。在這個數字為 0 的位置，總和只會減少不會增加。 e.g. 我們讓 1 重複更多次時，最低位的總和只會變更多或是不變，不管怎麼樣都會大於原本的
  $2$ 。其他兩個位置的總和只會減少，不管怎麼樣都不會大於原本的總和。

數字	binary
1	001
2	010
3	011
4	100
各位置 1 出現的次數	122

程式碼解說


















int findDuplicate(int *nums, int numsSize)
{
    int res = 0;
    const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);
    for (size_t i = 0; i < log_2; i++) {
        int bit = 1 << i;
        int c1 = 0, c2 = 0;
        for (size_t k = 0; k < numsSize; k++) {
            if (k & bit)
                ++c1;
            if (nums[k] & bit)
                ++c2;
        }
        if (c1 < c2)
            res += bit;
    }
    return res;
}

4: 這裡我們根據 n 計算最多需要計算多少 bit。只要在 n 的 leading zero 區域，更小的數字都不可能會用到這些 bit。但我們實際會出現的數字範圍只有到
$n - 1$ ，所以這裡可以這樣改成 numSize-1：
```
const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize-1);
```
外層迴圈：這裡我們走過每個需要看的 bit 位置。
內能迴圈：這裡我們走過
$0 \sim n - 1$ ，一邊計算
$1 \sim n - 1$ 當中這個 bit 1 出現的次數 c1，一邊計算陣列中的數字裡 1 出現的次數 c2。最後比較 c1 < c2 就知道重複的數字在這個位置上是不是 1 了。如果是，就在 res 把對應的 bit 設為 1。
走完所有 bit 位置後，就知道重複的數字長怎樣了。

實作改善

分析

現有實作的缺點就是一定得走訪整個 nums
$\log_{2} (n - 1)$ 次，時間複雜度為
$O (n \log n)$ ，換來的則是
$O (1)$ 的空間複雜度。
Leetcode 上最快的實作是直接用一個長度
$n$ 的陣列紀錄數字是否出現過，如此通常不必走完整個陣列就完成任務了。缺點是
$O (n)$ 的儲存空間。

改善

現有的實作可透過增加一個長度
$\log_{2} (n)$ 的陣列來累計每個位置的 c2，如此只要完整走訪整個陣列一次，在每個數字則利用 gcc extension 加速。如此用
$O (\log n)$ 的儲存空間換取到更短的時間。

另外一點是，c1 事實上可以直接計算而不必實際走訪

1 \sim n - 1

來累計。觀察以下二進位表，就可以發現規律。

Decimal	Binary
0	000
1	001
2	010
3	011
4	100
5	101
6	110
7	111
首先 $0 \sim n - 1$ 和 $1 \sim n - 1$ 的累計是一樣的。再來第 0 個 bit 是 2 個數字作為一個周期變化，每兩個數字中有 1 個為 1 。第 1 個 bit 則是 4 個數字成為一個周期，每 4 個數字中有 2 個為 1 。
如此根據 n ，我們可以計算出 bit $i$ 的累積結果：
\begin{align}
\floor{\frac{n}{2^{i+1}}} 2^i + \max(n\bmod{2^{i+1}},2i)-2^i
\end{align}

Code























int findDuplicate(int *nums, int n)
{
    int res = 0;
    const size_t log_2 = 8 * sizeof(int) - __builtin_clz(n-1);
    int *c2 = calloc(log_2, sizeof(int));

    for (size_t i = 0; i < n; i++) {
        while(nums[i]) {
            ++c2[__builtin_ctz(nums[i])];
            nums[i] &= nums[i] - 1;
        }
    }

    for (size_t i = 0; i < log_2; i++) {
        int c1, r, bit = 1 << i;
        r = n & bit ? n & (bit-1): 0;
        c1 = ((n >> (i+1)) << i) + r;
        res |= (c1 < c2[i]) << i;
    }

    free(c2);
    return res;
}

7~12: 這裡走訪整個 nums 來統計各 bit 的累計次數。其中用到與 quiz3-Bitmap 一樣的技巧，利用 ctz 來避免檢查每一個 bit 位置。
14~19：這裡檢查每一個 bit 位置，直接計算 c1 後，比較 c1 與 c2 來設定 res

比較結果
- 在 LeetCode 實測過後偶爾可以達到 4ms，原本則都是 8ms。
- 以下為在我電腦上實測的結果，x 軸為
  $n$ ，y 軸為執行時間。

測試程式

這裡測資的產生並不夠隨機，所以比較結果可能不公平，畢竟新方法會受到 set bit 數量而影響速度。
但平均來講新方法還是會比較快才對。












































































#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define MAX_N 20000

int findDuplicate_improve(int *nums, int n)
{
    int res = 0;
    const size_t log_2 = 8 * sizeof(int) - __builtin_clz(n-1);
    int *c2 = calloc(log_2, sizeof(int));

    for (size_t i = 0; i < n; i++) {
        while(nums[i]) {
            ++c2[__builtin_ctz(nums[i])];
            nums[i] &= nums[i] - 1;
        }
    }

    for (size_t i = 0; i < log_2; i++) {
        int c1, r, bit = 1 << i;
        r = n & bit ? n & (bit-1): 0;
        c1 = ((n >> (i+1)) << i) + r;
        res |= (c1 < c2[i]) << i;
    }

    free(c2);
    return res;
}


int findDuplicate(int *nums, int numsSize)
{
    int res = 0;
    const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);
    for (size_t i = 0; i < log_2; i++) {
        int bit = 1 << i;
        int c1 = 0, c2 = 0;
        for (size_t k = 0; k < numsSize; k++) {
            if (k & bit)
                ++c1;
            if (nums[k] & bit)
                ++c2;
        }
        if (c1 < c2)
            res += bit;
    }
    return res;
}

int main(void)
{
    int *nums = malloc(sizeof(int) * MAX_N);
    nums[0] = 1;
    double time1=0, time2=0;
    for (int i=2; i < MAX_N; ++i) {
        nums[i-1] = i;
        nums[i] = 1;
        clock_t t1,t2; 

        t1 = clock(); 
        findDuplicate(nums, i + 1); 
        time1 += t1 = clock() - t1; 

        t2 = clock();
        findDuplicate_improve(nums, i + 1);
        time2 += t2 = clock() - t2;

        printf("%d, %.8f, %.8f\n", i + 1,
            (double)t1 / CLOCKS_PER_SEC, (double)t2 / CLOCKS_PER_SEC); // in seconds 
    }
    printf("%.8f, %.8f\n", time1 / CLOCKS_PER_SEC, time2 / CLOCKS_PER_SEC); // in seconds 
    return 0;
}

Jim Huang

2020/10/22 09:44:56

標註你的 GitHub 帳號，即加上 contributed by 的資訊 (Edited)

Tim096

2020/10/23 03:56:37

但 NaN 的部份應該更加小心，因為 mantissa 只要不為 0 就算 NaN

同學您這邊是不是想錯了呢 ? 我想老師這邊的意思應該是如果原本 infinity 就直接回傳原本的 infinity，反之若原本是 NaN 就回傳 NaN 呢 ? (因為原本就會知道它是屬於 infinity 或是 NaN) 還是說我有其他想法沒注意到呢 ? 謝謝 (Edited)

Yu Jen Lin

2020/10/26 07:06:33

我不確定老師原本的意思是啥，但因為BFloat16 也有定義 Inf 與 NaN，所以我這裡是假設 NaN 就要轉成 Bfloat16 的 NaN，也就是底下 16 bit 還是要 truncate。

2020q3 Homework6 (quiz6)

tags: 進階電腦系統理論與實作

測驗 1

測驗 2

do {…} while(0)

測驗 3

測驗 4

原理

程式碼解說

實作改善

分析

改善

Read more

2020q3 Homework1 (quiz1)

2020q3 Homework3 (quiz3)

2020q3 Homework6 (kcalc)

2020q3 Homework5 (quiz5)

tags: `進階電腦系統理論與實作`