C 語言不調用庫函數實現平方根：二分法與牛頓迭代法完整對比

問題重述

輸入任意正數 n，不使用 `sqrt()`、`math.h` 庫函數，僅用基本算術與循環計算平方根。

方法一：二分法 (Binary Search)

原理：平方根在 [0, n] (n≥1) 或 [0, 1] (n<1) 區間單調遞增，反覆縮小區間。
代碼：

#include <stdio.h>

double sqrt_binary(double n) {
    if (n < 0) return -1; // 錯誤處理
    if (n == 0 || n == 1) return n;
    
    double low = 0, high = (n >= 1) ? n : 1;
    double mid, eps = 1e-10; // 精度閾值
    
    while (high - low > eps) {
        mid = (low + high) / 2;
        if (mid * mid > n)
            high = mid;
        else
            low = mid;
    }
    return (low + high) / 2;
}

int main() {
    double x;
    printf("輸入正數: ");
    scanf("%lf", &x);
    printf("√%.6f ≈ %.10f\n", x, sqrt_binary(x));
    return 0;
}

優點：邏輯簡單、保證收斂、易於理解區間縮小過程。
缺點：收斂速度線性 (每輪精度翻倍)，需 ~30-40 次迭代達雙精度極限。

方法二：牛頓迭代法 (Newton-Raphson) - 推薦

原理：求解 f(x) = x² - n = 0 的根。切線迭代公式：
x_{k+1} = x_k - f(x_k)/f'(x_k) = (x_k + n/x_k) / 2
代碼：

double sqrt_newton(double n) {
    if (n < 0) return -1;
    if (n == 0) return 0;
    
    double x = n; // 初始猜測，也可用 n/2 或 1
    double prev;
    do {
        prev = x;
        x = (x + n / x) * 0.5;
    } while (x != prev && (x - prev > 1e-15 || prev - x > 1e-15)); // 雙精度收斂判斷
    return x;
}

優點：二次收斂 (正確位數每輪翻倍)，通常 5-6 次迭代達雙精度極限，速度極快。
缺點：初始值極差時可能震盪，除零風險 (x=0)，需邊界保護。

方法三：快速逆平方根 (Fast Inverse Sqrt) - 經典圖形學技巧

Quake III 著名的 `0x5f3759df` 魔數法，僅供了解，現代 CPU `sqrtss` 指令已更快。

float inv_sqrt_quake(float x) {
    float xhalf = 0.5f * x;
    int i = *(int*)&x; // 位模式視為整數
    i = 0x5f3759df - (i >> 1); // 魔數近似
    x = *(float*)&i;
    x = x * (1.5f - xhalf * x * x); // 一次牛頓修正
    return x;
}
// 平方根 = x * inv_sqrt(x)

精度與邊界測試

void test() {
    double cases[] = {0, 0.25, 1, 2, 3.14159, 100, 1e-6, 1e6};
    for (double v : cases) {
        double b = sqrt_binary(v);
        double n = sqrt_newton(v);
        double std = sqrt(v); // 僅用於驗證
        printf("√%-10.6f  二分:%-.10f  牛頓:%-.10f  標準:%-.10f  差異:%e\n", 
               v, b, n, std, n - std);
    }
}

輸出顯示牛頓法誤差通常在 1e-15 級別 (雙精度極限)，二分法受 `eps` 限制約 1e-10。

工程落地建議

1. 生產代碼直接用 `sqrt()`：編譯器會內聯為硬件指令 (`sqrtss`/`sqrtsd`)，經過 IEEE 754 驗證、處理亞正規數/特殊值、性能最優。
2. 教學/面試/嵌入式無 FPU：首選牛頓法，注意定點數實現 (Q 格式) 避免浮點開銷。
3. 區間縮小初始猜測：利用 `frexp` 獲取指數部分，`x = ldexp(1, exp/2)` 作為牛頓法初始值，進一步減少迭代次數。