C++の二分探索で指定された精度の平方根を求める方法

正の数 n と精度 p が与えられたとき、二分探索(バイナリサーチ)の手法を用いて、小数点以下 p 桁までの n の平方根を求める方法を解説します。例えば、n = 50、p = 3 の場合、出力は 7.071 となります。

アルゴリズムの手順

• 探索範囲を start := 0、end := n として初期化します。
• 中央値 mid の二乗と対象の数を比較します。一致していれば整数部が確定し、mid の二乗が小さければ右側へ、大きければ左側へ探索範囲を絞り込みます。
• 整数部の計算が完了したら、続いて小数部の計算に進みます。
• 増分変数を 0.1 で初期化し、小数部を p 桁まで順に計算します。各反復のたびに増分は前の値の 1/10 に縮小されます。
• 最終的な結果を返します。

サンプルコード

#include<iostream>
using namespace std;
float sqrtBinarySearch(int num, int p) {
    int left = 0, right = num;
    int mid;
    float res;
    while (left <= right) {
        mid = (left + right) / 2;
        if (mid * mid == num) {
            res = mid;
            break;
        }
        if (mid * mid < num) {
            left = mid + 1;
            res = mid;
        } else {
            right = mid - 1;
        }
    }
    float incr = 0.1;
    for (int i = 0; i < p; i++) {
        while (res * res <= num) {
            res += incr;
        }
        res -= incr;
        incr /= 10;
    }
    return res;
}
int main() {
    int n = 50, p = 3;
    cout << "Square root of " << n << " up to precision " << p << " is: " << sqrtBinarySearch(50, 3) << endl;
}

実行結果

Square root of 50 up to precision 3 is: 7.071

コードの解説

このアルゴリズムは大きく2つの段階に分かれています。

第1段階(整数部の探索)： left と right の中央値 mid を取り、mid の二乗と num を比較します。二分探索により、平方が num を超えない最大の整数が効率的に求まります。例えば n = 50 の場合、整数部は 7 となります。

第2段階(小数部の計算)： 増分 incr を 0.1 から始め、res の二乗が num を超えるまで res を加算し続けます。超えた時点で1つ分戻し、増分を 1/10 に縮小して次の桁へ進みます。この処理を p 回繰り返すことで、小数点以下 p 桁までの精度が得られます。

この手法は標準ライブラリの sqrt 関数に頼らず、二分探索の考え方を数値計算に応用した良い例であり、計算量は O(log n) と効率的です。