markarz (簡子昕)
簡介
- GitHub:
markarz - HackMD:
WestminsterSorryMaker
2025 Linux 核心設計/實作 春季班 自我評量
成果發表和貢獻
6分。
這次專題有特別研究xorshift，它的核心時做是用xor和左右位移的位元處理做出亂數功能，那數學的部分他有一個轉移矩陣，這個轉移矩陣T的公式:
\(T = (I + L^c)(I + R^b)(I + L^a)\) ，
\((I+L^C)\vec{z}\) =
z^(z<<c)這個 \(\vec{z}\) 就是數學定義的\(seed\) ，z^(z<<c)
是程式語法，那 \(T\)
的物理意義是產生亂數的核心邏輯，也就是說我的 \(\vec{seed} !=0\)可以與 \(T\)
相乘就會產生亂數，那為了驗證a、b、c參數設定是可以做出亂數功能，這個轉移矩陣轉變成特徵多項式，這個特徵多項式需要滿足兩個性質:minimal
polynomial 和 P(k) 的值不被 K 本身整除，這個 P(K) 是特徵多項式套入
K後的值，\(k\in2^{32}-1\)的質因數，詳細驗證有在期末專案連結提供。
作業/隨堂測驗
6分。 在這次寫了 lab0 讓自己對 linked list
相關程式設計有進步不少，也是老師藉由這個專案讓我知道有好用到
list.h，可以不用自己一直手刻程式碼，可以藉由函示庫裡面的fuction
節省程式碼行數，也讓我知道原來我們所使用的亂數其實也不是真的隨機產生而是有規律的產生出來，在這次也讓我知道我的數學能力和程式設計能力還需要多多加強。
期末專題
8分。
我剛開始先重看一次老師給的教材，之前在做時都沒看得很懂，所以藉由專題讓我再重做一次，發現自己當初沒有好好看教材造成自己無法順利實做，後面在嘬期末專題時順利做出，在剛開始做時有看網路上怎麼實作演算法，把他們的實作邏輯直接拿來改寫，後來發現無法做到
uniform
的效果，後來發現srand()不能加進去，因為老師給的測試程式會一直執行到
do_shuffle，造成 srand() 一直被重複執行，那我有去看 c99
規格書查看 srand() 內部程式碼設計，發現他是負責設定初始值，初始值會給
rand() 使用完就會產生一個數字，那如果我們一直呼叫
srand()，那他的起始值會一直一樣然後產生出來的亂數會一模一樣，就會造成不均勻的問題。
在老師教材裡有看到要對亂數做比較，所以我看到教材提供的關鍵字
xorshift，我就去查詢他的程式碼實作和理論，最後也成功用他去實作Fisher–Yates
shuffle，也比較出xorshift() 比 rand()
效能和亂數品質都來的好，在這次實作發現數學真的可以幫助程式效能改善，像是rand()是用一系列的除法和模同餘的指令實作，但是xorshift()卻能用位元位移結合互斥或的方式做亂數演算法，他能實做出來就是藉由很多數學推導而成，讓我深知老師說程式要寫的好脫離不了數學的背後的原因。
TODO: 依據第一份作業指示，重新投入，並強化對於亂數、排序演算法和改進、常數時間判定的理論和實務、統計手法、網頁伺服器，以及程式碼品質的議題。 我是專精在
Fisher–Yates shuffle的實作，我使用兩種亂數演算法做出兩個shuffle的版本，針對效能以及亂數的均勻程度做比較。
與授課教師的互動
7分。
- 6/9
討論開根號和計算其二進位表示中，共有幾個 “1” 上課時有聽到老師在講開根號，一開始覺得直接用 C library 裡面的 function 計算就好，直到老師在一對一面談時問我開根號的程式設計才發現原來平常很基本數學自己竟然無法馬上用遞迴寫出來，讓我知道自己覺得簡單的東西卻無法用程式時做出來發現自己的程式能力和數學是有問題，所以我後面重看老師給的數學推導，才知道根號背後有很多自己大學學的微積分，自己卻看不懂需要重學，也發覺到老師開頭一直講數學的重要。
計算其二進位表示中，共有幾個 “1”，老師要求我不能用迴圈和 branch 相關指令，我當下也寫不出來，後來去查別人寫的才知道可以用位元位移和 and 計算，這個方法程式碼很少，但是當下要想到只有一個可能就是平常要做 bitwise 相關操作，也是老師讓我知道原來很多東西都是有辦法做到精簡化讓程式效率變好，而不是只想有做到就好，如果繼續抱持功能有做到就好的想法，會讓自己未來寫出來的程式都變得毫無效率，也會直接影響到自己工作做的產品效能。
所見所聞所感
10分。
觀察同學們的心得
這學期看到同學們做出許多跟排程相關的期末專題，讓自己對 OS 有重新的看法，以前自己對 OS 相關都只有看到表層，直到這堂課看到許多同學都有做排程專案才感受到不是課本上知道 CPU 在每個演算法上怎麼安排 process 進 running、ready state，同學讓我感受到原來我們其實也有能力動手寫這些排程相關程式，而不是紙上談兵。
觀察老師的心得
老師每次都為了讓我們不要睡著，所以都會講笑話給我們聽，我覺得效果很好，老師為了不讓學生在想他問的問題時沒有聲音都會講一些跟科技產業相關課題，讓我們即使在學校也可以知道很多科技業發生的事情，老師教材設計的很用心雖然太多短時間看不完，但是它讓我們重新調整自己的學習方式，讓我們學會袍根究底而不是不求甚解，列出一些大家平常覺得簡單的數學公式原來背後有大量微積分和統計學，特別在程式設計上老師只會教我們如何寫一個程式是有效率不是用一堆程式碼做到事情。
回顧自身在本課程的投入狀況 自己這學期只有 lab0 部分功能，還有老師一對一給的問題，我這學期雖然只做一些事情，但是老師瘸改變了我讀東西的習慣，以前我都只會看別人怎麼寫然後不特別探究數學相關理論只管對方邏輯怎麼設計，寫出來後假裝自己懂這段程式，殊不知自己其實甚麼都不懂只是看過別人寫得程式，也讓我學會要直接看規格書不是單靠猜測或是用測試方式得知，而是要先去看規格書寫的描述準確得知原因，因為你用測試其實也是用你的想法去做也不見得是他真正的原因，也讓我覺得我該回去算微積分了。 ## 自我評量 (1 ~ 10)： \(GEOMEAN = ( 6 \times 6 \times 8 \times 7 \times 10 )^{1/5} = 7.25935618\)
方案 B ：\(1 + floor(GEOMEAN) = 1 + 7 = 8\)
