2023q1 Homework3 (fibdrv)

contributed by < bonianlee >

不要打錯自己的 GitHub 帳號
:notes: 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!
:notes: 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 則用來儲存 a 與 b 相加的數字字串結果

而因為 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

時間測量與效能分析