math.gcd-lcm

Imports name this capability’s declared dependencies, which fune builds next to it in your project; each one links to its page.

use super::funejson::Value;  ← the fune runtime: the JSON value the test vectors use; fune build keeps it only where a signature takes one

const MAX_SAFE: i64 = 9_007_199_254_740_991;

fn check_safe(name: &str, value: i64) {
    // i64 could go further, but TypeScript cannot, and the three languages
    // must give the same answer or the same error.
    if !(-MAX_SAFE..=MAX_SAFE).contains(&value) {
        panic!("{} is outside the safe integer range (±9007199254740991)", name);
    }
}

/// Euclid's algorithm on wide integers. Never negative; `gcd_wide(0, 0)` is 0.
pub fn gcd_wide(a: i128, b: i128) -> i128 {
    let mut x = a.abs();
    let mut y = b.abs();
    while y != 0 {
        let r = x % y;
        x = y;
        y = r;
    }
    x
}

/// # Panics
/// Panics if either input is outside ±(2^53 - 1).
pub fn gcd(a: i64, b: i64) -> i64 {
    check_safe("a", a);
    check_safe("b", b);
    gcd_wide(a as i128, b as i128) as i64
}

/// # Panics
/// Panics if either input is outside ±(2^53 - 1), or the lcm is.
pub fn lcm(a: i64, b: i64) -> i64 {
    let g = gcd(a, b);
    if g == 0 {
        return 0;
    }
    // Divide before multiplying: a * b overflows long before the lcm does.
    let result = (a as i128).abs() / (g as i128) * (b as i128).abs();
    if result > MAX_SAFE as i128 {
        panic!("the lcm of {} and {} exceeds 2^53 - 1", a, b);
    }
    result as i64
}

/// Greatest common divisor and least common multiple of two integers.
///
/// Both are returned together because a caller needing one nearly always
/// needs the other (common denominators, repeating schedules).
///
/// # Panics
/// Panics if either input is outside ±(2^53 - 1), or the lcm is.
pub fn gcd_lcm(a: i64, b: i64) -> GcdLcm {
    GcdLcm {
        gcd: gcd(a, b),
        lcm: lcm(a, b),
    }
}

pub fn gcd_lcm_to_value(result: &GcdLcm) -> Value {
    Value::obj(vec![
        ("gcd", Value::Int(result.gcd)),
        ("lcm", Value::Int(result.lcm)),
    ])
}

pub fn fune_vector(args: &[Value]) -> Value {
    // Refuse what the typed signature cannot hold, with the wording TypeScript
    // and Python use, rather than let the conversion below quietly change it.
    if let Value::Float(f) = args[0] {
        if f.fract() != 0.0 {
            panic!("a must be an integer, received {}", f);
        }
    }
    if let Value::Float(f) = args[1] {
        if f.fract() != 0.0 {
            panic!("b must be an integer, received {}", f);
        }
    }
    gcd_lcm_to_value(&gcd_lcm(args[0].as_i64(), args[1].as_i64()))
}