Namaran

Code daily. Without assist.

2026-09-02

root.rs

fn root(f: impl Fn(f64) -> f64, mut lo: f64, mut hi: f64) -> f64 {
    while hi - lo > 1e-9 {
        let mid = (lo + hi) / 2.0;
        if f(mid) < 0.0 {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    lo
}

fn main() {
    println!("{:.6}", root(|x| x * x - 2.0, 0.0, 2.0));
    println!("{:.6}", root(|x| x * x - 2e16, 0.0, 2e8));
}

root は、増加する関数 f について、f(lo) < 0 ≦ f(hi) を保ったまま区間を半分ずつ狭め、f(x) = 0 の解を近似するつもりの関数です。main の1行目は x2 = 2 の解として 1.414214 を表示しますが、2行目の x2 = 2 × 1016 では何も表示されないまま、プログラムが終わりません。本来は2行目に 141421356.237309 と表示されるはずです。

Answer

Wrong

while hi - lo > 1e-9 {

f64 の有効数字は値の大きさによらず2進数で53桁なので、隣り合う f64 の間隔は値の大きさに比例して広がります。2行目の解 1.41 × 108 の付近では、この間隔が約3 × 10−8 で、1e-9 より広くなります。

区間が隣り合う2つの f64 まで縮むと、その間に数はないので、中点 (lo + hi) / 2.0 は lo か hi のどちらかに丸められ、区間はそれ以上縮みません。hi - lo は約3 × 10−8 のまま 1e-9 を下回らないので、ループが終わりません。1行目の解の付近では間隔が約2 × 10−16 なので、同じ条件でも止まります。

Right

for _ in 0..100 {

繰り返しの回数を決めておけば、値の大きさに関係なく必ず終わります。幅 2 × 108 の区間でも、約53回半分にすると隣り合う2つの f64 に達します。そこから先は中点が端に一致し、lo = mid や hi = mid は区間を変えないので、100回まで回しても答えは変わりません1。

  1. 止める条件を hi - lo > 1e-9 * hi.abs() のように値の大きさに比例させる書き方もありますが、解が0に近いと右辺も0に近づき、同じように終わらなくなります。中点が lo か hi に一致した時点で止める書き方なら、回数を決めなくても終わります。