contributed by < rain20010126
>
資工系的學生不會寫程式,機械系的學生不會做機械
你該學習的不是看到事情要完蛋了就去避免失敗,而是應該學習如何處理與承受失敗,你才能變得比以前更強大。
要是現在就放棄的話,你這輩子日後遇到這種等級的困難,就只會想逃避而已
人不付出犧牲,就得不到任何回報。如果要得到什麼,就必須付出同等的代價,這就是鍊金術的基本原則,等價交換。當時我們深信著,這就是這世界的真理。–––《鋼之鍊金術師》
此時的我就如同作者口中的機械系的學生相同,除了沒辦法設計出一個完整的機構外,文章中的愷宏所需要解決的問題我能解決出來的真的屈指可數,如果我處在他們的團隊中,很不幸的沒有什麼是我能幫上忙的,這是我應該檢討的地方。
在作業中常常令我挫折,在理解每週的考題與教材都需要花費我大量的時間,而作業中的延伸問題需要自己動手寫出程式碼,常常遇到些 error 就會想跳過這個問題,或者在看完題目要求後只會默默地對自己說:這問題太難了,我一定做不出來就直接放棄。我需要更誠實面對自己,沒有人一開始就會,需要一步一腳印慢慢加強自己,如同作者慢慢解決他在實作所遇到的困難一樣,試著解決問題,克服逃避問題的心態。
由於是機械背景,相關的先備知識不夠充足,因此我會先把閱讀課程教材以及補齊欠的作業補齊作為主要努力的方向,以下是我對期末專案的想法為以下
依照有興趣作為排序
最後包裝成題目的程式碼如以下
首先 uint32_t x = (in | 1) - (in >> 2)
部分,當 in
為偶數時會需要做 +1
,
當 in
為奇數時,
接著 uint32_t q = (x >> 4) + x;
,當 in
為偶數時,
當 in
為奇數時,
此時若是 ,則 q = (q >> 8) + x;
可以等價為 q = x
,也就是 q
不變,假設 in
為奇數,(q >> 3)
會等價於 即可取得商數
這邊我有發現若是將 in
設定為偶數 (120) 代入,若是沒有經過 +1
處理的話算出來的商數會錯誤,但不理解詳細原因為何
若是 則會透過 q = (q >> 8) + x;
,假設 in
為奇數,可以將 逼近至
最後取餘數程式碼 *mod = in - ((q & ~0x7) + (*div << 1));
即為 *div * 10
,其中 q & ~0x7
目的是保留最後三個 bits 以外的位元,等同於 *div << 3
TODO: 改善上方程式碼
IEEE 754, Assume float is 32-bit
誠實面對自己
TODO: 撰寫程式碼、測試,附上分析
首先由 IEEE 754 可知 32-bit 浮點數表示法如下圖
其中 sign 記錄正負號, exponent 用來計算指數的偏移量,計算方式為 ,其中 為固定偏移值,fraction 部分為計算數字的實際值,計算公式為 ,由上述可知,32-bit 浮點數的表示方式為
實作以上程式碼之前,我初步的想法是將輸入 x
分別乘以 和 做相加, 也就是 exponent 分別加上 和 ,因此直接使用較值觀的方法,直接在 exponent 加上對應到 和 的數值
接著參考 浮點數運算和定點數操作, 你所不知道的 C 語言: 浮點數運算 了解到除了上述表示方法 (Normalized),還需要考慮到 NaN ,INF 以及 Denormalize 的表示方式如下圖
Denormalize 的表示方式是用於處理極小的數值,此表示方法允許浮點數系統在接近零的範圍內平滑地過渡,避免超出 Normalized 表示方法時能表達的最小數值,使數值直接跳到 0,以此來減少計算中的誤差和 underflow 問題。
因此程式碼部分需要分成三種情況
以下為完整程式碼
測試部分參考 Youri 的作法,設立 10000 筆資料,將自己實作的 float_mul10
和內建的浮點數乘法使用 perf stat
進行比較,並將浮點數的三種不同表示方法分開進行比較
float_mul10
結果:
內建浮點數乘法的結果:
float_mul10
結果:
內建浮點數乘法的結果:
float_mul10
結果:
浮點數乘法的結果:
TODO: 找同學同組並確認
TODO: 第 4 周測驗 3 的 XTree ,將其與紅黑樹、 AVL 樹進行比較: 量化分析 (演算法分析: tree height, 數學!),提出 XTree 的改進方案