2020q3 Homework2 (quiz2)

contributed by < haoyu0970624763 >

1. ASCII 編碼判斷

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>

bool is_ascii(const char str[], size_t size)
{
    if (size == 0)
        return false;
    int i = 0;
    while ((i + 8) <= size) {
        uint64_t payload;
        memcpy(&payload, str + i, 8);
        if (payload & 0x8080808080808080)
            return false;
        i += 8;
    }
    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
    return true;
}

程式解說

對於單個字元 1 byte = 8 bits , ASCII碼為0-126

若此字元和 0x80 做＆不等於0 則表示他從左邊數過來第二個bit != 0 也就不為ASCII碼

同樣的邏輯推廣到 8 個字元即是答案

memcpy 的使用不但是用來得到 64 bits 的 payload，memcpy會去檢查記憶體位址是否有

alignment ，可以避免因為對記憶體的 unaligned memory access 產生錯誤。

延伸問題二

































#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>

#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)

bool is_alphabet(const char str[], size_t size)
{
    if (size == 0)
        return false;
    int i = 0;
    while ((i + 8) <= size) {
        uint64_t payload;
        memcpy(&payload, str + i, 8); 
        uint64_t A = payload + PACKED_BYTE(128 - 'A' );  
        uint64_t Z = payload + PACKED_BYTE(128 - 'Z' - 1); 
        uint64_t a = payload + PACKED_BYTE(128 - 'a' );  
        uint64_t z = payload + PACKED_BYTE(128 - 'z' - 1); 
        uint64_t lowerMask = (a ^ z) & PACKED_BYTE(0x80);
        uint64_t upperMask = (A ^ Z) & PACKED_BYTE(0x80);        
        if (( lowerMask | upperMask ) ^ PACKED_BYTE(0x80)){
            return false;
        }   
        i += 8;
    }   
    while (i < size) {
        if ( (str[i] < 65 || (str[i] > 90 && str[i] < 97) || str[i] > 122))
            return false;
        i++;
    }   
    return true;
}

程式解說

一開始想不到要怎麼寫參考了別人一下也發現看不太懂

看不懂就說看不懂，不要說模糊地「不太懂」。如果你認定其他同學的共筆寫不好，那就留訊息指出其不足之處。
再者，你的標點符號呢？

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

但是把全部測驗都解釋整理一次之後就是把測驗 5 的思考迴路跟解法搬過來這邊解

2. 16進位字元轉換






uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & 0x40;
    const uint8_t shift = (letter >> 3) | (letter >> 6);
    return (in + shift) & 0xf;
}

程式解說

我們可以觀察回傳值 (in + shift) & 0xf 僅要後面四碼而已

而字元'0'到'9' 的僅取其後四個bit轉換過來即為答案

至於字元'a'到'f' 的其後四個bit轉換過來為 1-7 只要都再+9 即為對應之答案

我們先用 mask=0x40 如果你是字母（大小寫都可）letter都會等於 0x40 如果是數字 letter=0x00

而shift則表示如果你是字母 shift=0x09 數字的話則為0

接著就可求到答案了

3.快速除法









const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF) / (D) + 1))

/* compute (n mod d) given precomputed M */
uint32_t quickmod(uint32_t n)
{   uint64_t quotient = ((__uint128_t) M * n) >> 64;
    return n - quotient * D;
}

程式原理

n \mod D = n - (n / D) \times D

也就是說 n - quotient * D 的 quotient 就是 n / D 的整數部份。

從題目裡的提示

\frac{n}{d} = n \times (\frac{2^{N} / d}{2^{N}})

quotient = ((__uint128_t) M * n) >> 64 右移 64 bits 即為

\frac{1}{2^{N}}

，所以 N = 64。

但是

M ＝ (2^{64} / D)

跟

(2^{64} - 1) / D + 1

略為不同參考Rsysz 發現兩者算出來的答案是一樣的所以 M=0xFFFFFFFFFFFFFFFF

4.倍數判斷




bool divisible(uint32_t n)
{
    return n * M <= M-1;
}

程式原理

延伸上一題的觀念

因為D=3 令 n=3k,3k+1,3k+2 (k為非負整數)

其中 3M=0x10000000000000002 已經overflow 所以會把 3M視為3M=0x0000000000000002

所以 case1:

n * M = 3 k M = 2 k

case2 :

n * M = 3 k M + M = 2 k + M

case3 :

n * M = 3 k M + 2 M = 2 k + 2 M

所以答案 C,D皆符合

疑問：有點像是用答案硬推理不知道為什麼當初會這樣構想程式

工程人員說話要精準，避免說「有點像是」，後者是文組^TM用語

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

5. 字串大寫轉換小寫

#include <ctype.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)


void strlower(char *s, size_t n);
/* vectorized implementation for in-place strlower */
void strlower_vector(char *s, size_t n);


int main()
{
    /* quote from https://www.gutenberg.org/files/74/74-h/74-h.htm */
    char *str =
        "This eBook is for the use of anyone anywhere at no cost and with \
almost no restrictions whatsoever.  You may copy it, give it away or \
re-use it under the terms of the Project Gutenberg License included \
with this eBook or online at www.gutenberg.net";
    int n = strlen(str);
    strlower_vector(str, n);
    puts(str);
}
void strlower(char *s, size_t n)
{
    for (size_t j = 0; j < n; j++) {
        if (s[j] >= 'A' && s[j] <= 'Z')
            s[j] ^= 1 << 5;
        else if ((unsigned) s[j] >= '\x7f') /* extended ASCII */
            s[j] = tolower(s[j]);
    }
}

void strlower_vector(char *s, size_t n)
{
    size_t k = n / 8;
    for (size_t i = 0; i < k; i++, s += 8) {
        uint64_t *chunk = (uint64_t *) s;
        if ((*chunk & PACKED_BYTE(0x80)) == 0) { /* is ASCII? */
            uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + 0); 
            uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + (-1));
            uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x80)) >> 2;
            *chunk ^= mask;
        } else
            strlower(s, 8);
    }
    
    k = n % 8;
    if (k)
        strlower(s, k);
}

程式原理

PACKED_BYTE(b) 的作用是取出 b 的後 8 個位元(假設是 0x12)，並且變成 0x1212121212121212

接著檢查這個字元是不是 ASCII 編碼（運用到題一）

如果 *chunk + PACKED_BYTE(128 - 'A' + 0) >= 128 表示 chunk的ASCII 編碼大於等於'A'

如果 *chunk + PACKED_BYTE(128 - 'Z' -1) < 128表示 chunk的ASCII 編碼小於等於'Z'

把 A 跟 Z 做 Xor 如果等於 10000000 表示 chunk是介於 'A' 到 'Z' 之間

則 mask=00100000=' '

若大寫字母跟' ' Xor 則會跑出小寫字母

如果chunk不介於'A'到 'Z' 之間同時小於128 或是同時大於128

則 mask=00000000

任何東西跟0 Xor 都等於自己

6. 單次數尋找

int singleNumber(int *nums, int numsSize)
{
    int lower = 0, higher = 0;
    for (int i = 0; i < numsSize; i++) {
        lower ^= nums[i];
        lower &= ~higher;
        higher ^= nums[i];
        higher &=  ~lower;
    }
    return lower;
}

程式原理

lower 是紀錄哪個位置的bit出現數為奇數次出現奇數次的=1

higher 是紀錄哪個位置的bit出現數為偶數次出現偶數次的=1

實做邏輯

lower ^= nums[i] 會先把num[i]的bit 出現奇數次的bit紀錄住

lower &= ~higher 會把已經出現過偶數次的bit扣掉

（當有一個bit出現第三次 lower會紀錄住但是這個其實是不需要的會透過上一個迴圈的higher把第三次出現的的消掉因為我們只要出現一次的bit）

higher ^= nums[i] 會先把num[i]的bit 奇數次的bit的紀錄住

higher &= ~lower 會把已經出現過奇數次的bit扣掉

(當只出現一次 lower會記住 higher也會記住但會被扣掉而出現第二次時 lower會消掉
higher會記住但不會被扣掉也就是說higher會紀錄出現偶數次的bit)

注意筆記書寫規範，中英文字元用一個空白區隔，從小處做起

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

新增: 第2題 16進位字串轉換


































uint64_t HexToDigit(char* in) {

    char *tmp_ptr=in;
    char *reverse;
    uint64_t payload = 0, value = 0;
    if (in[0] == '0' && in[1] == 'x')
        tmp_ptr=&in[2];

    #if __BYTE_ORDER == __BIG_ENDIAN
        reverse=tmp_ptr;
    #else
        memset(reverse,'\0',strlen(tmp_ptr)+1);
        for (int i = 0; i < strlen(tmp_ptr); i++)
        {
            reverse[i]=tmp_ptr[strlen(tmp_ptr)-1-i];
        }

    #endif
    
    memcpy(&payload, reverse , sizeof(char)*strlen(tmp_ptr));
    
    uint64_t letter = payload & 0x4040404040404040;
    uint64_t shift = (letter >> 3) | (letter >> 6);
    uint64_t tmp=(payload + shift) & 0x0F0F0F0F0F0F0F0F;
    int i=strlen(tmp_ptr);
    
    for( int i=strlen(tmp_ptr); i!=0 ; i--){
        value= value << 4;        
        value |= ((tmp >> (i-1)*8) & 0x0F);
    }
    return value;
}

根據電腦的endian架構去決定input的字串要不要反過來

把 input 的字串反過來是因為電腦架構還有 uint64_t 的 endian 是不一樣的，會發現這個

是因為我在測試 0x12 的時候，答案一直都不是我預期的，反而是 0x21 的答案，所以就上

stackoverflow 尋找才發現是 endian 的問題

邏輯:

strlen(tmp_ptr) 表示需要轉換的長度
用 tmp 存著所有轉換完的 input ，每 8bits 表示一個數字

從轉換完的輸入最左邊 8bits 開始依序到最右邊 8bits ，將 8bits 右移到最右邊8 個 bits 並且跟 value 做 AND 接著再把 value 左移4個bits(因為是16進位)
把第8-15bits 右移到最右邊8 個 bits 並且跟 value 做 AND …依此類推

tmp >> (i-1)*8 控制是哪一組 8bits 右移到最右邊
＆ 0x0F 只需要最右邊 4bits

新增: 第3題快速除法（jemelloc原理）

n

為被除數,

q

為商,

d

為除數

數學式子從Rsysz參考，但是他的

r = (- 2)^{k} m o d d

應為筆誤或是錯誤

r 表示

2^{k} m o d d

(也就是餘數)

假設

n = q \times d

，已知 n , d 求 q

q = n / d

= ⌊ ⌈ \frac{2^{k}}{d} ⌉ \times \frac{n}{2^{k}} ⌋ = ⌊ \frac{2^{k} + r}{d} \times \frac{n}{2^{k}} ⌋ ， k 為 任 意 整 數 ， 而 r = - (2)^{k} m o d d

將 ⌊ \frac{2^{k} + r}{d} \times \frac{n}{2^{k}} ⌋ 展 開 為 ⌊ \frac{2^{k}}{d} \times \frac{n}{2^{k}} + \frac{r}{d} \times \frac{n}{2^{k}} ⌋ = ⌊ \frac{n}{d} + \frac{r}{d} \times \frac{n}{2^{k}} ⌋

因 假 設 n / d 為 整 除 ， 所 以 n / d 的 小 數 部 分 為 0 ， 因 此 式 子 可 以 化 簡 為 \frac{n}{d} + ⌊ \frac{r}{d} \times \frac{n}{2^{k}} ⌋

也就是當

\frac{r}{d} \times \frac{n}{2^{k}} < 1

，

n / d = ⌊ ⌈ \frac{2^{k}}{d} ⌉ \times \frac{n}{2^{k}} ⌋

就會成立

因

r

是

\frac{2^{k}}{d}

的餘數，因此 r < d 且

r / d < 1

總是成立，所以只需滿足

\frac{n}{2^{k}} < 1

又

n

為32bits的數，最大值為

2^{32} - 1

，因此可以令 k = 32(k之最大值)來確保

\frac{n}{2^{k}} < 1

，而這也是為什麼jemalloc bound 數值範圍在

2^{32}

之間。

code 連結

div_info->magic =

⌈ \frac{2^{k}}{d} ⌉

為何要取上高斯??

用例子說明：

12 \times \frac{2^{3}}{6} >> 3

若是

\frac{2^{3}}{6}

四捨五入或取下高斯，答案皆為1，取上高斯答案則為 6（所以要取上高斯）

理論上最優的算法當然是

12 \times 2^{3} / 6 >> 3

但程式語言無法做到這件事。

取下高斯或是捨去會有部份值被捨去，會造成相乘出來的結果變小，進而影響結果。

取上高斯或是進位，會造成相乘出來的結果變大，進而影響結果，但後來有右移所以把答案調回來。

新增: 快速除法跟一般除法之間的效能比較:

最一開始的實驗: 將快速除法跟除法分成兩個執行檔，除數為亂數設定，被除數也是亂數設定。

兩個檔案的亂數種子是設定為一樣的，所以兩個檔案的除數跟被除數都是一樣的，皆進行一億次運算

想像中的結果，quickdiv 應該快於 div 的運算，然而結果卻不一樣。

div code 連結

quickdiv code 連結

從上圖可以發現，一般的除法會略快於快速除法

為什麼會導致這樣的結果呢?

1. 實驗設計錯誤
2. 在實做上 quickdiv真的慢於div
3. 實驗測資導致的結果

針對實驗設計錯誤的問題，我仿照`RinHizakura`的實驗方式進行實驗

底下的 code 為 RinHizakura 的實驗基礎設計

static uint64_t MAX = ((uint64_t)(1) << 32) - 1;
int main()
{
    struct timespec tt1, tt2;
    clock_gettime(CLOCK_MONOTONIC, &tt1);
    for (uint64_t i = 2; i < 5000; i++) {
        div_info_t DIV;
        div_init(&DIV, i); 

        uint64_t num = rand() % MAX;
        clock_gettime(CLOCK_MONOTONIC, &tt1);
        size_t ans1 = div_compute(&DIV, num);
        clock_gettime(CLOCK_MONOTONIC, &tt2);

        long long time1 = (long long) (tt2.tv_sec * 1e9 + tt2.tv_nsec) -
                          (long long) (tt1.tv_sec * 1e9 + tt1.tv_nsec);


        clock_gettime(CLOCK_MONOTONIC, &tt1);
        size_t ans2 = num / i;
        clock_gettime(CLOCK_MONOTONIC, &tt2);

        long long time2 = (long long) (tt2.tv_sec * 1e9 + tt2.tv_nsec) -
                          (long long) (tt1.tv_sec * 1e9 + tt1.tv_nsec);

        printf("%ld, %lld, %lld\n", i, time1, time2);
    }   
}

改良的第一版測試，測試多個被除數除以單一除數

test1 code 連結

下圖為測試結果

可以發現在編譯器沒優化的情況下， quickdiv 明顯快於 div

而經過優化之後發現兩者速度皆減低不少，而根據 RinHizakura的實驗發現這是因為編譯器發現

除法的結果是不需要用到的，所以自動把它略過了。

改良的第二版測試，測試多個被除數除以多個除數

test2 code 連結

因為知道存在編譯器的優化，所以在程式過程中我們把編譯器的優化關掉。

同時為了避免測資的偏頗，設置數個不同的 divisor ，並分別計算兩種不同的除法的時間並取平均值，

quickDiv 暫時不包含 div_init 的執行時間（也就是僅計算除法的部份）。

由上圖可發現 quickdiv 明顯快於 div

改良的第三版測試，測試2的小變形

test3 code 連結

test2的變形，因為在程式執行過程中，其實不能忽略 div_init 的執行時間

因為他也算在 quickDiv 的部份環節，若是以 test2 為基準，每一層 loop 都找一個新的divisor

也就是每一個quickDiv都包含 div init的時間。

由上圖就可以發現， quickdiv 的時間明顯慢於 div

關於 RinHizakura 的實驗筆記的這部份修正，我覺得是不必要的。

int main()
{
    struct timespec tt1, tt2;
    clock_gettime(CLOCK_MONOTONIC, &tt1);
    for (uint64_t i = 2; i < 5000; i++) {
        div_info_t DIV;
        div_init(&DIV, i); 

        uint64_t num = rand() % 10000;
        num *= i;

        clock_gettime(CLOCK_MONOTONIC, &tt1);
        size_t ans1 = div_compute(&DIV, num);
        clock_gettime(CLOCK_MONOTONIC, &tt2);

        long long time1 = (long long) (tt2.tv_sec * 1e9 + tt2.tv_nsec) -
                          (long long) (tt1.tv_sec * 1e9 + tt1.tv_nsec);


        clock_gettime(CLOCK_MONOTONIC, &tt1);
        size_t ans2 = num / i;
        clock_gettime(CLOCK_MONOTONIC, &tt2);

        long long time2 = (long long) (tt2.tv_sec * 1e9 + tt2.tv_nsec) -
                          (long long) (tt1.tv_sec * 1e9 + tt1.tv_nsec);

        printf("%ld, %lld, %lld, %ld, %ld\n", i, time1, time2, ans1, ans2);
    }   
}

為了符合 div 的假設，因此需讓被除數 n 可以整除 d，才可以得到正確的計算結果

因為 jemalloc 其實也可以處理非整除的問題，只是要將 debug的那一行註解掉，而且我覺得 div_init 的時間是需要被考慮進去的，所以我在自己的測驗code3有加入 init ，還有一個地方是他的 divisor 是從 2 加到 4999 ，我覺得要用亂數才比較能符合真實狀況，所以有進行修改。

小結論:我們從改良的實驗code可以發現，當遇到一個新的除數，因為要包含div_init的時間，在這個時候，quickdiv會較慢，在除同一個除數的時候 quickdiv 會較快，但這個結論跟我的最開始的實驗有產生矛盾。

矛盾解法1.

仔細看 RinHizakura 跟我最開始設計的實驗有一個巨大的差異，就是他的變數宣告都是

uint64_t 而我的是 int ，但此題的除法實做應該只須用到 int ， quickdiv 是用乘法跟右移取代掉 32bit除法，在過程中的確需要 64bit ，但卻不是全部都需要。

test4 code 連結

將test2進行微調，並把變數宣告成int 並且不包含 div_init

可以發現，用 int 型別的確略快於 uint64_t ，然而卻不足以超越 quickdiv的時間
比對最初的資料跟 test1 ， 1E 筆資料 int 型別大概要0.9秒而 uint64_t 要1.5秒

矛盾解法2.

重新 review 自己最開始的測試結果，我發現我測試的是整段 code ，而 code 當中還包含rand（）
而 rand() 次數高達一億次，也因為包含這個非除法的部份，會導致自己偵測的時間變得不只包含除法，所以不準確。

hint

在測驗過程中應盡量避免極端值得出現，EX：數字太小，數字太小在 fastdiv 測試會有異常高的測驗時間值，但我因為測試的資料量較大，所以我認為平均下來應該還好，然而最好還是要撇去極端值存在才能更好得比較效能

新增: 第5題延伸問題 char str[] 更換為 char *str

結果: Segmentation fault

char *p = “abc”;

defines p with type ‘‘pointer to char’’ and initializes it to point to an object with type ‘‘array of char’’ with length 4 whose elements are initialized with a character string literal
If an attempt is made to use p to modify the contents of the array, the behavior is undefined.

string literal 是靜態配置的，也就是 const char *str 嘗試去更動其內容是 undefined behavior

新增 4.倍數判斷解說






bool divisible(uint32_t n)
{
    return n * M <= M-1;
}

延伸自上一題的觀念

若以 D=3 此題為例子來看:

其中 3*M=0x10000000000000002 會產生overflow ，也就是所以大於 3 的數字乘上 M 都會發生overflow ， 3M 在這裡被視為 0x0000000000000002 ， 4M 則代表 2+M…依此類推

而 6*M 則視為 4 ，也就是說當 3的倍數乘上 M ，最後的數值會小於或小於 M （不確定是哪個）。

但有一點很重要的是， M 是

⌈ \frac{2^{k}}{d} ⌉

（上高斯值），舉個例子說明

EX：當我們取 k=4 (bit數為4的意思) 而 d=4 ，則 M = 4 = (0xF/4)+1

取 n=4 ， nM = 16 （overflow ,修正為 0 < M）
取 n=5 ， nM = 20 （overflow ,修正為 4 = M）
取 n=6 ， nM = 24 （overflow ,修正為 8 > M ）
取 n=7 ， nM = 28 （overflow ,修正為 C > M ）
取 n=8 ， n*M = 32 （overflow ,修正為 0 < M ）

(0xF/4）實際上只有 3.x 的值，但取上高斯則為 4 ，會導致一個情況是 n * M 造成的overflow 進行修正後的值 = 取上高斯的值，導致 n*M=M ，但是這情況是不整除的。

所以要 -1 修正，把上高斯的值去掉。

新增： 6.改寫 singleNumber

這題舉例子說明的話

例1： 1,1,1,3

bit 0 =1 出現 4 次，而 bit1=1 出現 1 次，其餘 bit X=1 出現 0次，最後要回一個數字 bit 0,1 = 1

例2 : 1,1,1,3,5,5,5

bit 0 =1 出現 7 次，而 bit1=1 出現 1 次， bit2=1 出現 3 次其餘 bit X=1 出現 0次，最後要回一個數字 bit 0,1 = 1

從這裡我們可以發現，要去紀錄 bit X 出現 3k+1 次的時候 ( k >= 0 ) ，出現 3 次的則是不重要

因此我們可以做簡化，紀錄出現 3k+1次的，紀錄出現 3k+2 次的，出現 3k+3 次的














int singleNumber(int *nums, int numsSize)
{
    int apprear1 = 0, apprear2 = 0, apprear3 = 0;
    int tmp1=0,tmp2=0,tmp3=0;
    for(int i=0;i<numsSize;i++) {
        apprear1 = (~(tmp2 | tmp1) & nums[i]) | tmp1 & ~nums[i] | tmp3 & nums[i];
        apprear2 = tmp1 & nums[i] | tmp2 & ~nums[i];
        apprear3 = tmp2 & nums[i] | apprear3 & ~nums[i];
        tmp1 = apprear1;
        tmp2 = apprear2;
        tmp3 =apprear3;
    }
    return apprear1;
}

apprear 1 紀錄出現 3k+1 次的， apprear2 紀錄出現 3k+2 次的， apprear 1 紀錄出現 3k+1 次的。

apprea1 要紀錄的有

1.沒有出現在 3K+1 次也沒有出現在 3K+2 次但是 nums[i] 有的（因為這些應該被紀錄在 apprear2 跟 apprear3 裡面）
2.出現 3K+1次但在 nums[i] 沒出現的，
3.出現在 3K+3 次也有出現在 nums[i]裡面的(因為 3k+4 = 3(k+1) +1 )

apprea2 要紀錄的有

2.出現 3K+1次在 nums[i] 也有出現的，
3.出現 3K+2 次但在 nums[i] 沒出現的

apprea3 要紀錄的有

2.出現 3K+2次在 nums[i] 也有出現的，
3.出現 3K+3 次但在 nums[i] 沒出現的

最後回傳出現 3K+1 次的即可。

改寫版 code 連結

改寫擴充版 code 連結

Yiwei Lin

2021/01/19 13:37:22

因為 jemalloc 其實也可以處理非整除的問題，只是要將 debug的那一行註解掉

如果我記得沒錯的話，非整除的狀況答案是有可能出錯的喔(你可以實驗確認一下?)。將 debug 註解掉只是"程式可以執行"。 (Edited)

2021/01/19 13:47:02

div_init 的時間是需要被考慮進去的

因為我當初預設使用快速除法的情境是"會有一個經常需要除的數字"，因此初始化(div_init)只要一次，而真正的除法(div_compute)則會不斷被使用。所以我認為 div_compute 的時間差距才是最在意的地方。 (Edited)

2021/01/19 13:48:33

不過我覺得確實應該要考慮要把快速除法使用在甚麼情境上去設計實驗，所以我的做法也不一定是完全合理的~

Jim Huang

2021/01/25 04:54:22

"for example" 的簡寫是 "e.g."，而非 "EX"，後者通常指「之前的」 (Edited)

2020q3 Homework2 (quiz2)

1. ASCII 編碼判斷

延伸問題二

2. 16進位字元轉換

3.快速除法

程式原理

4.倍數判斷

程式原理

5. 字串大寫轉換小寫

程式原理

6. 單次數尋找

程式原理

新增: 第2題 16進位字串轉換

新增: 第3題 快速除法（jemelloc原理）

新增: 快速除法跟一般除法之間的效能比較:

針對實驗設計錯誤的問題，我仿照RinHizakura的實驗方式進行實驗

改良的第一版測試，測試 多個被除數 除以 單一除數

改良的第二版測試，測試 多個被除數 除以 多個除數

改良的第三版測試，測試2的小變形

矛盾解法1.

矛盾解法2.

hint

新增: 第5題 延伸問題 char str[] 更換為 char *str

新增 4.倍數判斷 解說

新增： 6.改寫 singleNumber

Read more

Parallel Programming HW-6

Parallel Programming HW-2

2020q3 Homework3 (quiz3)

論文筆記

新增: 第3題快速除法（jemelloc原理）

針對實驗設計錯誤的問題，我仿照`RinHizakura`的實驗方式進行實驗

改良的第一版測試，測試多個被除數除以單一除數

改良的第二版測試，測試多個被除數除以多個除數

新增: 第5題延伸問題 char str[] 更換為 char *str

新增 4.倍數判斷解說