小数から近い分数を求める

memomathematics

例えば、双方向プログラミング的なもので、数値をスライダーで調整できるようになっていた場合、実際のところは5/7とかわかりやすい有理数だったりとか、整数に近い値を表したいのにめちゃくちゃ長い小数点の数値が残ったりする。

これを、適当なグリッドにスナップするUIの一つとして、許容できる誤差範囲と整数の複雑さを指定して分数に変換するのが良いのではないか。

ChatGPTに聞いた。連分数展開というのを使うと良いらしい。Rustのコードを書いてもらった。

/// 任意の実数 x を近似する収束分数・半収束分数を求める
///   x: 近似したい実数
///   eps: 絶対誤差許容値
///   max_den: 分母の上限
///   max_num: 分子の上限
fn rational_approx(
    x: f64,
    eps: f64,
    max_den: u64,
    max_num: u64,
) -> Vec<(u64, u64)> {
    // 連分数展開の a_k リストを構築
    let mut a: Vec<u64> = Vec::new();
    let mut r = x;
    for _ in 0..64 {
        let ak = r.floor() as u64;
        a.push(ak);
        let frac = r - (ak as f64);
        if frac.abs() < f64::EPSILON {
            break;
        }
        r = 1.0 / frac;
    }
 
    let mut candidates: Vec<(u64, u64)> = Vec::with_capacity(a.len());
    let (mut p_nm2, mut q_nm2) = (0u128, 1u128);
    let (mut p_nm1, mut q_nm1) = (1u128, 0u128);
 
    for &ak in &a {
        // 収束分数
        let p = ak as u128 * p_nm1 + p_nm2;
        let q = ak as u128 * q_nm1 + q_nm2;
        if q > max_den as u128 { break; }
        let num = p as u64;
        let den = q as u64;
        if num <= max_num {
            let approx = (num as f64) / (den as f64);
            if (x - approx).abs() <= eps {
                candidates.push((num, den));
            }
        }
        // 半収束分数
        for d in 1..=(ak / 2) {
            let ap = ak - d;
            let p2 = ap as u128 * p_nm1 + p_nm2;
            let q2 = ap as u128 * q_nm1 + q_nm2;
            if q2 <= max_den as u128 && p2 <= max_num as u128 {
                let num2 = p2 as u64;
                let den2 = q2 as u64;
                let approx2 = (num2 as f64) / (den2 as f64);
                if (x - approx2).abs() <= eps {
                    candidates.push((num2, den2));
                }
            }
        }
        p_nm2 = p_nm1;
        q_nm2 = q_nm1;
        p_nm1 = p;
        q_nm1 = q;
    }
 
    candidates.sort_by(|&(p1, q1), &(p2, q2)| {
        let e1 = (x - (p1 as f64)/(q1 as f64)).abs();
        let e2 = (x - (p2 as f64)/(q2 as f64)).abs();
        e1.partial_cmp(&e2).unwrap()
    });
    candidates.dedup();
    candidates
}
 
/// x を percent% 精度で近似するラッパー
///   x: 近似したい実数
///   percent: 相対誤差許容値（%）
///   max_num: 分母、分子の上限
fn rational_approx_pct(
    x: f64,
    percent: f64,
    max_num: u64,
) -> Vec<(u64, u64)> {
    let eps = (percent / 100.0) * x.abs();
    rational_approx(x, eps, max_num, max_num)
}
 
fn main() {
    let x = 2.7182818284;
    let percent = 1.0; // 1%
    let max_num = 500;
    let results = rational_approx_pct(x, percent, max_num);
    println!("近似候補（percent={}%）:", percent);
    for (p, q) in results {
        let approx = p as f64 / q as f64;
        let err = (x - approx).abs();
        println!("{}/{} = {:.8}, 誤差 {} ({:.4}%差)",
            p, q, approx, err, err / x.abs() * 100.0);
    }
}
 

近似候補（percent=1%）:
193/71 = 2.71830986, 誤差 0.00002803075492963103 (0.0010%差)
106/39 = 2.71794872, 誤差 0.00033311045128181505 (0.0123%差)
87/32 = 2.71875000, 誤差 0.00046817160000012237 (0.0172%差)
68/25 = 2.72000000, 誤差 0.0017181716000003178 (0.0632%差)
49/18 = 2.72222222, 誤差 0.003940393822222443 (0.1450%差)
19/7 = 2.71428571, 誤差 0.003996114114285465 (0.1470%差)

悪くなさそう（ここから5個ぐらいまでを提示するとして、）