#51 √2の近似値を二分法で計算してみた

概要

√2の近似値を二分法で計算してみようと思います。√2に限らず、JavaScriptで表せる任意の正の実数であれば同じように計算できます

手順

以下の手順で近似値を求めます

1. 最小値と最大値の中間値を求める

2. 1で求めた値が目的の値より小さい場合は最小値を、大きい場合は最大値を1で求めた値に置き換える

3. 任意の精度(※)に達していなければ1に戻る

※JavaScriptではNumber.EPSILON(2^-52)より小さな差を表現できないので、今回はそこを目標にします

実装

2の平方根は2より小さいことが知られているので、

• 最小値: 0

• 最大値: 2

を初期値として設定し、計算を行います

let targetNumber = 2;
let min = 0;
let max = 2;
let count = 0;

//もし誤差が小さければループを抜ける
while (!((max - Number.EPSILON) - (min + Number.EPSILON) <= Number.EPSILON)) {
    //最小値と最大値の中間を求める
    let sqrt = (min + max) / 2;

    //√2の候補を2乗する
    let t2 = sqrt ** 2;

    //もし中間値が目的値より小さいなら範囲の最小値を更新、そうでないなら最大値を更新
    if (t2 < targetNumber) {
        min = sqrt;
    }
    else {
        max = sqrt;
    }

    count++;
    console.log(`count: ${count}`);
    console.log(`√${targetNumber} ≒ ${min}～${max}`);
}

実行結果

実行結果として

count: 1
√2 ≒ 1～2
count: 2
√2 ≒ 1～1.5
count: 3
√2 ≒ 1.25～1.5
count: 4
√2 ≒ 1.375～1.5
count: 5
√2 ≒ 1.375～1.4375
count: 6
√2 ≒ 1.40625～1.4375
count: 7
√2 ≒ 1.40625～1.421875
count: 8
√2 ≒ 1.4140625～1.421875
count: 9
√2 ≒ 1.4140625～1.41796875
count: 10
√2 ≒ 1.4140625～1.416015625
count: 11
√2 ≒ 1.4140625～1.4150390625
count: 12
√2 ≒ 1.4140625～1.41455078125
count: 13
√2 ≒ 1.4140625～1.414306640625
count: 14
√2 ≒ 1.4141845703125～1.414306640625
count: 15
√2 ≒ 1.4141845703125～1.41424560546875
count: 16
√2 ≒ 1.4141845703125～1.414215087890625
count: 17
√2 ≒ 1.4141998291015625～1.414215087890625
count: 18
√2 ≒ 1.4142074584960938～1.414215087890625
count: 19
√2 ≒ 1.4142112731933594～1.414215087890625
count: 20
√2 ≒ 1.4142131805419922～1.414215087890625
count: 21
√2 ≒ 1.4142131805419922～1.4142141342163086
count: 22
√2 ≒ 1.4142131805419922～1.4142136573791504
count: 23
√2 ≒ 1.4142134189605713～1.4142136573791504
count: 24
√2 ≒ 1.4142135381698608～1.4142136573791504
count: 25
√2 ≒ 1.4142135381698608～1.4142135977745056
count: 26
√2 ≒ 1.4142135381698608～1.4142135679721832
count: 27
√2 ≒ 1.414213553071022～1.4142135679721832
count: 28
√2 ≒ 1.4142135605216026～1.4142135679721832
count: 29
√2 ≒ 1.4142135605216026～1.414213564246893
count: 30
√2 ≒ 1.4142135605216026～1.4142135623842478
count: 31
√2 ≒ 1.4142135614529252～1.4142135623842478
count: 32
√2 ≒ 1.4142135619185865～1.4142135623842478
count: 33
√2 ≒ 1.4142135621514171～1.4142135623842478
count: 34
√2 ≒ 1.4142135622678325～1.4142135623842478
count: 35
√2 ≒ 1.4142135623260401～1.4142135623842478
count: 36
√2 ≒ 1.414213562355144～1.4142135623842478
count: 37
√2 ≒ 1.4142135623696959～1.4142135623842478
count: 38
√2 ≒ 1.4142135623696959～1.4142135623769718
count: 39
√2 ≒ 1.4142135623696959～1.4142135623733338
count: 40
√2 ≒ 1.4142135623715149～1.4142135623733338
count: 41
√2 ≒ 1.4142135623724243～1.4142135623733338
count: 42
√2 ≒ 1.414213562372879～1.4142135623733338
count: 43
√2 ≒ 1.414213562372879～1.4142135623731065
count: 44
√2 ≒ 1.4142135623729928～1.4142135623731065
count: 45
√2 ≒ 1.4142135623730496～1.4142135623731065
count: 46
√2 ≒ 1.414213562373078～1.4142135623731065
count: 47
√2 ≒ 1.4142135623730923～1.4142135623731065
count: 48
√2 ≒ 1.4142135623730923～1.4142135623730994
count: 49
√2 ≒ 1.4142135623730923～1.4142135623730958
count: 50
√2 ≒ 1.414213562373094～1.4142135623730958
count: 51
√2 ≒ 1.414213562373095～1.4142135623730958
count: 52
√2 ≒ 1.414213562373095～1.4142135623730954

という結果が求められました

まとめ

JavaScriptでは倍精度浮動小数点数しか扱えないため、16桁程度の精度までしか求めることができませんでした

次回は任意精度での計算に挑戦してみようと思います