Try   HackMD

2024q1 Homework5 (assessment)

contributed by < dockyu >

閱讀〈因為自動飲料機而延畢的那一年〉與課程啟發

閱讀心得

我看完因為自動飲料機而延畢的那一年後覺得非常感動,他們就好像灌籃高手裡的湘北高中一樣付出努力但是最後卻不是最好的結果,乍看之下好像浪費了付出的努力,但是如果過程中有學到東西(心態的成長,經驗累積,朋友的幫助)就夠了

期末專題提案

希望能夠進行 simplefs 或是 kHTTPd-改進


Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

IEEE 754. Assume float is 32-bit width.

// Return x * 10
float float_mul10(float x)
{
    // using bitwise operation; No mul/div
    unsigned sign = (unsigned)x >> 31;
    unsigned exp = ((unsigned)x << 1) >> 23;
    unsigned frac = ((unsigned)x << 9) >> 9;
    
    unsigned frac1 = frac << 3;
    unsigned frac2 = frac << 1;
    frac1 += frac2;
    
    frac1 = frac1 >> 4;
    exp = exp << 2;
    
    unsigned result = (sign << 31) | (exp << 23) | (frac1);
    return (float)result;
}

10 = (2 << 3) + (2 << 0)
float_mul10(4.9) = ?
TODO: 撰寫程式碼、測試,分析
誠實面對自己!


如果按照我一開始的寫法 (unsigned) 會將 x 強制轉型,之後操作的都不是浮點數的格式,小數點以下的部份也在這時候就不見了

unsigned frac = ((unsigned)x << 9) >> 9;

印出 (unsigned)x 的二進制

/* x: 4.9 */
(unsigned)x
	4
	0x00000004
	0000 0000 0000 0000 0000 0000 0000 0100

用一個指標 p 指到 x ,可以在不用強制轉型的情況下使用 bitwise 去操作,輸出 *p 確認

/* x: 4.9 */
unsigned* p = (unsigned*)&x;
*p
	0x409ccccd
	0100 0000 1001 1100 1100 1100 1100 1101

取出浮點數的三個區塊

unsigned sign = (*p & 0x80000000) >> 31; /* 1000 0000 0000 0000 0000 0000 0000 0000 */
unsigned exp = (*p & 0x7F800000) >> 23;  /* 0111 1111 1000 0000 0000 0000 0000 0000 */
unsigned frac = *p & 0x007FFFFF;         /* 0000 0000 0111 1111 1111 1111 1111 1111 */
x
	0x409ccccd
	0100 0000 1001 1100 1100 1100 1100 1101
sign
	0x00000000
	0000 0000 0000 0000 0000 0000 0000 0000
exp
	0x00000081
	0000 0000 0000 0000 0000 0000 1000 0001
frac
	0x001ccccd
	0000 0000 0001 1100 1100 1100 1100 1101

指數部份是

129127=2 ,是2的2次方
小數部份是
00111001100110011001101
,最前面要加上1所以是
1.001110011001100110011012
,也就是十進制的
1.2250000238418579101610

小數部份乘上指數部份
1.2250000238418579101622=4.90000009537

從這個結果可以看出這確實是 4.9 的浮點數,而且我取出的3個部份也是對的,接著就可以將小數部份乘10

我一開始的寫法是

/* frac: 00111001100110011001101 */
unsigned frac1 = frac << 3;
unsigned frac2 = frac << 1;
frac1 += frac2;

沒有考慮到前面要加上的1,所以現在要做的是將小數部份乘以10並從第一個1開始向後數24個,後面23的就會是 frac 的 23 bit 的內容

首先要將 implicit leading bit 補上去, 在 IEEE 754 中浮點數的 implicit leading bit 是 1

frac = frac | 0x00800000;

可以看到在第24位加上1,因為 frac 佔了 23 位

frac
	0x001ccccd
	0000 0000 0001 1100 1100 1100 1100 1101
frac with implicit leading bit 1
	0x009ccccd
	0000 0000 1001 1100 1100 1100 1100 1101

首先是能正確的乘2和乘8

unsigned frac2 = frac << 1; /* frac * 2 */
unsigned frac8 = frac << 3; /* frac * 8 */
frac*2
	0x0139999a
	0000 0001 0011 1001 1001 1001 1001 1010
frac*8
	0x04e66668
	0000 0100 1110 0110 0110 0110 0110 1000
frac = frac2 + frac8; /* frac * 10 */

因為 frac8 在 27 位一定有1,而兩個二進制相加最多只會進位一位,所以 28 位有可能會有 1 ,而 29 位則不可能會有,所以只要判斷 28 位 是不是 1 就可以了,因為如果不是 那就知道最高位的 1 一定在 27 位

  • 28 位是 1 : 取 5~27 為 frac
  • 28 位不是 1(27位是1) : 取 4~26 為 frac
if (frac >> 27)
    frac = frac >> 4;
else 
    frac = frac >> 3;

frac = frac & 0xff7fffff; /* 1111 1111 0111 1111 1111 1111 1111 1111 */
frac * 10
	0x06200002
	0000 0110 0010 0000 0000 0000 0000 0010
frac 23 bit
	0x00440000
	0000 0000 0100 0100 0000 0000 0000 0000

在這之前因為有調整位數所以指數部份也要有對應的更改

  • 28 位是 1 : frac 位移4位,指數要+4
  • 28 位不是 1(27位是1) : frac 位移3位,指數要+3
if (frac >> 27) {
    exp += 4;
    frac = frac >> 4;
} else {
    exp += 3;
    frac = frac >> 3;
}

可以成功輸出

float x = 4.9;
printf("%f\n", float_mul10(x)); /* 49.000000 */
x = 4.91;
printf("%f\n", float_mul10(x)); /* 49.099998 */
x = 4.92;
printf("%f\n", float_mul10(x));  /* 49.200001 */

如果比較直接乘10和我寫的乘10,會發現我的誤差也會出現在直接乘10上,但在某些數值上還是會有不一樣例如3.14

49.000000
49.000000

x:4.910000
49.099998
49.099998

x:4.920000
49.200001
49.200001

x:99.000000
990.000000
990.000000

x:99.900002
999.000000
999.000000

x:3.140000
31.400002
31.400000

我想要作到 branchless

- if (frac >> 27) {
-     exp += 4;
-     frac = frac >> 4;
- } else {
-     exp += 3;
-     frac = frac >> 3;
- }
+ int shift = 3 + (frac >> 27);
+ exp += shift;
+ frac = frac >> shift;

commit: 06e0963


TODO: quiz3+4 + quiz7 + extra