He Chengtian's inequality implementation in TypeScript and Rust as a function that finds the closest integer ratio to a given target number

inequality-approximation.rs

#![feature(gen_blocks)]

use std::fmt::{Debug, Display, Formatter};

struct Ratio {
    pub a: i32,
    pub b: i32,
}

impl Display for Ratio {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}/{}", self.a, self.b)
    }
}

macro_rules! calc {
    ($ratio: expr) => {f64::from($ratio.a) / f64::from($ratio.b)};
}

impl Ratio {
    pub fn new(a: i32) -> Ratio {
        Ratio { a, b: 1 }
    }

    pub fn copy(other: &Ratio) -> Ratio {
        Ratio { a: other.a, b: other.b }
    }
}

/// He Chengtian's inequality approximation
///
/// Given a/b < x < c/d,
/// a+c/b+d approaches x.
fn find_ratios(target: &f64) -> impl Iterator<Item = Ratio> {
    gen {
        let target_ratio = *target;
        let mut start = Ratio::new(target.floor() as i32);
        let mut end = Ratio::new(target.ceil() as i32);

        fn approx_fraction(left: &Ratio, right: &Ratio) -> Ratio {
            Ratio {
                a: left.a + right.a,
                b: left.b + right.b,
            }
        }

        let mut min_diff = f64::INFINITY;

        loop {
            let ratio = approx_fraction(&start, &end);
            let diff = calc!(&ratio) - &target_ratio;
            let abs_diff = diff.abs();

            if abs_diff < min_diff {
                min_diff = abs_diff;
                yield Ratio::copy(&ratio);
            }

            if min_diff == 0.0 {
                break;
            }

            if diff < 0.0 {
                start = Ratio::copy(&ratio);
            } else {
                end = Ratio::copy(&ratio);
            }
        };
    }
}

fn get_accuracy(target: f64, result: f64) -> usize {
    let str_target = target.to_string();
    let str_result = result.to_string();
    let len = str_target.len();

    for i in 0..len {
        if str_result.chars().nth(i) != str_target.chars().nth(i) {
            return i - 1;
        }
    }

    len - 1
}

struct RatioInfo {
    accuracy: usize,
    ratio: Ratio,
    result: f64,
    iteration: usize,
}

impl Display for RatioInfo {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "i:{}\taccuracy: {}\t| {} |\tresult: {}", self.iteration, self.accuracy, self.ratio, self.result)
    }
}

fn main() {
    let nums = vec![
        std::f64::consts::PI,
        std::f64::consts::E,
        0.122377112,
        607.7692307692307
    ];

    for num in nums {
        println!("Ratios for {num}:");

        let mut accuracy: usize = 0;

        let ratios_info = find_ratios(&num)
            .enumerate()
            .filter_map(|(i, ratio)| {
                let result = calc!(ratio);

                let _accuracy = get_accuracy(num, result);

                if _accuracy > accuracy {
                    accuracy = _accuracy;
                } else if result != num {
                    return None;
                }

                Some(RatioInfo {
                    iteration: i,
                    accuracy: _accuracy,
                    result,
                    ratio
                })
            });

        for info in ratios_info {
            println!("{info}");
        }

        println!("---------------\n")
    }
}

inequality-approximation.ts

/**
 * He Chengtian's inequality approximation
 * 
 * Given a/b < x < c/d,
 * a+c/b+d approaches x.
 * 
 * @param target x
 * @param start a/b
 * @param end c/d
 * @param [useDiv=true] whether to use the division operator for a natural comparison
 * instead of cross-multiplication
 * 
 * Not using division can lead to algorithm diverging into infinity due to limited precision of IEEE 754 fp,
 * but works faster in general (less yields).
 * 
 * @returns ratio generator which gets closer to the target value with each iteration
 */
function* findRatio(
  target: number,
  options?: {
    start?: Ratio;
    end?: Ratio;
    useDiv?: boolean;
  }
) {
  let {
    start = Ratio(Math.floor(target)),
    end = Ratio(Math.ceil(target)),
    useDiv = true,
  } = options || {};

  // If the fractions are out of order, flip the values
  if (compare(start, end) < 0) {
    [start, end] = [end, start];
  }

  const approxFraction = (_left: Ratio, _right: Ratio) => ({
    a: (_left.a + _right.a),
    b: (_left.b + _right.b)
  });

  let minDiff = Infinity;

  while (true) {
    const ratio = approxFraction(start, end);

    const difference = compare(ratio, { a: target, b: 1 }, useDiv);

    const absDiff = Math.abs(difference);

    // Only yield results that actually improve accuraccy
    if (absDiff < minDiff) {
      minDiff = absDiff;
      yield ratio;
    }

    if (difference === 0) {
      // Congrats, we found the exact ratio
      return ratio;
    }

    if (difference > 0) {
      start = ratio;
      /**
       * start                     end
       * |-----X----target---------|
       * |---->^ move start to X
       *       |----target---------|
       */
    } else {
      end = ratio;
      /**
       * start                     end
       * |----------target----X----|
       * move end to X        ^----|
       * |----------target----|
       */
    }
  }
}

/**
 * Compares two Ratio values
 * 
 * @param [useDiv=true] whether to use the division operator for a natural comparison
 * instead of cross-multiplication
 * 
 * @returns a number close to 0
 * - `0` if the values are equal;
 * - positive number if `left` is smaller than `right` (in order);
 * - negative number if `left` is greater than `right` (out of order);
 */
function compare(left: Ratio, right: Ratio, useDiv = true) {
  const crossLeft = useDiv ? left.a/left.b : left.a * right.b;
  const crossRight = useDiv ? right.a/right.b : left.b * right.a;

  return crossRight - crossLeft;
}

/**
 * Simple ratio type, a/b
 */
interface Ratio { a: number, b: number }

function Ratio(a: number, b = 1) {
  if (b === 0) {
    throw new TypeError('Cannot compare undefined ratios');
  }

  return { a, b }
}

function printRatios(target: number, useDiv = true) {
  let processedAcc = 0;

  // Print only the ratios that improve accuracy
  // by readable digits, compared to previous results
  const ratios = findRatio(target, { useDiv })
    .map((ratio, iteration) => {
      const result = ratio.a/ratio.b;

      return {
        accuracy: getAccuracy(target, result),
        frac: `${ratio.a}/${ratio.b}`,
        result,
        iteration,
      };
    })
    .filter(x => {
      if (x.accuracy <= processedAcc) {
        return x.result === target;
      }

      processedAcc = x.accuracy;

      return true;
    });

  console.group('Ratios for ' + target);

  for (const ratio of ratios) {
    console.log(ratio);
  }

  console.groupEnd();

  function getAccuracy(target: number, result: number) {
    const starget = String(target);
    const sresult = String(result);
    const len = starget.length;

    for (let i = 0; i < len; i++) {
      if (sresult[i] !== starget[i]) {
        return i - 1;
      }
    }

    return len - 1;
  }
}

printRatios(Math.PI, false);
printRatios(Math.E, false);
printRatios(3.616347, false);
printRatios(0.122377112, false);
printRatios(12/34, false);
printRatios(7452461/7184502, false);
printRatios(-16802/2621);
printRatios(15802/26);