Try   HackMD

2023q1 Homework3 (fibdrv)

contributed by < bonianlee >

不要打錯自己的 GitHub 帳號

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

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          6
On-line CPU(s) list:             0-5
Thread(s) per core:              1
Core(s) per socket:              6
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           158
Model name:                      Intel(R) Core(TM) i5-9500 CPU @ 3.00GHz
Stepping:                        10
CPU max MHz:                     4400.0000
CPU min MHz:                     800.0000
BogoMIPS:                        6000.00
Virtualization:                  VT-x
L1d cache:                       192 KiB
L1i cache:                       192 KiB
L2 cache:                        1.5 MiB
L3 cache:                        9 MiB
NUMA node0 CPU(s):               0-5
## 完成進度

不用抄題目,show me the code!

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

開發過程

正確顯示
fibonacii(100)

根據〈費氏數列分析〉,費氏數列 (Fibonacci sequence) 若以 64 位元來表示的話,正確的數值最高只能夠顯示到第 92 項

fibonacii(92) ,因為當
fibonacii(n),n>92
時,會因為數值超過 64 位元所能表示的最大值,而造成溢位 (overflow) 的發生

在原始程式碼 fibdrv 中,費氏數列是以 64 位元的資料型態 long long 來表示,實際運行的結果顯示為

f(93) fail
input: 7540113804746346429
expected: 12200160415121876738

與預期的結果相同,當數列計算到

f(93) 時,會因為溢位而導致系統報錯,且顯示的輸出結果也與預期的不同,為了要解決這種狀況,我參考〈Small/Short String Optimization 的實作〉以及 qwe661234 的實作

解決方式是將數字改以字串 (string) 的形式進行運算並且表示結果的值,首先定義結構體

typedef struct str{
    char numberStr[106];
}str_t;

接著計算費氏數列的部份,因為只會用到加法,故實作字串的加法,以下為部份程式碼

static void add_str(char *a, char *b, char *out)
{
    size_t size_a = strlen(a), size_b = strlen(b);
    int i, sum, carry = 0;
    if (size_a >= size_b) {
        for (i = 0; i < size_b; i++) {
            sum = (a[i] - '0') + (b[i] - '0') + carry;
            out[i] = '0' + sum % 10;
            carry = sum / 10;
        }

        for (i = size_b; i < size_a; i++) {
            sum = (a[i] - '0') + carry;
            out[i] = '0' + sum % 10;
            carry = sum / 10;
        }
        
    if (carry)
        out[i++] = '0' + carry;
    out[i] = '\0';
}

前述的程式碼在做兩個數字字串的相加,其作法是十進位制每一個位數個別做相加,將進位存在 carry 當中,而 out 則用來儲存 ab 相加的數字字串結果

而因為 out 是從低位數排列到高位數的字串,故在輸出結果時會將 out 做反轉,使最終結果方便閱讀,以下結果是計算到

fibonacii(100) 的結果

...
Reading from /dev/fibonacci at offset 98, returned the sequence 135301852344706746049
Reading from /dev/fibonacci at offset 99, returned the sequence 218922995834555169026
Reading from /dev/fibonacci at offset 100, returned the sequence 354224848179261915075

時間測量與效能分析