2023q1 Homework5 (assessment)

contributed by < fewletter >

實驗環境

$ uname -r
5.15.0-67-generic

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.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 MHz:                         3000.000
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

改進第三周作業 fibdrv

• 利用 Schönhage–Strassen Algorithm 來實作乘法 bn_multSSA
• 利用大數乘法實作 fast doubling，並對大數乘法 bn_multSSA 進行除錯

〈因為自動飲料機而延畢的那一年〉啟發和修課心得

• 修課心得
  學期初抱著決心來修這堂課，給自己的要求是無論如何都不要退選，就算沒有理解或聽懂上課的教材，至少都可以開開眼界，而一開始的功課量就已經讓我應付不來，只能跟自己說走一步算一步，不要放棄一直走，不知不覺就已經走到第五周的作業，而這幾周的一直都有感受到滿滿的挫折，但是就像因為自動飲料機而延畢的那一年中所說的 「你不能現在就放棄，要是現在就放棄的話，你這輩子日後遇到這種等級的困難，就只會想逃避而已。」，所以我會撐下去，撐完就是我的。

  在修課期間一直聽到老師說要能夠注重細節才能征服 Linux 核心，而我在寫作業時不斷體會到這句話的意思，就舉這禮拜的作業作為例子，當我在實作大數乘法 bn_multSSA 時，我不停地遇到一堆我沒想到過的 bug，遇到的當下真的非常不爽和不開心，明明在測試時

  $F(91)\times F(92)$ 這兩個數字相乘出來的結果是對的，但是卻沒辦法在 fast doubling 中使用，甚至還會遇到程式執行時間太長跑不出來。

  為了去 debug，我很土法煉鋼的把所有資料一一列出，發現到一個大問題，原來在執行 fast doubling 的時候如果沒有限制大數的 size 大小，size 會一直疊加上去，到

  $F(100)$ 時，size 甚至會到達 80 ，而這一切都只是因為我在寫程式時完全沒有想到重複使用乘法會疊加 size 大小，所以當我回去看作業說明:大數運算乘法，發現了這行程式碼，
  ​​int d = bn_msb(a) + bn_msb(b);
  ​​d = DIV_ROUNDUP(d, 32) + !d; // round up, min size = 1
  

  霎那間我完全懂了，我完全懂為什麼這行程式碼要出現在這裡，這行原本被我忽視掉以為沒什麼重要的程式碼在 fast doubling 中會限制大數 size 大小，而我在測試

  $F(91)\times F(92)$ 並沒有重複使用乘法，導致沒有測出這個問題，到這裡我完全可以了解什麼叫注重細節，並且實作過後更能夠深刻體會到這句話。