Google Drive
Gist
Clipboard
contributed by < yourui1017 >
「資工系的學生不會寫程式，機械系的學生不會做機械」
人不付出犧牲，就得不到任何回報。如果要得到什麼，就必須付出同等的代價，這就是鍊金術的基本原則，等價交換。當時我們深信著，這就是這世界的真理。–––《鋼之鍊金術師》
對於這兩句話特別有感受。雖然目前已經修習過許多課程，但往往都只是把課本上的知識死背硬背，求的就只是課程的高分，雖然成績單上有好看的成績，但根本不了解學習這些課程背後的意義，在面對真實世界的考驗時，無法應用學習的知識解決當前的問題。
若想要貫通學習課程的意義必須要擁有獨立思考的能力並解決實作時遇到的困難，沒有付出犧牲是無法解決面對的問題的，只有絞盡腦汁不被問題擊敗，才能夠一步一步慢慢成長。
前陣子因為在忙於實驗室的比賽的部份，對於本課程的投入時間非常不足，根據等價交換的基本原則，付出多少時間就只能得到等價的回報。另外，在觀摩其他學員的成果時，發現學員對於整體系統的開發到微小的細節都有充分的理論與實驗佐證，在進行實驗時也會考慮到不同的資料測試結果（如：最差狀況、最佳狀況、隨機資料等等），讓我了解到想要開發完整的專案必須留意各式細節，仔細思考實驗應考慮的情況，認真對待面對的問題。
list_sort 到 lab0-c ，比較自己實作的排序驗算法與 list_sort 的效能差異。quick_sort 的運作原理，改善演算法使用到的記憶體大小與最差狀況的快速排序實作，並使用實驗佐證。minrun 的判斷，並實作插入排序保證達成 minrun ，進行效能測試的實驗，最後將 Timsort 引入 lab0-c 作為另一個有效的排序命令。尚未開始，需要投入更多時間。
尚未開始，需要投入更多時間。
目前想要做的期末專案為以下：
stackful vs. stackless
A => A1 + A2 + A3
B => B1 + B2
A1, A2, A3 -> B1, B2 -> A1, ..
A1 -> B1, B2 -> A2, A3
保存狀態: 用到 stack
使用 global
IEEE 754, assume float is 32-bit width
float float_mul10(float x)
{
// using bitwise operation; No mul/div
}
10 = 8 + 2 = (2 << 3) + (2 << 0)
誠實面對自己
TODO: 撰寫程式碼並測試，附上你的分析
在做 float_mul10 之前，需要先了解浮點數的運作方式，參考自 你所不知道的 C 語言: 浮點數運算 和 浮點數運算和定點數操作 ，在 C 語言中 float 是遵照 IEEE 754 的規定進行設計的， float 存放方式分為三種：
為了使數值表達範圍更廣，才使用這種表達方式，但相對的這種方式會導致數值運算變得更加複雜，普通的四則運算就要考慮到三種不同的模式：
Denormalize 是為了解決 underflow 的問題，在 denormalize 模式下可以表達更小的數值範圍。
underflow，意思是運算出來的數值非常接近 0，近到無法用正規的浮點數來表示
並因為此種表示方式延伸出誤差和精度問題。underflow 會有什麼麻煩呢？明明 \(A>B\)，但是 \(A-B\) 的運算結果卻成為 0
NaN 用以表達未定義或不可表示的情況。
根據 IEEE 754 2008 年版本 6.2 節
有兩種不同的 NAN
X111 1111 1AXX XXXX XXXX XXXX XXXX XXXX
如果在 A 的位置為 1 ，則為 quiet NAN
反之如果 A 的位置為 0 ，其他的位置為非 0 ，則為 signal NAN
6.2 節也提到當要傳送這個 NAN 時，應採取 quiet NAN 的形式，當要送給系統信號時，應當採取 signal NAN
INF 模式則是用以表達接近無限大的數值。
誤差
浮點數表示法會隨著數值愈來愈大，誤差也愈來愈大。
精度
\(log_{10}2^{24} ≈ 7.224719\)
了解浮點數的表示法後，就可以開始實作函式 float_mul10。
IEEE 754, assume float is 32-bit width
float float_mul2 (float f)
{
unsigned int uf = *(unsigned int*) &f;
unsigned int uf_sgn = (uf >> 31) & 0x01;
unsigned int uf_exp = (uf >> 23) & 0xff;
if (uf_exp == 0) {
uf <<= 1;
uf += (uf_sgn << 31);
} else if (uf_exp != 0xff) {
uf_exp += 1;
if (uf_exp == 0xff) {
uf &= 0x80000000;
} else {
uf &= 0x807fffff;
}
uf = uf + (uf_exp << 23);
}
float result = *(float*) &uf;
return result;
}
float float_mul8 (float f)
{
unsigned int uf = *(unsigned int*) &f;
unsigned int uf_sgn = (uf >> 31) & 0x01;
unsigned int uf_exp = (uf >> 23) & 0xff;
if (uf_exp == 0) {
uf <<= 3;
uf += (uf_sgn << 31);
} else if (uf_exp != 0xff) {
uf_exp += 3;
if (uf_exp == 0xff) {
uf &= 0x80000000;
} else {
uf &= 0x807fffff;
}
uf = uf + (uf_exp << 23);
}
float result = *(float*) &uf;
return result;
}
float float_mul10(float f)
{
// using bitwise operation; No mul/div
return float_mul2(f) + float_mul8(f);
}
首先，先把 float_mul10 拆解成 float_mul2 + float_mul8，這樣一來就可以針對 exponent 的部份進行左移得到 float_mul2 和 float_mul8。
至於在 float_mul2 函式中，需要先使用 unsigned 解釋浮點數的資料，並且藉由 bitwise operetion 得到 sign bit 和 exponent 。
接下來針對三種模式進行運算
最後把無號數的表示方式使用浮點數資料型態解釋並回傳。
注意：
*(float *) &uf 和 (float) uf 的差別
*(float *) &uf 代表使用浮點數的方式解讀 uf(float) uf 則是會把當前 uf 的資料使用 IEEE 754 的規定轉型成浮點數，導致資料會有變化結果：將自己實作的 float_mul2、float_mul8、float_mul10 和內建的浮點數乘法使用 perf 進行比較，測資個數皆為 100000 筆。
int main()
{
srand(42);
float x[NUM_FLOATS];
float result;
for (int i = 0; i < NUM_FLOATS; i++) {
x[i] = generate_random_float(LOWER_BOUND, UPPER_BOUND);
result = float_mul10(x[i]);
}
// for (int i = 0; i < NUM_FLOATS; i++) {
// x[i] = generate_random_float(LOWER_BOUND, UPPER_BOUND);
// result = x[i] * 10;
// }
printf("%f\n", result);
return 0;
}
自己實作的：
內建的浮點數乘法：
int main()
{
srand(42);
float x[NUM_FLOATS];
float result;
unsigned int a = 0x00000ff1;
for (int i = 0; i < NUM_FLOATS; i++) {
x[i] = *(float*) &a;
result = float_mul10(x[i]);
}
// for (int i = 0; i < NUM_FLOATS; i++) {
// x[i] = *(float*) &a;
// result = x[i] * 10;
// }
printf("%f\n", result);
return 0;
}
自己實作的：
內建的浮點數乘法：
int main()
{
srand(42);
float x[NUM_FLOATS];
float result;
unsigned int a = 0x7F800001;
for (int i = 0; i < NUM_FLOATS; i++) {
x[i] = *(float*) &a;
result = float_mul10(x[i]);
}
// for (int i = 0; i < NUM_FLOATS; i++) {
// x[i] = *(float*) &a;
// result = x[i] * 10;
// }
printf("%f\n", result);
return 0;
}
自己實作的：
內建的浮點數乘法：
quiz10 開發紀錄請看:2024q1 Homework(quiz10)
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe