Namaran

Code daily. Without assist.

2026-09-02

halve.rs

fn main() {
    let (lo, hi) = (0..4).fold((1.0, 2.0), |(lo, hi), _| {
        let mid = (lo + hi) / 2.0;
        if mid * mid > 2.0 { (lo, mid) } else { (mid, hi) }
    });
    println!("{lo} {hi}");
}

これは何を出力するでしょうか?

Answer

1.375 1.4375 です。

fold は (1.0, 2.0) から始めて、範囲 0..4 の要素の数だけ、つまり4回クロージャを呼び、返ってきた組を次の (lo, hi) にします。クロージャは区間の中点 mid の2乗を2と比べ、2より大きければ x2 = 2 の正の解は mid より左にあるので (lo, mid) を、そうでなければ (mid, hi) を返します。

1回目は mid が1.5で、2乗の2.25が2より大きいので (1, 1.5) が残ります。2回目は1.25で2乗が1.5625なので (1.25, 1.5)、3回目は1.375で2乗が1.890625なので (1.375, 1.5) です。4回目の1.4375は2乗が2.06640625で2を超えるので、hi の側が縮んで (1.375, 1.4375) になります。どの値も分母が2の累乗の分数なので f64 で誤差なく表せ、そのまま 1.375 と 1.4375 が表示されます。

区間を半分ずつ狭めて解に近づくこの方法を、二分法(bisection method)といいます。√2 = 1.41421… は常に残した区間の中にあり、4回で区間の幅は1から1/16まで縮みます。