math.big-integer

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

use std::cmp::Ordering;
use std::fmt;

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

/// The largest result, in bits, that power will build: about 19,700 decimal digits.
pub const MAX_POWER_BITS: u64 = 65536;

/// An integer of any size: sign and magnitude, the magnitude in 32-bit limbs,
/// least significant first, with no high zero limbs. Zero is never negative.
///
/// TypeScript and Python have this built in (`bigint`, `int`); Rust's standard
/// library does not, and the registry takes no crates, so this is the Rust
/// side of the same arithmetic. Schoolbook multiplication and shift-subtract
/// division: quadratic, and fast enough for the few-thousand-digit numbers
/// money and rate calculations reach.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct BigInt {
    negative: bool,
    mag: Vec<u32>,
}

fn trim(v: &mut Vec<u32>) {
    while let Some(&0) = v.last() {
        v.pop();
    }
}

fn mag_cmp(a: &[u32], b: &[u32]) -> Ordering {
    if a.len() != b.len() {
        return a.len().cmp(&b.len());
    }
    for i in (0..a.len()).rev() {
        if a[i] != b[i] {
            return a[i].cmp(&b[i]);
        }
    }
    Ordering::Equal
}

fn mag_add(a: &[u32], b: &[u32]) -> Vec<u32> {
    let n = a.len().max(b.len());
    let mut out = Vec::with_capacity(n + 1);
    let mut carry = 0u64;
    for i in 0..n {
        let x = *a.get(i).unwrap_or(&0) as u64;
        let y = *b.get(i).unwrap_or(&0) as u64;
        let t = x + y + carry;
        out.push(t as u32);
        carry = t >> 32;
    }
    if carry > 0 {
        out.push(carry as u32);
    }
    trim(&mut out);
    out
}

/// a - b for a >= b.
fn mag_sub(a: &[u32], b: &[u32]) -> Vec<u32> {
    let mut out = Vec::with_capacity(a.len());
    let mut borrow = 0i64;
    for i in 0..a.len() {
        let mut t = a[i] as i64 - *b.get(i).unwrap_or(&0) as i64 - borrow;
        if t < 0 {
            t += 1i64 << 32;
            borrow = 1;
        } else {
            borrow = 0;
        }
        out.push(t as u32);
    }
    trim(&mut out);
    out
}

fn mag_mul(a: &[u32], b: &[u32]) -> Vec<u32> {
    if a.is_empty() || b.is_empty() {
        return Vec::new();
    }
    let mut out = vec![0u32; a.len() + b.len()];
    for i in 0..a.len() {
        let mut carry = 0u64;
        let x = a[i] as u64;
        for j in 0..b.len() {
            let t = out[i + j] as u64 + x * b[j] as u64 + carry;
            out[i + j] = t as u32;
            carry = t >> 32;
        }
        out[i + b.len()] = carry as u32;
    }
    trim(&mut out);
    out
}

fn mag_bits(a: &[u32]) -> u64 {
    match a.last() {
        None => 0,
        Some(&top) => (a.len() as u64 - 1) * 32 + (32 - top.leading_zeros() as u64),
    }
}

fn mag_shl(a: &[u32], bits: u64) -> Vec<u32> {
    if a.is_empty() {
        return Vec::new();
    }
    let limbs = (bits / 32) as usize;
    let rem = (bits % 32) as u32;
    let mut out = vec![0u32; limbs];
    if rem == 0 {
        out.extend_from_slice(a);
    } else {
        let mut carry = 0u32;
        for &x in a {
            out.push((x << rem) | carry);
            carry = x >> (32 - rem);
        }
        if carry > 0 {
            out.push(carry);
        }
    }
    trim(&mut out);
    out
}

/// Quotient and remainder of magnitudes, by shift and subtract.
fn mag_divrem(a: &[u32], b: &[u32]) -> (Vec<u32>, Vec<u32>) {
    if b.is_empty() {
        panic!("division by zero");
    }
    if mag_cmp(a, b) == Ordering::Less {
        return (Vec::new(), a.to_vec());
    }
    let shift = mag_bits(a) - mag_bits(b);
    let mut quotient = vec![0u32; (shift / 32 + 1) as usize];
    let mut rest = a.to_vec();
    let mut s = shift as i64;
    while s >= 0 {
        let candidate = mag_shl(b, s as u64);
        if mag_cmp(&rest, &candidate) != Ordering::Less {
            rest = mag_sub(&rest, &candidate);
            quotient[(s / 32) as usize] |= 1u32 << (s % 32);
        }
        s -= 1;
    }
    trim(&mut quotient);
    (quotient, rest)
}

fn mag_divrem_small(a: &[u32], d: u32) -> (Vec<u32>, u32) {
    let mut out = vec![0u32; a.len()];
    let mut rem = 0u64;
    for i in (0..a.len()).rev() {
        let cur = (rem << 32) | a[i] as u64;
        out[i] = (cur / d as u64) as u32;
        rem = cur % d as u64;
    }
    trim(&mut out);
    (out, rem as u32)
}

impl BigInt {
    fn make(negative: bool, mut mag: Vec<u32>) -> BigInt {
        trim(&mut mag);
        let negative = negative && !mag.is_empty();
        BigInt { negative, mag }
    }

    pub fn zero() -> BigInt {
        BigInt { negative: false, mag: Vec::new() }
    }

    pub fn from_i128(value: i128) -> BigInt {
        let mut m = value.unsigned_abs();
        let mut mag = Vec::new();
        while m > 0 {
            mag.push(m as u32);
            m >>= 32;
        }
        BigInt::make(value < 0, mag)
    }

    pub fn from_i64(value: i64) -> BigInt {
        BigInt::from_i128(value as i128)
    }

    pub fn is_zero(&self) -> bool {
        self.mag.is_empty()
    }

    pub fn is_negative(&self) -> bool {
        self.negative
    }

    /// Bits in the magnitude; 0 for zero.
    pub fn bit_length(&self) -> u64 {
        mag_bits(&self.mag)
    }

    pub fn neg(&self) -> BigInt {
        BigInt::make(!self.negative, self.mag.clone())
    }

    pub fn abs(&self) -> BigInt {
        BigInt::make(false, self.mag.clone())
    }

    pub fn add(&self, other: &BigInt) -> BigInt {
        if self.negative == other.negative {
            return BigInt::make(self.negative, mag_add(&self.mag, &other.mag));
        }
        match mag_cmp(&self.mag, &other.mag) {
            Ordering::Equal => BigInt::zero(),
            Ordering::Greater => BigInt::make(self.negative, mag_sub(&self.mag, &other.mag)),
            Ordering::Less => BigInt::make(other.negative, mag_sub(&other.mag, &self.mag)),
        }
    }

    pub fn sub(&self, other: &BigInt) -> BigInt {
        self.add(&other.neg())
    }

    pub fn mul(&self, other: &BigInt) -> BigInt {
        BigInt::make(self.negative != other.negative, mag_mul(&self.mag, &other.mag))
    }

    /// Quotient truncated towards zero, and the remainder with the sign of self.
    ///
    /// # Panics
    /// Panics if `other` is zero.
    pub fn div_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
        let (q, r) = mag_divrem(&self.mag, &other.mag);
        (
            BigInt::make(self.negative != other.negative, q),
            BigInt::make(self.negative, r),
        )
    }

    /// Quotient truncated towards zero.
    pub fn div(&self, other: &BigInt) -> BigInt {
        self.div_rem(other).0
    }

    /// Quotient truncated towards zero by a small positive divisor, and the
    /// remainder of the magnitude. Much faster than `div_rem` for scaling by
    /// powers of ten.
    ///
    /// # Panics
    /// Panics if `divisor` is zero.
    pub fn div_rem_small(&self, divisor: u32) -> (BigInt, u32) {
        if divisor == 0 {
            panic!("division by zero");
        }
        let (q, r) = mag_divrem_small(&self.mag, divisor);
        (BigInt::make(self.negative, q), r)
    }

    /// Remainder with the sign of self.
    pub fn rem(&self, other: &BigInt) -> BigInt {
        self.div_rem(other).1
    }

    /// # Panics
    /// Panics beyond MAX_POWER_BITS, as the other languages do.
    pub fn pow(&self, exponent: u64) -> BigInt {
        if mag_cmp(&self.mag, &[1]) != Ordering::Greater {
            if exponent == 0 {
                return BigInt::from_i64(1);
            }
            if self.negative {
                return BigInt::from_i64(if exponent % 2 == 0 { 1 } else { -1 });
            }
            return self.clone();
        }
        if (self.bit_length() as u128) * (exponent as u128) > MAX_POWER_BITS as u128 {
            panic!("result too large: power is limited to {} bits", MAX_POWER_BITS);
        }
        let mut result = BigInt::from_i64(1);
        let mut base = self.clone();
        let mut e = exponent;
        while e > 0 {
            if e & 1 == 1 {
                result = result.mul(&base);
            }
            e >>= 1;
            if e > 0 {
                base = base.mul(&base);
            }
        }
        result
    }

    /// # Panics
    /// Panics if the value does not fit in an i128.
    pub fn to_i128(&self) -> i128 {
        if self.bit_length() > 127 {
            panic!("value does not fit in 128 bits");
        }
        let mut m: u128 = 0;
        for &limb in self.mag.iter().rev() {
            m = (m << 32) | limb as u128;
        }
        if self.negative {
            -(m as i128)
        } else {
            m as i128
        }
    }

    /// # Panics
    /// Panics if the value does not fit in an i64.
    pub fn to_i64(&self) -> i64 {
        let v = self.to_i128();
        if v > i64::MAX as i128 || v < i64::MIN as i128 {
            panic!("value does not fit in 64 bits");
        }
        v as i64
    }
}

impl Ord for BigInt {
    fn cmp(&self, other: &BigInt) -> Ordering {
        match (self.negative, other.negative) {
            (false, true) => Ordering::Greater,
            (true, false) => Ordering::Less,
            (false, false) => mag_cmp(&self.mag, &other.mag),
            (true, true) => mag_cmp(&other.mag, &self.mag),
        }
    }
}

impl PartialOrd for BigInt {
    fn partial_cmp(&self, other: &BigInt) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl fmt::Display for BigInt {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if self.mag.is_empty() {
            return write!(f, "0");
        }
        let mut chunks: Vec<u32> = Vec::new();
        let mut rest = self.mag.clone();
        while !rest.is_empty() {
            let (q, r) = mag_divrem_small(&rest, 1_000_000_000);
            chunks.push(r);
            rest = q;
        }
        let mut text = String::new();
        if self.negative {
            text.push('-');
        }
        text.push_str(&chunks.last().unwrap().to_string());
        for chunk in chunks.iter().rev().skip(1) {
            text.push_str(&format!("{:09}", chunk));
        }
        write!(f, "{}", text)
    }
}

/// Parse the registry's decimal integer form. "-0", "+1", "01" and " 1" are refused.
///
/// # Panics
/// Panics on anything else.
pub fn parse_big_integer(text: &str) -> BigInt {
    let (negative, digits) = match text.strip_prefix('-') {
        Some(rest) => (true, rest),
        None => (false, text),
    };
    let valid = !digits.is_empty()
        && digits.bytes().all(|b| b.is_ascii_digit())
        && (digits == "0" || !digits.starts_with('0'))
        && !(negative && digits == "0");
    if !valid {
        panic!("not a whole number in decimal: \"{}\"", text);
    }
    let mut mag: Vec<u32> = Vec::new();
    for b in digits.bytes() {
        let mut carry = (b - b'0') as u64;
        for limb in mag.iter_mut() {
            let t = *limb as u64 * 10 + carry;
            *limb = t as u32;
            carry = t >> 32;
        }
        if carry > 0 {
            mag.push(carry as u32);
        }
    }
    BigInt::make(negative, mag)
}

/// Raise to a power, refusing results beyond MAX_POWER_BITS before building them.
///
/// # Panics
/// Panics on a negative exponent or a result that would be too large.
pub fn power_big_integer(base: &BigInt, exponent: &BigInt) -> BigInt {
    if exponent.is_negative() {
        panic!("exponent must not be negative");
    }
    if base.abs() <= BigInt::from_i64(1) {
        if exponent.is_zero() {
            return BigInt::from_i64(1);
        }
        if base.is_negative() {
            let even = exponent.rem(&BigInt::from_i64(2)).is_zero();
            return BigInt::from_i64(if even { 1 } else { -1 });
        }
        return base.clone();
    }
    if exponent.bit_length() > 32
        || (base.bit_length() as u128) * (exponent.to_i128() as u128) > MAX_POWER_BITS as u128
    {
        panic!("result too large: power is limited to {} bits", MAX_POWER_BITS);
    }
    base.pow(exponent.to_i64() as u64)
}

/// Exact integer arithmetic on decimal strings. Division truncates towards
/// zero and the remainder takes the sign of the dividend, as in TypeScript.
///
/// # Panics
/// Panics on malformed numbers, division by zero, a negative or oversized
/// power, or an unknown operation.
pub fn calculate_big_integer(a: &str, op: &str, b: &str) -> String {
    let x = parse_big_integer(a);
    let y = parse_big_integer(b);
    match op {
        "add" => x.add(&y).to_string(),
        "subtract" => x.sub(&y).to_string(),
        "multiply" => x.mul(&y).to_string(),
        "divide" => {
            if y.is_zero() {
                panic!("division by zero");
            }
            x.div(&y).to_string()
        }
        "remainder" => {
            if y.is_zero() {
                panic!("division by zero");
            }
            x.rem(&y).to_string()
        }
        "power" => power_big_integer(&x, &y).to_string(),
        other => panic!("unknown operation \"{}\"", other),
    }
}

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