整數開方算法：二分法遞近求解（精度可控、無庫依賴）

問題描述

求實數 N ≥ 0 的平方根，精度要求 |x² - N| ≤ 0.001。不使用 sqrt 庫函數。

二分法核心邏輯

1. 確定搜索區間：
   　　N > 1 → [1, N]；
   　　N < 1 → [N, 1]（因 √N > N）。
2. 中點 mid = (low + high) / 2，計算 mid²。
3. 比較 mid² 與 N：
   　　差值在精度內 → 返回 mid；
   　　mid² > N → high = mid；
   　　mid² < N → low = mid。
4. 循環直到收斂。

完整代碼（C99）

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 

#define EPS 0.001 

double my_sqrt(double n) { 
    if (n < 0) return -1; // 域錯誤 
    double low = (n > 1) ? 1 : n; 
    double high = (n > 1) ? n : 1; 
    double mid; 

    while (low <= high) { 
        mid = (low + high) / 2.0; 
        double sq = mid * mid; 
        double diff = sq - n; 
        if (diff <= EPS && diff >= -EPS) 
            return mid; 
        else if (diff > 0) 
            high = mid; 
        else 
            low = mid; 
    } 
    return mid; // 理論上不會走到這裡 
} 

int main() { 
    double n; 
    while (scanf("%lf", &n) == 1) { 
        printf("%.6f\n", my_sqrt(n)); 
    } 
    return 0; 
}

關鍵點

• 區間初始化覆蓋 0 < N < 1 情況，避免邏輯漏洞。
• 精度判斷用雙向不等式 |mid² - N| ≤ EPS，避免浮點誤差導致死循環。
• 收斂速度：二分法每輪壓縮區間一半，log2((high-low)/EPS) 輪即達標。對 N=1e9, EPS=1e-3 約 40 輪。
• 邊界：N=0 直接返回 0；N=1 返回 1。

擴展：牛頓迭代法（收斂更快）

double newton_sqrt(double n) { 
    if (n <= 0) return 0; 
    double x = n; 
    do { 
        double prev = x; 
        x = 0.5 * (x + n / x); 
        if (fabs(x - prev) < EPS) break; 
    } while (1); 
    return x; 
}

牛頓法二次收斂，通常 5~6 次迭代達到 1e-6 精度，工程首選。

總結

二分法邏輯簡單、邊界清晰、無除法溢出風險，適合教學與嵌入式無 FPU 場景。牛頓法收斂快、代碼極短，適合通用高性能計算。本文整理自 51CTO 博客「整數開方算法」。