--- tags: 作業 --- # 浮點數除法程式 假設 `divop()` 的第二個參數也就是除數，必為大於 `0` 的整數 ```cpp= #include <stdio.h> #include <stdlib.h> double divop(double dividend, int divisor) { if (dividend == 0 || divisor == 1) return dividend; int odd = divisor & 1; double result = divop(dividend/2, odd ? (divisor+1)>>1 : divisor>>1); if (odd) result += divop(result, divisor); return result; } ``` ### 程式說明： * 第 5 ~ 6 行： * 判斷被除數為 0 或是除數為 1 的時候回傳被除數，作為遞迴結束的條件 * 除數在第 8 行遞迴會透過 bitwise 右移，所以無論什麼除數最後一定可以得到 1，使遞迴結束 * 這個會使得奇數除數時會有個小循環，不斷 +1 右移直到 1，又再次回到原本的除數 **(第 10 行)** * 被除數在第 8 行遞迴會直接除以 2，由於型態為 `double`，所以最後除到最小的誤差 `DBL_EPSILON` (定義在 `float.h`)，就會視同等於 0 了 * 決定奇數除數時會何時結束，例如改成 `dividend <= 1e-4`，就最多計算到小數點第 5 位 * 第 7 行： * 判斷當前除數的奇偶，直接比較 LSB 的值即可 * 第 8 行： * 程式的核心，可以想像成分數，分子分母同 ÷ 2 不影響結果，分母變 1 時分子就是商了 * ÷ 2 對於浮點數來說只是改變 exponent 的部分而已 * 除數為偶數的話比較直觀，兩邊都能同 ÷ 2，尤其是當 2 的指數 * 除數為奇數的話，會先 +1 變成較大的偶數再右移 * 由於多了 +1 的動作，奇數情況的除數並非等同原本的除數，會多除一點使得商相對較小，例如 `1 ÷ 3 = 0.33` 實際上會變成 `1 ÷ 4 = 0.25` * 除數無論奇偶，過程中依舊可能會得到奇數 * 尤其當除數為質數時，如 `5 -> 3 -> 2`、`13 -> 7 -> 4`、`37 -> 19 -> 10 -> 5`、`101 -> 51 -> 26 -> 13` 等等 * 第 9 ~ 10 行： * 除數為奇數時，會將遞迴得到的商再次進行遞迴，主要是為了處理 +1 所造成的誤差 * case 1：`1 ÷ 3` 1. 除數會經過 `3 -> 2 -> 1` 兩次，得到 `1 ÷ 4 = 0.25` 的商 **(第 8 行)** 2. 如果把商乘回原本除數就是 `0.25 × 3 = 0.75`，誤差正好等於商 `0.25` 3. 那要多少個 3 可以填補誤差，也就是在計算 `0.25 ÷ 3`，作法同上 **(第 10 行)** 4. 由於 `0.25 ÷ 3` 一定又會有新的誤差，所以當這誤差小於我們設定的條件 **(第 5 行)** 就會結束了 5. 將全部得到的商相加就是最接近的商了 **(第 10 行)** * case 2：`1 ÷ 5` 1. 除數會經過 `5 -> 3 -> 2 -> 1` 三次，得到 `1 ÷ 8 = 0.125` 的商 **(第 8 行)** 2. 但過程中又經過奇數除數 3 的狀況，也就是當 `0.5 ÷ 3` 時的誤差，`0.125 × 3 = 0.375`，誤差正好是 `0.125` 3. 所以同理又繼續遞迴 `0.125 ÷ 3` **(第 10 行)** 直到終止條件 **(第 5 行)** 4. 到此等同做完一次 ÷ 5，相加得到的商會接近 `0.166...` **(第 10 行)** 5. 把商乘回原本除數 `0.166... × 5 = 0.833...`，誤差再次等於商 `0.166...` 6. 所以同理又繼續遞迴 `0.166... ÷ 5` **(第 10 行)** ，也會再次碰到除數為 3 7. 最終當計算的誤差都小於設定的條件就會結束了 8. 將全部得到的商相加就是最接近的商了 **(第 10 行)** ### 核心概念： 只有相同除數的商才能相加 1. 以 `1 ÷ 5` 為例 2. 當作 `1 ÷ 6` 等價 `0.5 ÷ 3` 3. 當作 `0.5 ÷ 4` 等價 `0.25 ÷ 2` 4. `0.25 ÷ 2` 等價 `0.125 ÷ 1` (4) => (3) 兩邊同乘 2 (3) => (2) 這些 ÷ 4 的商相加，構成了近似 ÷ 3 的商，也就等價回 ÷ 6 (2) => (1) 這些 ÷ 6 的商相加，構成了近似 ÷ 5 的商，也就是解 > 但實際上逼近的過程是根據較大的 2 的次方數，像 ÷ 5 實際上是用 ÷ 8 逼近，÷ 9 則會是 ÷ 16，因為商都是不斷 ÷ 2 得來的 ### 範例： 考慮 `dividend <= 1e-3` * case 1：`1 ÷ 3` ```cpp= dividend: 1.0000000000, divisor: 3 dividend: 0.5000000000, divisor: 2 dividend: 0.2500000000, divisor: 1 result: 0.2500000000 dividend: 0.2500000000, divisor: 3 dividend: 0.1250000000, divisor: 2 dividend: 0.0625000000, divisor: 1 result: 0.0625000000 result: 0.0156250000 result: 0.0039062500 result: 0.0009765625 dividend: 0.0009765625, divisor: 3 // <= 1e-4 final: 0.3339843750 // result 總和 ``` * case 2：`1 ÷ 5` ```cpp= dividend: 1.0000000000, divisor: 5 // 對應到 22 行 ---------------------------------- dividend: 0.5000000000, divisor: 3 dividend: 0.2500000000, divisor: 2 dividend: 0.1250000000, divisor: 1 result: 0.1250000000 dividend: 0.1250000000, divisor: 3 // 處理 3 情況 dividend: 0.0625000000, divisor: 2 dividend: 0.0312500000, divisor: 1 result: 0.0312500000 dividend: 0.0312500000, divisor: 3 dividend: 0.0156250000, divisor: 2 dividend: 0.0078125000, divisor: 1 result: 0.0078125000 result: 0.0019531250 result: 0.0009765625 result: 0.1679687500 // 第一輪 ÷ 5 的商 ---------------------------------- dividend: 0.1679687500, divisor: 5 // 對應到 40 行 ---------------------------------- dividend: 0.0839843750, divisor: 3 dividend: 0.0419921875, divisor: 2 dividend: 0.0209960938, divisor: 1 result: 0.0209960938 dividend: 0.0209960938, divisor: 3 dividend: 0.0104980469, divisor: 2 dividend: 0.0052490234, divisor: 1 result: 0.0052490234 result: 0.0013122559 result: 0.0006561279 result: 0.0288696289 // 第二輪誤差的商 ---------------------------------- dividend: 0.0288696289, divisor: 5 ---------------------------------- dividend: 0.0144348145, divisor: 3 dividend: 0.0072174072, divisor: 2 dividend: 0.0036087036, divisor: 1 result: 0.0036087036 dividend: 0.0036087036, divisor: 3 dividend: 0.0018043518, divisor: 2 dividend: 0.0009021759, divisor: 1 result: 0.0009021759 result: 0.0054130554 // 第三輪誤差的商 ---------------------------------- dividend: 0.0054130554, divisor: 5 ---------------------------------- dividend: 0.0027065277, divisor: 3 dividend: 0.0013532639, divisor: 2 dividend: 0.0006766319, divisor: 1 result: 0.0006766319 dividend: 0.0006766319, divisor: 3 // <= 1e-4 result: 0.0013532639 // 第四輪誤差的商 ---------------------------------- dividend: 0.0013532639, divisor: 5 ---------------------------------- dividend: 0.0006766319, divisor: 3 // <= 1e-4 result: 0.0006766319 // 第五輪誤差的商 ---------------------------------- dividend: 0.0006766319, divisor: 5 // <= 1e-4 final: 0.2049579620 // result 總和 ```