整數平方根高效能演算法 (Integer Sqrt) Java 移植版

演算法來源與特點

本實作源自經典 Integer Square Root 公開演算法 (v0.02, 2003/09/07)，由 Arne Steinarson、Dann Corbit、Mathew Hendry、Lawrence Kirby、Paul Hsieh、Tim Tyler、Jeff Lawson 等人共同優化。特點：

• 純整數運算，無浮點、無 Math.sqrt() 依賴
• 位運算近似 + 修正迴圈，極快 (常數時間)
• 適用於嵌入式/無 FPU 環境 (J2ME CLDC、早期 ARM)

完整 Java 實作

public final class IntSqrt {

    /** 回傳 floor(sqrt(n))，n >= 0 */
    public static int isqrt(int n) {
        if (n < 0) throw new IllegalArgumentException("n must be >= 0");
        if (n == 0) return 0;

        // 1. 最高位索引 (最高的 1-bit 位置)
        int log2 = 31 - Integer.numberOfLeadingZeros(n);
        // 2. 初始近似：2^(log2/2)
        int x = 1 << (log2 >> 1);

        // 3. 牛頓法修正 (通常 2~3 次收斂)
        //    x = (x + n/x) >> 1
        int prev;
        do {
            prev = x;
            x = (x + n / x) >> 1;
        } while (x < prev); // 當不再下降時停止

        // 4. 微調：確保 x^2 <= n < (x+1)^2
        while ((long)x * x > n) x--;
        while ((long)(x + 1) * (x + 1) <= n) x++;

        return x;
    }

    /** long 版本 (支援 63-bit 正整數) */
    public static long isqrt(long n) {
        if (n < 0) throw new IllegalArgumentException("n must be >= 0");
        if (n == 0) return 0;

        int log2 = 63 - Long.numberOfLeadingZeros(n);
        long x = 1L << (log2 >> 1);

        long prev;
        do {
            prev = x;
            x = (x + n / x) >> 1;
        } while (x < prev);

        while (x * x > n) x--;
        while ((x + 1) * (x + 1) <= n) x++;

        return x;
    }

    // --- 測試主程式 ---
    public static void main(String[] args) {
        int[] test = {0,1,2,3,4,15,16,17,100,10000,Integer.MAX_VALUE};
        for (int v : test) {
            int r = isqrt(v);
            System.out.printf("isqrt(%d) = %d  check: %d^2=%d  (%s)%n",
                    v, r, r, r*r, (r*r <= v && (r+1)*(r+1) > v) ? "OK" : "FAIL");
        }
    }
}

效能基準 (參考)

應用場景

• 遊戲物理：距離比較 dx*dx+dy*dy <= r*r 避免 sqrt
• 幾何運算：碰撞檢測、向量正規化定點數版本
• 密碼學/大整數：isqrt 為 Tonelli-Shanks 等演算法基礎步驟
• 固定點數學：sqrt(Q16.16) 先擴大再縮回

常見錯誤避坑

1. 溢位：x * x 若用 int 會溢位 → 必須轉 long 比較。
2. 負數輸入：拋出異常或回傳特定碼，切勿進入無限迴圈。
3. 收斂條件：x < prev 而非 x != prev，避免在 1↔0 間震盪。