contributed by < shauming1020
>
homework
假設 divop() 的第二個參數必為大於 0 的整數,而且不超過 int 型態能表達的數值上界。
int od = slots & 1;
判斷 slots 是否為奇數double result = divop(orig / D1, od ? (slots + D2) >> 1 : slots >> 1);
od ? (slots + D2) >> 1 : slots >> 1)
當 slots 是奇數時,必須 + 1 後再進行右移 (/2) ,如此才會滿足遞迴中止條件 (slots == 1),因此 D2 為 1orig / D1
浮點數無法透過右移 bit 來進行除 2 的動作,因此 D1 為 2if (od) result += divop(result, slots);
e.g. 在計算時會變成 ,誤差為 ,恰近似於
將上述例子用數學式描述
搭配閱讀 C 語言: 編譯器和最佳化原理 及 C 語言: 遞迴呼叫
觀察 gcc -S -O 編譯器行為
假設 float 為 32-bit 寬度,考慮以下符合 IEEE 754 規範的平方根程式,請補上對應數值,使其得以運作:
搭配研讀 以牛頓法求整數開二次方根的近似值 (第 19 頁)
,由於 x 要為正整數,因此 ,即 ,而 k 的範圍可從近似解 得知
觀察
1 | N | 0 |
2 | N + (-1) | -1 |
3 | N + (-3) | -2 |
4 | N + (-6) | -3 |
5 | N + (-10) | -4 |
n | N + | 1-n |
檢驗 是否成立來判斷正整數解 x,從上表可以觀察出 ,故 ZZZ 為 (1 - i)
e.g.
而 ,且 k 為大於等於 2 的正整數,因此
x += (1-i)
計算出 後,進入下個迴圈前,k 會先被加一再和 比較大小,因此範圍為 ,迴圈的條件判斷式才會是 i < x