math.fractional-power

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
use super::math_big_integer::{parse_big_integer, BigInt};  ← from math.big-integer ^1.0.0 · built alongside by fune

/// Intermediate values beyond 2^512 (about 10^136 after scaling) are refused.
const MAX_BITS: u64 = 512;

/// Every value is held as an integer count of 10^-18.
pub fn fixed_scale() -> BigInt {
    BigInt::from_i64(1_000_000_000_000_000_000)
}

fn too_large(value: &BigInt) -> bool {
    value.bit_length() > MAX_BITS
}

/// Product of two non-negative fixed-point values, floored.
pub fn mul_fixed(a: &BigInt, b: &BigInt) -> BigInt {
    // Dividing by 10^9 twice floors exactly as dividing by 10^18 once does.
    a.mul(b).div_rem_small(1_000_000_000).0.div_rem_small(1_000_000_000).0
}

/// x^n for a non-negative fixed-point x, by square-and-multiply from the
/// lowest bit, flooring after every product. The order of operations is part
/// of the contract: it is what makes TypeScript, Python and Rust agree to the
/// last digit. Returns bound + 1 as soon as the result must exceed `bound`
/// (x >= 1 only grows), so a bisection never builds an astronomically large
/// number.
///
/// # Panics
/// Panics if an intermediate value passes 2^512.
pub fn pow_fixed_bounded(x: &BigInt, n: u64, bound: Option<&BigInt>) -> BigInt {
    let scale = fixed_scale();
    let grows = *x >= scale;
    let mut result = scale.clone();
    let mut base = x.clone();
    let mut e = n;
    while e > 0 {
        if e % 2 == 1 {
            result = mul_fixed(&result, &base);
            if let Some(b) = bound {
                if grows && result > *b {
                    return b.add(&BigInt::from_i64(1));
                }
            }
        }
        e /= 2;
        if e > 0 {
            base = mul_fixed(&base, &base);
            if let Some(b) = bound {
                if grows && base > *b {
                    return b.add(&BigInt::from_i64(1));
                }
            }
            if too_large(&base) {
                panic!("fractional power result too large");
            }
        }
    }
    if too_large(&result) {
        panic!("fractional power result too large");
    }
    result
}

/// x^n in fixed point.
pub fn pow_fixed(x: &BigInt, n: u64) -> BigInt {
    pow_fixed_bounded(x, n, None)
}

/// The q-th root of x in fixed point: the largest y with pow_fixed(y, q) <= x,
/// found by bisection.
pub fn root_fixed(x: &BigInt, q: u64) -> BigInt {
    if q == 1 {
        return x.clone();
    }
    let scale = fixed_scale();
    let one = BigInt::from_i64(1);
    let two = BigInt::from_i64(2);
    let mut lo = BigInt::zero();
    // For x >= 1, (1 + (x - 1)/q)^q >= x (Bernoulli), so the root is below it.
    let mut hi = if *x >= scale {
        scale.add(&x.sub(&scale).div(&BigInt::from_i64(q as i64))).add(&two)
    } else {
        scale.add(&one)
    };
    while hi.sub(&lo) > one {
        let mid = lo.add(&hi).div(&two);
        if pow_fixed_bounded(&mid, q, Some(x)) <= *x {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    lo
}

/// x^(p/q) in fixed point: the q-th root first, then the power, then the
/// reciprocal if p < 0.
///
/// # Panics
/// Panics on an exponent out of range, a base of zero or less, or a result
/// too large to hold.
pub fn fractional_power_fixed(x: &BigInt, p: i64, q: i64) -> BigInt {
    if p < -100000 || p > 100000 {
        panic!("exponentNumerator must be between -100000 and 100000, received {}", p);
    }
    if q < 1 || q > 100000 {
        panic!("exponentDenominator must be between 1 and 100000, received {}", q);
    }
    if *x <= BigInt::zero() {
        panic!("base must be greater than zero");
    }
    let root = root_fixed(x, q as u64);
    if p >= 0 {
        return pow_fixed(&root, p as u64);
    }
    let denominator = pow_fixed(&root, (-p) as u64);
    if denominator.is_zero() {
        panic!("fractional power result too large");
    }
    let scale = fixed_scale();
    let result = scale.mul(&scale).div(&denominator);
    if too_large(&result) {
        panic!("fractional power result too large");
    }
    result
}

/// Parse a non-negative decimal of at most 18 places into fixed point.
///
/// # Panics
/// Panics on anything else.
pub fn parse_fixed(text: &str) -> BigInt {
    let (whole, fraction) = match text.split_once('.') {
        Some((w, f)) => (w, Some(f)),
        None => (text, None),
    };
    let valid = !whole.is_empty()
        && whole.bytes().all(|b| b.is_ascii_digit())
        && match fraction {
            None => true,
            Some(f) => !f.is_empty() && f.len() <= 18 && f.bytes().all(|b| b.is_ascii_digit()),
        };
    if !valid {
        panic!(
            "base must be a positive decimal with at most 18 places, received \"{}\"",
            text
        );
    }
    let mut digits = whole.trim_start_matches('0').to_string();
    let mut padded = fraction.unwrap_or("").to_string();
    while padded.len() < 18 {
        padded.push('0');
    }
    digits.push_str(&padded);
    let digits = digits.trim_start_matches('0');
    if digits.is_empty() {
        return BigInt::zero();
    }
    parse_big_integer(digits)
}

/// base^(exponent_numerator / exponent_denominator), to 12 decimal places.
///
/// Computed in 18-place fixed point with a floor after every step, then
/// rounded half-up to 12 places, so the last digit printed is right unless the
/// true value sits within about 10^-15 of a rounding boundary.
pub fn fractional_power(base: &str, exponent_numerator: i64, exponent_denominator: i64) -> String {
    let x = parse_fixed(base);
    let value = fractional_power_fixed(&x, exponent_numerator, exponent_denominator);
    let (rounded, _) = value.add(&BigInt::from_i64(500_000)).div_rem_small(1_000_000);
    let (whole, fraction) = rounded.div_rem(&BigInt::from_i64(1_000_000_000_000));
    format!("{}.{:012}", whole, fraction.to_i64())
}

pub fn fune_vector(args: &[Value]) -> Value {
    Value::str(&fractional_power(
        args[0].as_str(),
        args[1].as_i64(),
        args[2].as_i64(),
    ))
}