浮點數除法程式

假設 divop() 的第二個參數也就是除數，必為大於 0 的整數












#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 ÷ 5 為例
當作 1 ÷ 6 等價 0.5 ÷ 3
當作 0.5 ÷ 4 等價 0.25 ÷ 2
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


















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








































































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 總和

浮點數除法程式

程式說明：

核心概念：

範例：

Read more

物聯網環境建置與測試