factorion-math 1.0.7

#![doc = include_str!("../README.md")]
use rug::integer::IntegerExt64;
use rug::ops::*;
use rug::{Complete, Float, Integer};
use std::ops::Mul;
use std::ops::Rem;

pub use rug;

/// The k-factorial of n
pub fn factorial(n: u64, k: u32) -> Integer {
    Integer::factorial_m_64(n, k as u64).complete()
}

/// The k-factorial of -n is the factorial of n-k times this factor (inf if None)
pub fn negative_multifacorial_factor(n: Integer, k: i32) -> Option<Integer> {
    let n = -n;
    let rem = n.rem(2 * (k as i64));
    if rem == 0 {
        None
    } else if rem < k {
        Some(Integer::ONE.clone())
    } else if rem == k {
        None
    } else {
        Some(Integer::NEG_ONE.clone())
    }
}

/// The subfactorial of n
pub fn subfactorial(n: u64) -> Integer {
    let mut f = Integer::ONE.clone();
    let mut b = true;
    for i in 1..=n {
        f *= Integer::from(i);
        if b {
            f -= Integer::ONE;
        } else {
            f += Integer::ONE;
        }
        b.not_assign();
    }
    f
}

/// The termial of n
pub fn termial(n: Integer) -> Integer {
    (n.clone() * (n + 1)) / 2
}

/// The k-termial of n
pub fn multitermial(n: Integer, k: u32) -> Integer {
    let modulo = n.mod_u(k);
    let floor = n / k;
    let ceil = floor.clone() + if modulo == 0 { 0 } else { 1 };
    k * termial(floor) + ceil * modulo
}

/// The factorial of x (using gamma)
pub fn fractional_factorial(x: Float) -> Float {
    (x + 1.0f64).gamma()
}

/// Calculates the k-factorial of x.
///
/// Algorithm adapted from the formula by pregunton in a
/// [Math Stack Exchange reply](https://math.stackexchange.com/questions/3488791/define-the-triple-factorial-n-as-a-continuous-function-for-n-in-mathbb/3488935#3488935).
pub fn fractional_multifactorial(x: Float, k: u32) -> Float {
    let _k = k as i32;
    let k = Float::with_val(x.prec(), k);
    let fact = fractional_factorial(x.clone() / k.clone());
    let pow = k.clone().pow(x.clone() / k.clone());
    let t = if _k <= 7 {
        fractional_multifactorial_product(x, _k, k)
    } else {
        fractional_multifactorial_product_fast(x, _k, k)
    };
    fact * pow * t
}

fn fractional_multifactorial_product(x: Float, _k: i32, k: Float) -> Float {
    (1.._k)
        .map(|j| {
            let exp = fractional_multifactorial_sum(x.clone(), j, _k, k.clone());
            (j / k.clone().pow(j / k.clone()) / fractional_factorial(j / k.clone())).pow(exp)
        })
        .reduce(Mul::mul)
        .unwrap_or(Float::with_val(x.prec(), 1))
}

fn fractional_multifactorial_product_fast(x: Float, _k: i32, k: Float) -> Float {
    (-3..=3)
        .map(|n| {
            ((x.to_integer().unwrap() + n - 1) as Integer)
                .rem(_k - 1)
                .to_i32()
                .unwrap()
                + 1
        })
        .map(|j| {
            let exp = fractional_multifactorial_sum(x.clone(), j, _k, k.clone());
            (j / k.clone().pow(j / k.clone()) / fractional_factorial(j / k.clone())).pow(exp)
        })
        .reduce(Mul::mul)
        .unwrap_or(Float::with_val(x.prec(), 1))
}

fn fractional_multifactorial_sum(x: Float, j: i32, _k: i32, k: Float) -> Float {
    (0.._k)
        .filter(|l| *l != j)
        .map(|l| 1 - Float::cos_pi(2 * ((x.clone() - l) / _k)))
        .reduce(Mul::mul)
        .unwrap_or(Float::with_val(x.prec(), 1))
        / (1.._k)
            .map(|l| 1 - Float::cos_pi(-2 * l / k.clone()))
            .reduce(Mul::mul)
            .unwrap_or(Float::with_val(x.prec(), 1))
}

/// The termial of x
pub fn fractional_termial(x: Float) -> Float {
    let prec = x.prec();
    let gamma_plus = ((x.clone() + 2) as Float).gamma();
    let gamma_minus = ((x) as Float).gamma();
    if !gamma_minus.is_finite() && gamma_plus.is_finite() {
        return Float::new(prec);
    }
    (gamma_plus / gamma_minus) / 2
}

/// Calculates Sterling's Approximation of large factorials.
/// Returns a float with the digits, and an int containing the extra base 10 exponent.
///
/// # Panic
/// Will panic if `n <= 0`.
///
/// Algorithm adapted from [Wikipedia](https://en.wikipedia.org/wiki/Stirling's_approximation) as cc-by-sa-4.0
pub fn approximate_factorial(n: Integer, prec: u32) -> (Float, Integer) {
    let n = Float::with_val(prec, n);
    approximate_factorial_float(n)
}
/// Calculates Sterling's Approximation of large factorials.
/// Returns a float with the digits, and an int containing the extra base 10 exponent.
///
/// # Panic
/// Will panic if `n <= 0`.
///
/// Algorithm adapted from [Wikipedia](https://en.wikipedia.org/wiki/Stirling's_approximation) as cc-by-sa-4.0
pub fn approximate_factorial_float(n: Float) -> (Float, Integer) {
    let prec = n.prec();
    let base = n.clone() / Float::with_val(prec, 1).exp();
    let ten_in_base = Float::with_val(prec, 10).ln() / base.clone().ln();
    let (extra, _) = (n.clone() / ten_in_base.clone())
        .to_integer_round(rug::float::Round::Down)
        .unwrap_or_else(|| panic!("Got non-finite number, n was {n}"));
    let exponent = n.clone() - ten_in_base * Float::with_val(prec, extra.clone());
    let factorial = base.pow(exponent)
        * (Float::with_val(prec, rug::float::Constant::Pi) * Float::with_val(prec, 2) * n.clone())
            .sqrt();
    // Numerators from https://oeis.org/A001163 (cc-by-sa-4.0)
    let numerators: [f64; 17] = [
        1.0,
        1.0,
        1.0,
        -139.0,
        -571.0,
        163879.0,
        5246819.0,
        -534703531.0,
        -4483131259.0,
        432261921612371.0,
        6232523202521089.0,
        -25834629665134204969.0,
        -1579029138854919086429.0,
        746590869962651602203151.0,
        1511513601028097903631961.0,
        -8849272268392873147705987190261.0,
        -142801712490607530608130701097701.0,
    ];
    // Denominators from https://oeis.org/A001164 (cc-by-sa-4.0)
    let denominators: [f64; 17] = [
        1.0,
        12.0,
        288.0,
        51840.0,
        2488320.0,
        209018880.0,
        75246796800.0,
        902961561600.0,
        86684309913600.0,
        514904800886784000.0,
        86504006548979712000.0,
        13494625021640835072000.0,
        9716130015581401251840000.0,
        116593560186976815022080000.0,
        2798245444487443560529920000.0,
        299692087104605205332754432000000.0,
        57540880724084199423888850944000000.0,
    ];
    let series_sum: Float = numerators
        .into_iter()
        .zip(denominators)
        .enumerate()
        .map(|(m, (num, den))| num / (den * n.clone().pow(m)))
        .reduce(|a, e| a + e)
        .unwrap_or(Float::new(prec));
    let factorial = factorial * series_sum;
    adjust_approximate((factorial, extra))
}

pub const APPROX_FACT_SAFE_UPPER_BOUND_FACTOR: u32 = 4_000_000;
/// Calculates an approximation of the multifactorial
/// using the sterling aproximation and the fractional multifactorial algorithm.
///
/// # Panic
/// Will panic if n is non-positive,
/// or if the input is so large, that the output is inf, safe if n * 4_000_000 is finite.
pub fn approximate_multifactorial(n: Integer, k: u32, prec: u32) -> (Float, Integer) {
    let n = Float::with_val(prec, n);
    approximate_multifactorial_float(n, k)
}
/// Calculates an approximation of the multifactorial
/// using the sterling aproximation and the fractional multifactorial algorithm.
///
/// # Panic
/// Will panic if n is non-positive,
/// or if the input is so large, that the output is inf, safe if n * 4_000_000 is finite.
pub fn approximate_multifactorial_float(n: Float, k: u32) -> (Float, Integer) {
    let prec = n.prec();
    let k = Float::with_val(prec, k);
    let fact = approximate_factorial_float(n.clone() / k.clone());
    let pow = approximate_multifactorial_pow(n.clone(), k.clone());
    let t = approximate_multifactorial_product(n, k);
    adjust_approximate((fact.0 * pow.0 * t, fact.1 + pow.1))
}
fn approximate_multifactorial_pow(n: Float, k: Float) -> (Float, Integer) {
    let base = n.clone() / k.clone();
    let k_log10 = k.clone().log10();
    let e = (base.clone() * k_log10.clone())
        .to_integer_round(rug::float::Round::Down)
        .unwrap()
        .0;
    let x = k.pow(base - e.clone() / k_log10);
    (x, e)
}
fn approximate_multifactorial_product(n: Float, k: Float) -> Float {
    let j: Float = ((n - 1) as Float).rem(&k) + 1;
    j.clone() / k.clone().pow(j.clone() / k.clone()) / fractional_factorial(j.clone() / k.clone())
}

/// The subfactorial of n as a * 10^b
pub fn approximate_subfactorial(n: Integer, prec: u32) -> (Float, Integer) {
    let n = Float::with_val(prec, n);
    approximate_subfactorial_float(n)
}
/// The subfactorial of n as a * 10^b
pub fn approximate_subfactorial_float(n: Float) -> (Float, Integer) {
    let prec = n.prec();
    let (x, e) = approximate_factorial_float(n);
    adjust_approximate((x / Float::with_val(prec, 1).exp(), e))
}

/// The k-termial of n as a * 10^b
pub fn approximate_termial(n: Integer, k: u32, prec: u32) -> (Float, Integer) {
    let n = Float::with_val(prec, n);
    approximate_termial_float(k, n)
}

/// The k-termial of n as a * 10^b
pub fn approximate_termial_float(k: u32, n: Float) -> (Float, Integer) {
    let prec = n.prec();
    let len: Integer = n
        .clone()
        .abs()
        .log10()
        .to_integer_round(rug::float::Round::Down)
        .unwrap()
        .0;
    let len_10 = Float::with_val(prec, 10).pow(len.clone());
    let a = n.clone() / len_10.clone();
    let b = (n + k) / len_10;
    adjust_approximate(((a * b) / (2 * Float::with_val(prec, k)), 2 * len))
}

/// The k-termial of x * 10^e as a * 10^b
pub fn approximate_approx_termial((x, e): (Float, Integer), k: u32) -> (Float, Integer) {
    let a = x.clone();
    let b = x + k;
    adjust_approximate(((a * b) / (2 * k), 2 * e))
}

/// Calculates the approximate digits of a multifactorial.
/// This is based on the base 10 logarithm of Sterling's Approximation.
///
/// # Panic
/// Will panic if either `n` is non-positive,
/// or if `n` is `inf` as a `Float`.
///
/// Algorithm adapted from [Wikipedia](https://en.wikipedia.org/wiki/Stirling's_approximation) as cc-by-sa-4.0
pub fn approximate_multifactorial_digits(n: Integer, k: u32, prec: u32) -> Integer {
    let n = Float::with_val(prec, n);
    approximate_multifactorial_digits_float(k, n)
}
/// Calculates the approximate digits of a multifactorial.
/// This is based on the base 10 logarithm of Sterling's Approximation.
///
/// # Panic
/// Will panic if either `n` is non-positive,
/// or if `n` is `inf` as a `Float`.
///
/// Algorithm adapted from [Wikipedia](https://en.wikipedia.org/wiki/Stirling's_approximation) as cc-by-sa-4.0
pub fn approximate_multifactorial_digits_float(k: u32, n: Float) -> Integer {
    let prec = n.prec();
    let k = Float::with_val(prec, k);
    let ln10 = Float::with_val(prec, 10).ln();
    let base = n.clone().ln() / &ln10;
    ((Float::with_val(prec, 0.5) + n.clone() / k.clone()) * base - n.clone() / k / ln10)
        .to_integer_round(rug::float::Round::Down)
        .unwrap_or_else(|| panic!("Got non-finite number, n was {n}"))
        .0
        + Integer::ONE
}

/// The k-termial of n as 10^b
pub fn approximate_termial_digits(n: Integer, k: u32, prec: u32) -> Integer {
    let n = Float::with_val(prec, n);
    approximate_termial_digits_float(k, n)
}
pub fn approximate_termial_digits_float(k: u32, n: Float) -> Integer {
    let prec = n.prec();
    ((n.log10() * 2) as Float - Float::with_val(prec, 2 * k).log10())
        .to_integer_round(rug::float::Round::Down)
        .unwrap()
        .0
}

/// Adjusts the output of [`approximate_factorial`], by combining the 10 exponents of the number and the extra exponent.
///
/// # Panic
/// Will panic if `x` is not finite.
pub fn adjust_approximate((x, e): (Float, Integer)) -> (Float, Integer) {
    let prec = x.prec();
    if x == 0.0 {
        return (Float::with_val(prec, 0), Integer::ZERO.clone());
    }
    let (extra, _) = (x.clone().abs().ln() / Float::with_val(prec, 10).ln())
        .to_integer_round(rug::float::Round::Down)
        .unwrap_or_else(|| panic!("Got non-finite number, x was {x}"));
    let x = x / (Float::with_val(prec, 10).pow(extra.clone()));
    let total_exponent = extra + e;
    (x, total_exponent)
}

/// Number of digits of n (log10 of absolute, but 1 if 0)
pub fn length(n: &Integer, prec: u32) -> Integer {
    if n == &0 {
        return Integer::ONE.clone();
    }

    (Float::with_val(prec, n).abs().ln() / Float::with_val(prec, 10).ln())
        .to_integer_round(rug::float::Round::Down)
        .unwrap()
        .0
        + 1
}

/// Recommended constants
pub mod recommended {
    /// Recommended prec, balancing accuracy and performance
    pub const FLOAT_PRECISION: u32 = 1024;
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::str::FromStr;

    use recommended::FLOAT_PRECISION;

    #[test]
    fn test_calculate_multi_single_factorial() {
        assert_eq!(factorial(0, 1), Integer::from(1));
        assert_eq!(factorial(1, 1), Integer::from(1));
        assert_eq!(factorial(2, 1), Integer::from(2));
        assert_eq!(factorial(3, 1), Integer::from(6));
        assert_eq!(factorial(4, 1), Integer::from(24));
        assert_eq!(factorial(5, 1), Integer::from(120));
        assert_eq!(factorial(6, 1), Integer::from(720));
        assert_eq!(factorial(7, 1), Integer::from(5040));
        assert_eq!(factorial(8, 1), Integer::from(40320));
        assert_eq!(factorial(9, 1), Integer::from(362880));
        assert_eq!(factorial(10, 1), Integer::from(3628800));
    }

    #[test]
    fn test_calculate_multi_double_factorial() {
        assert_eq!(factorial(0, 2), Integer::from(1));
        assert_eq!(factorial(1, 2), Integer::from(1));
        assert_eq!(factorial(2, 2), Integer::from(2));
        assert_eq!(factorial(3, 2), Integer::from(3));
        assert_eq!(factorial(4, 2), Integer::from(8));
        assert_eq!(factorial(5, 2), Integer::from(15));
        assert_eq!(factorial(6, 2), Integer::from(48));
        assert_eq!(factorial(7, 2), Integer::from(105));
        assert_eq!(factorial(8, 2), Integer::from(384));
        assert_eq!(factorial(9, 2), Integer::from(945));
        assert_eq!(factorial(10, 2), Integer::from(3840));
        assert_eq!(
            factorial(100, 2),
            Integer::from_str(
                "34243224702511976248246432895208185975118675053719198827915654463488000000000000"
            )
            .unwrap()
        );
    }

    #[test]
    fn test_calculate_triple_factorial() {
        assert_eq!(factorial(0, 3), Integer::from(1));
        assert_eq!(factorial(1, 3), Integer::from(1));
        assert_eq!(factorial(2, 3), Integer::from(2));
        assert_eq!(factorial(3, 3), Integer::from(3));
        assert_eq!(factorial(4, 3), Integer::from(4));
        assert_eq!(factorial(5, 3), Integer::from(10));
        assert_eq!(factorial(6, 3), Integer::from(18));
        assert_eq!(factorial(7, 3), Integer::from(28));
        assert_eq!(factorial(8, 3), Integer::from(80));
        assert_eq!(factorial(9, 3), Integer::from(162));
        assert_eq!(factorial(10, 3), Integer::from(280));

        assert_eq!(factorial(20, 3), Integer::from(4188800));
        assert_eq!(factorial(22, 3), Integer::from(24344320));
        assert_eq!(factorial(25, 3), Integer::from(608608000));
        assert_eq!(
            factorial(100, 3),
            Integer::from_str("174548867015437739741494347897360069928419328000000000").unwrap()
        );
    }

    #[test]
    fn test_calculate_quadruple_factorial() {
        assert_eq!(factorial(0, 4), Integer::from(1));
        assert_eq!(factorial(1, 4), Integer::from(1));
        assert_eq!(factorial(2, 4), Integer::from(2));
        assert_eq!(factorial(3, 4), Integer::from(3));
        assert_eq!(factorial(4, 4), Integer::from(4));
        assert_eq!(factorial(5, 4), Integer::from(5));
        assert_eq!(factorial(6, 4), Integer::from(12));
        assert_eq!(factorial(7, 4), Integer::from(21));
        assert_eq!(factorial(8, 4), Integer::from(32));
        assert_eq!(factorial(9, 4), Integer::from(45));
        assert_eq!(factorial(10, 4), Integer::from(120));

        assert_eq!(factorial(20, 4), Integer::from(122880));
        assert_eq!(factorial(22, 4), Integer::from(665280));
        assert_eq!(factorial(25, 4), Integer::from(5221125));
        assert_eq!(
            factorial(100, 4),
            Integer::from_str("17464069942802730897824646237782016000000").unwrap()
        );
    }

    #[test]
    fn test_calculate_quituple_factorial() {
        assert_eq!(factorial(0, 5), Integer::from(1));
        assert_eq!(factorial(1, 5), Integer::from(1));
        assert_eq!(factorial(2, 5), Integer::from(2));
        assert_eq!(factorial(3, 5), Integer::from(3));
        assert_eq!(factorial(4, 5), Integer::from(4));
        assert_eq!(factorial(5, 5), Integer::from(5));
        assert_eq!(factorial(6, 5), Integer::from(6));
        assert_eq!(factorial(7, 5), Integer::from(14));
        assert_eq!(factorial(8, 5), Integer::from(24));
        assert_eq!(factorial(9, 5), Integer::from(36));
        assert_eq!(factorial(10, 5), Integer::from(50));

        assert_eq!(factorial(15, 5), Integer::from(750));
        assert_eq!(factorial(20, 5), Integer::from(15000));
        assert_eq!(factorial(22, 5), Integer::from(62832));
        assert_eq!(factorial(25, 5), Integer::from(375000));
        assert_eq!(
            factorial(100, 5),
            Integer::from_str("232019615953125000000000000000000").unwrap()
        );
    }

    #[test]
    fn test_calculate_factorials_with_interesting_lengths() {
        let result = factorial(22, 1);
        assert_eq!(22, length(&result, FLOAT_PRECISION));

        let result = factorial(23, 1);
        assert_eq!(23, length(&result, FLOAT_PRECISION));

        let result = factorial(24, 1);
        assert_eq!(24, length(&result, FLOAT_PRECISION));

        let result = factorial(82, 1);
        assert_eq!(123, length(&result, FLOAT_PRECISION));

        let result = factorial(3909, 1);
        assert_eq!(12346, length(&result, FLOAT_PRECISION));

        let result = factorial(574, 1);
        assert_eq!(1337, length(&result, FLOAT_PRECISION));
    }

    #[test]
    fn test_calculate_factorial_with_ten_thousand_digits() {
        let mut num = 0;
        let mut result = Integer::new();
        while length(&result, FLOAT_PRECISION) < 10_000 {
            num += 1;
            result = factorial(num, 1);
        }
        assert_eq!(num, 3249);
    }

    #[test]
    fn test_calculate_factorial_hundred_thousand() {
        let num = 100_001;
        let result = factorial(num, 1);
        assert_eq!(length(&result, FLOAT_PRECISION), 456579);
    }

    #[test]
    fn test_calculate_factorial_multilevel_hundred_thousand() {
        let num = 100_001;
        let result = factorial(num, 10);
        assert_eq!(length(&result, FLOAT_PRECISION), 45660);
    }

    // #[test]
    // fn test_calculate_upper_limit() {
    //     let num = UPPER_CALCULATION_LIMIT;
    //     let result = factorial(num, 1);
    //     assert_eq!(length(&result), 5565709);
    // }

    #[test]
    fn test_calculate_subfactorial() {
        assert_eq!(subfactorial(0), Integer::from(1));
        assert_eq!(subfactorial(1), Integer::from_str("0").unwrap());
        assert_eq!(subfactorial(2), Integer::from_str("1").unwrap());
        assert_eq!(subfactorial(3), Integer::from_str("2").unwrap());
        assert_eq!(subfactorial(4), Integer::from_str("9").unwrap());
        assert_eq!(subfactorial(5), Integer::from_str("44").unwrap());
        assert_eq!(subfactorial(6), Integer::from_str("265").unwrap());
        assert_eq!(subfactorial(10), Integer::from_str("1334961").unwrap());
        assert_eq!(subfactorial(12), Integer::from_str("176214841").unwrap());
        assert_eq!(subfactorial(13), Integer::from_str("2290792932").unwrap());
        assert_eq!(subfactorial(14), Integer::from_str("32071101049").unwrap());
        assert_eq!(
            subfactorial(20),
            Integer::from_str("895014631192902121").unwrap()
        );
        assert_eq!(
            subfactorial(21),
            Integer::from_str("18795307255050944540").unwrap()
        );
        assert_eq!(
            subfactorial(34),
            Integer::from_str("108610077126170304674801654684367969729").unwrap()
        );
        assert_eq!(subfactorial(100), Integer::from_str("34332795984163804765195977526776142032365783805375784983543400282685180793327632432791396429850988990237345920155783984828001486412574060553756854137069878601").unwrap());
        assert_eq!(subfactorial(1000), Integer::from_str("148030000371669080363916614118966054237787246771683461554691846089888817122236071181318987391054867545959072618913067395256592673937835956772241168222528295595683596720980666220609427831904885242029599391814586746492963217722340317777195575260366010059010655172144738284878861758208131004735035818477569368786432061632016188446807685910940321832572996649981481772252325191040086154426554657538458444535765717871033946613771702350305625265004320388243386097879262683082846870385959781954488956389970392578944288660459295031234507478736716881824136783622584535138805982288145285315709292044924680549217929790115984545014441521755735726306195457199770572691754663617787391418043564291295463544232345623814234091075245481655240617768194600801613370454579550360990469214942505585371933295794820730182459765487139302567668926438713305035074950095908181875721870629028442704188817930628082595769711646309710902713389577813924985084195489687602046619502008960961979336971200011845832972766496820425232309014424160383352549432587175804599513224295387620793237492133106194854781675335264245443368406349778626577154153936165795176414280246708209684255021094823421966794931258601926237888502063061179908920389122437280096694180318756729540187743522955287693403344627192008193243150047926683116206789808737520329932175926689631039801333205271773068694119886681439408208634536616162125484968246433299086618972038726320143524530159155122816067209479359158975104676175689942972909538981915518610438058966813454552135810617643268326508884740007563057812557756872119827948177012498720002846584320083602883505675223930415710240943383142087697091237570482781352256162809593048997307636369071690373544475334727722226964401838105804104033698859046508072636221121284767256179261384695575800126777871914608799740333135169078085040301870738700721986026518324144597854534393940110548874771456733548819690014891150299883374569036144504075650284247154291122602262577738634502394468066637260601515590412677997656372138988479892629787344855469625993188902215341743976591335786134612426484416557074485085137922648888557127618980204107341206517456111787177656668620397156874752365541689736459115633909848251703534756902949331850082296669410306980175719986482188446333446450823956158029544268395051423740042819986368612454904255206373684842598857136228239326853906860111911390847498545181350875035398066868621959973870036473108206470890805125591766035651660263166256071859066523494404932873989243033885387310363168734739688132495065765084286985470381074859852651721482664917019227944750044815550686001").unwrap());
        assert_eq!(subfactorial(3500), Integer::from_str("87964690579311476903697952535762423171293573041549831274936832063230377496387961881818325071352362000126022647600219125671302009007771359686789512876254212531891950092753355796126046992513774857242432339339333447252782390365510514829896378091943331363298445226434169243647341041682693637335917283552025047705718743606179620237721970890403909827137815240107365022480391637222374108121610989139629430195740447594499162476924925761753896065968572455897006913141562929011308795335867966360121651137911521052895606137398154068818807527050702040952530158904764608197311241528896866121709121383604182201034765434742018825060316913243796781281776391694867036100295773369046670790385522751768636832092969508050108015738623884523245531324120166592130951369346913120217300513632695873818291127329035960771001998771206126436169206318142794123554007303866321668204237469209729131486662626246912565485170993538306414755056352947560851586773098953595642256313233249851379867036232442255598798461536754895744498876527681968761354354492707047576158302678895095224873599342851839817500887247380544700566649519276391975014368166344681311284691317802595922124458635093418346890412488353399986161511676807760260985582716782003108227290059624211491058442048370865657825059701419818090874444530701374111546561579906853579715976287845919061574251086979668208048769329795711131444085509117916969361052475322507621969047833839549195745407431764562643081820141462954616728643224174311951463115049364179678092979408523270388666724820774242348382042912267743010056997700031268389624352623296112305476625195636895577209727842898517396664307434638564583446052771848664649059251606564552198025097236159143436898622941491316116404027176288022394396660586264908732436100151684471984067779045661330652207815265549082928308925294739624045036557731562446095969313646788713297423629885992284846268942557929165945599793545941860308786165492769938736519597957349597769666061366120837416003934850618708189411098020107735661898987023479925076383048624977683033753070054859860275363003243244942946304343402379555825371040659106921107436910748777482289050509309926706331412950832857394161018706819894665606393858954099698056127800910399031861987913217488849867040052827141575981142204405211413582494654061270471036024734315935594278864231871024691039184822489106374619196954575870107827539914782731142220557019645062242623026221727309194863753886258573948257747513967037767828550744015732061727723268244729778736549758891049432907667569934141158501220497464926181928478953778307835953566247059496765940635380699983265826073949460771997208096870070336937598848179821051894439684705140849471755120072515257029959137778212800375460351018080073354920646370945741941634800154553888811450309234133504584449112307914779008369693230748531390331325895922551985794989379838622872524210467665435051783609604218458176648003274964146077707990975976236268280765140873260019036781201925125401480567049477443992146917663588390489638806499515406158460859565940934843640731634171429071834929638577410486879445333777436331724942319267885681588041957271116813751844518067954619461045274234671731629971934381930568474807059584442552526106416191776951215714071559066979314076869334695519171280451654010299961640187041103229115345161292553222755357135295815872391785443499846030813021312810702143146357073461137431823532988625245427436770117075095025760111649969810428473114214583666562993369630869575446589978517676701140858753060519736036788343419418617105185124121275438367345608695776395425137278057052289984442748338035729387341620787288371776819382730644633027274047771282773011047758941316074627464207424589638721993170932525856281376541646687545501022749130180523839559753006315695772045002882085473627587729530957335083580614897677969299970486149183518811846046910935519927488184484952509021797992421767912555572768013098629479426556070699241891692098894619448791303450217535578300653035214784304104612941484379436258939528989793337248229249876372532917829455089744055476064504661076615272923181881539937076670618926044766470319609981511398361154372412415754367903500461179995749430648049442897151777195861229513504655721164101719999476873679702522404923550850170049339063225647264431498628429379963108689944602674574530919309841717831276224289686829131766591678520371273662907809068291690255040203950742544662139963321733321885983378394593986216920855440540952425181171634296877940658670865280696076366370022234185846408478425682449402155035911713541542423531103734110905481570961308500547839824241854642339337746367121638802147086232742035082236149687293844035413508842200085456993102116390657292789376469986875266489936770793263235214678341519899131577345196917108210167938612105336141315492485647570337713582097330131071465133220821916649258316309256754483670844820463723841479928646014635282713587187360340335842916461041724879812062010034682791552016109952641678459959226724331046005384739690824171005092057197148939983215485933044021748741067066908330037346425053828727335790079526990685098335095440381806114648376891732360985954259866485232950768681143906797869488883362250628528117984224743776630068651153277921637952379690471297285066890575704551874506748076555958802924925596912828947483072312680055748721457158536611958298309979628268049779666027460243557939520330843403760671188346721303955140539101107990300377346632746731787751105097013010903507184907229126206513844656876918988795582127896303829530075104385732564924467829704790506109105834758126277618946388346004661311696310924958360270220105709679904356893289799630367572744438275175923269459162671177233194480142210788721530646823467125939215036536465157827413585445365165165915606415114099570094767091653632276504209889443402868353141534809861207103353943268313254640667985433420472553499232910442938942919693243233561177711979926110722172022737153307778869836921938587120527105650668696575824390138068745418782434841574997255995251572576406771823432674179335516601407313583265400052485324402417586844302231051681938575031066609247951503588903794036646174279702242564883441131160507126067243240092117029748077464903470387550328866739683428050951725595700639617287370731256213111999758359027455336528710956142573893881326878941093138131479379294251401417863619504206964901012032308773656436629188059311079457810781082974058106425244860363680240470052638940169307108921420711337115721225383754830003251702273619151233159279243133115154307608233845473881220670873291299290646293642508352998006307399916974568296893624787729206513193854404379855303422436094229561826000023221073445361466722049739856318354208605036699632697852644845119631570734162294941377191874106565985040658910112566448717064361618441271045302145484836205067631904046804475085968220553112907851498800492210003043273877419079679861285952923433908370629232474392928766290295064761239923630489630007957201301936166490884863426388521716380562674782761603792641656907964911228231491878619263605954533691517685422191131596474076843093189868252213720762798258300230150585792431906485315694669475768176831380871077799923078148316602418163689517261555968879487540775664659337492101741179114049283169582092914624642076458636012553193900023445784497194557250469946018709716607649225595788322693475009518057720896054150983017409308327434118273282094590984491205096140181011543655282964683506540015539106161536711490336637097766270141682461564210558251256707669449523336662127956338371056013133811171722912468083337681828360879384481805289584067164775747154834952255591004563041907301058117034926857977241751962919346515162869584710105588756103446049723659130603418505700829369029416617082551537771773315963730259239576084272960989430962441043516909431414119570867039902745353092903805511936260039242676378874630083076279075677001917984838363735263020251688601101593673204078661250191763468713933780382437772609593558323141361681098165177930721519667462360474607153307985411784774251110522086635432001126935882086991886786535526281052589277366716572437098827959739373617691344094645054981583127579297368870183680771108547000256373322517687463175442080190797890501784079340755252930289258180900130956090609840893843861202859488120034522865066096591692369186011865061204988448160851129870266754387045352779168322441197286011419200739289288148249792822232227137483483502226290940689315335190961838082107636284781807296530521465934474244209202411327384364890292342342239532860144004427078539453772671947862914778607665210576992750053067862595183262133101683685883334415755332658021542110066297060370283009577808870902943496372837782428630791577023804810253897055408079271452828274114865018535899788981714846791991166023512370519823365959750091304567581141773002573680791270530380559859697656309168340852099931237823578136765546626522053596853687797852320323209531454790757286059591405127963225761461430937644503881197794383308844051466772515323922349958895906460872308893973689678406231643106745061319874112715695932081311413162510500039609781053185701719167529775168703026564111775826284764297102288110450845573186849410216506710448304118878222539180022811951746668693251894604679547515577952811562942664145349165520086307524581236405990006095387226342060859784848774755471700187362813826753348876791437770855454853080145557331494488102984016740339639552706654048771346251491452300428733191430126465918026675281507907566035675129511981018241089508566445265211591578035818691584464421406675550327254285369980199379036245766621728300025441564224756866910745264422284823851865956822853013111521330386681428382313762390962977389059536522004826263597249812413344419449459395324859258294463308724554625049668243581592586787048285309221587057323482013091684826606030332563466378010160369982023106523146425596640899220564357825549457948129968594976767890706762981861211549601853515166568638120219269404031002591396999438558456268808654332325314025710852717882733843182532191935408235554135867539625834822279172079130605023250834063134900502356866437756782971255690075896572968873979658781461138828564190205495576680444062462826173866204657788879178818157997477375728407633299554737598010317740961150647865156603733581643099429387772620782425866820395007565203712773766894192129790362799137131843313622358198995613626445074121377413210616787069224579518600461499342184009844742205676798826151464786496774857532951680903713204512902906492992144576558538101814735471388282608668421110084724985292356091560524893629269178894789966556090098403458297809761629926668671323154980927956092141059964791488175259377863097489806495919876285801573446487427421624626193806177713467030192937556068993461876359185574959886193605006151120425325017505191363383024530204542925298739431122986169913687221517731141010893087148865761151847729898372580007271389208387839822814090101247615212567521751476371764734480122019911635481351322859718149348651001").unwrap());
        assert_eq!(subfactorial(10000), Integer::from_str("10470804208445737513419697550328065766234399081684502763228668686283147925314523291314863732857026337680359333788520909830871014634592384682585292048843591651488378745429186959508254132734136717582691766695734308490073779346984573849186693486934977629545901730276260351384808998522474130864553928862785448752792107976590673721834208498342585926203001301530094295599095027796624265959994494831245191573138429154481209127194989500638951906688849372097945939546042812193464104539080530873197821078832846258439893651994841836130557888208557917480806961853235287156711293610130980405066995293756307549740598868239083804216287661575761990606362926425627694006133853650675293675412399201321126027742242408425710188498858353124206226685103346046812819385565110148001891982756945813847772777623970469392563078232299999340274111264366763599300718831358428923065215938745162710000988268691176446196011719661220770797592822093519250060403555953623946814614503488201400189701605013379064599828523666929213647892072402871979686494807552044228269648763949333918360957810138127763316737438698559369837240634716833290365568077088789893462721484938913233710243202470048377271762062789388943254993972375786908404156061280179172721981548789040600393178410172149490219974127200086797635214370678438162091745493239365354197089647279973252803829965642348308770277607999480656084271511088754078877478009920907972790643403112470506427875964328802646595496225121980604795110503058052652514680866929862334409587081263957642733467360261311791363211535232285904422509843325508016927153753313674093195650750624496765971145136947171849062536467139805955620769412300610603281876013488718989207907711003795320100917272143230335558203907274956697401964352032905611421017175724427425238357613918055064003946000491818751143095644265399718573230687714069993472666846569891357428592954364152580484792341251089495644960043895529170176893549443326849182733495831297051536241255935752653047696698903745391466909345830170669021627221098852675528887113411567918656661713714851794890437699860449797667911300260450883616779248716726810645040599089542481219168121165469725697055420024560361444987768415816264835422976629133369539531214627892728532200802257501640710835008000354025723491544005224295038359985260056411998117283569045028279523725371230387880455481160856539118017631103790860178134637032192259676999769105199569574974601729751224351343465417320638534180210038250318829483384956635179008610184779549282382841279563513818026949222904334033518362501369754827750481554933478395755351591229081165823297310518587704497148362315591637695524501928751651737536772211572123089245486838000305349781687431419501801222692051668217019197260918556086524288416706038727769240460830338943140354205217539019283325877642379174794774687568581098741671150661107383621181752233400175584478660588260442427462967997434861775384588313451660594239475876506001934006000447108969979627303843062370988854068560799623508310384376593408708742243022956923629025225916066758099205308116505347281492439914657720386252906588385796209744822533128427100396181812019701347081200855869274917569383875695993903779182634539676884500777202230236994218243629399712527313007589731305905080342970691632386032255332095994138379882631335566025764065386840065564251364379046258022478784016013064624502607520568701426656947996051104842229373414862021086934415126629746791526412715451600559697018574872718423429069947207433520729788714371823549267220241962534655306740241818325099137325595378071306772474835674494707184516232154878647653255600872740039052330521325769422505536782904346551645971669399363470121582924022729960562297642564889648410830451616444307241473019675494571519842112267296059719024680715546156208292144878997457088622307843887675347512009263451957942516024144428454580661665177564235079872350203976163545684058958984927463303888578509139963968557749867278601022816458931952934489554559979794310156756344343636887852030645117871235511211533693431768762022101161420785380754040694041326767751659471700744078805008402066924211790063735895465435242275856339436923766706119970913618736852398490089997888528271626638206505577570308765334389747342861326937988744110214232627672177017452607978732954780650459256401803914601083012676954709452565804043303302063846670940664281757405513090738277822636702893324327250764950690381056508195912604968777909113401326506960972955300935716104795842686555437443301499088163322897146942231277746474407947711594885853922040651598029478653371032034873824106011431812076838503512508299585553751099350917559428969269974525426809897160661478807729052307941319321553275435141562910023804182652470422508181053026886165461526208726648451711411270388334176099847283795510461878499537951076487290508250153934165372585528652014483769152277161686953526948667184093854496266957530311775595193814819838920043295446215644096431815128614604364132186241111887202953138123079664535661737311666445626059217701626106297061545397357774936229199651729032036540169655133823191976285671135294163776673147525001703519538467777433996642937341187124805038554005264208472561321250547599670000316481245908269626747900226615912419764764802649875689440094096870779955821473548372510891906607332803404638024808036060505750480491974074188817660940683042019559433884712760674251622760544800282652772709807325862294709922251378774517065141816863032846900043849423479590675161013626998803617790719652567349178635349249673549231936422641178035822810719547641118771722099373837874296804893895077340147562154003040013578026286901515160311623640809709836788767865912615870756562050156774182679805113623153889333325635517119131042345594595690704651760028610078443650183490217915939367916990660454222206486218049916829763542979453310478092780154853562658148660929135297539282333653790081725296488860154171078750748341136549245525364241200187230924947697033535777586553738878650519271231267046962654601810437320606437775770128946464167224848885592616619129412492159830241722159644968367900935047553252580065193774986877682063058146597770289419781319298875148452206437502521859974117081363335803377304356844475071668323080221904315595210095159961260265123153864884214990249612992494062492357764540382458605173709756108833671698924720650665709346373598613388402672842677033572418866312374221375979516452246266386150714199136589299429068974357014503721467541706623048182616094974959703710017987022778996036186738690343831546238666916722866159687599074384158251782818170165357244779964257231498273594914189015508002805585315142563894193110988707816223659650735088739913014910174553129522208104659335640480459238527154812164580455902045680673724918458655678621266030083426221697732870542363455606128862925257453435423971309170659876883343414736683467620247869427930582431138057069163855896539780424613094508906952605077800017441046084168571716633056067069276504441416543486093772915271673165386311881456267488375484682749843821543232295618774961313542118455519902990566167688910014187148040191674641135373610751817391519699884491698261243570898820063868684718312198422524834089184168756904503747578950705409840778131231916024025834927205557321645332191137252443613743280334289419099617442265080768250112756858074782679506896546630835865927212449974669858333314663973598869878383453152057951647297054761497166125559737899928832594757891195304034155362881121423079731748042663525360110635647778384891684192190162159675968459357399719407442253242985776172857047089216993666255799713152360984614008679140552449232203700435817923730831313779660190627759659410700384562947772146050960139093828930676916831922559549938467206820043170047455612499380530297303780587759817849307320401403667095796791958353310637574587899422852495136727167734750728032516229309482604755361308965243668928478232859821334880102805160257051722573558291906212230475424451475887650393245766690616006878839356263439625973808491327497566220923272121975065282806179537147166487589409173669735536494512339086776965172439730632769542720438983432076346004493716649088656518840569139408110124831174259882495932099263145834903590117428647512124184610522409437785376287182098827279464182984376240364260950088269693633930944218689607660566083060519610917000914382398817899959982682059468756179218159283618178689620064398017744357276218891288511295019058523707852542041994624475948910241164874446340922605961277294560816033885330083484338061754827136005648614311838883177794744421429437575107427759860720771959007488223069488094815681375003772765517042024067132170237355282792938460828563226527181110430638670220809030535736070065574462128229609484906993921043303601955031466064248566108709424703598630906451254942954594344036293038650933704474029415230217770279534360738807064394313730180910866745176408790616543314797978631594644204301204244929700208992849483393791712171299743471434273404250575059383862166275628210256867174223733501739358022975810340584079248153974005442782771754468623377697809513269757673748433841725671363890968121960227164777270535863346228560693039222820912336290754334665522387954448946387261326581898864931355729356766513242362450515796757963176001098659009338192332210492438807857119228264251235881920578675941372359527173549096428833358895427008075676651500662441685480201794772090607351953854644224601057787473724220439694396562270625047816803609837035995923691683626333226367021675080033077082419536304786160004642147768499150675695833309428734951549164091518000324740225776840825642372662373977428749387986492812858037668798036002929788056338947544700879134917962747795438084331458998311010522893986187914105926775514673229827053829624852732346463184776622392923307148006459748450939409716543500363905826461942526122725135256169657138658693560882462733953572197490397641963059239837400921779278370052600553910803156792213615983745447952033298155519189465020996552731940778352496894136245963547452682782053087192574854776019151301468421473114329640290019790492138462226041908293503795907564438847431249381550813811800309180797650285655530454868162708096689899448257552199366572239936149836919157780088989230959613725941672791060749711554226371728488900437937984927196797643293873761148405527516380046543252492883071614533215209066460610249302455903802289204356408602745618272323178338875142890281253915815530684387957940480204268493720627420568509282624818126433208713995574029733653900267546224689867784009829331734475363813458773591008635906628373643497574716315260886476178278277125932768149294339954859664837040278806123054846637193264781044719890046280412984415392836357144282637357120418378946746721368101876804984521230416244134971570926922819910788994326293615177812662689093761247633456281281713365711666332978776299858847574168263496339461321277062402977183768489139775408469658660855517239906285258981479058899282878924875016723303064571666748623703124356379719261123338924304084333762690804030983004188733758405265004800791601730870201446930815458304483646031394824798271362085110005966219265675927459001434832094005932884367732115596152271967758568362453343277642347199897918387766814706467599271211659554026636350408049091482115738787045275868753191917756210674551993832702780915571774088269462165398467212464550309684955437776251986784056812194692977570336240674925025448673455214339759773167335371101429321131393843706476728657007910190971899243909830430601515391652980780967282011622721271612339229825511999486969560269491400589672542812472160557663893378893620448796488304952784250346246933545185551410452357588262241777965639291585910286364695558245980673011757727314917325271409268929217449541885767036611503808288811548728556269253380337327959496571730988702260550725053462519221480037545153213136967682460202580659343277832539484921396025112138918858539731569409297154924193273452847683547077134429560186399185444572771094255505711820711809127743018342601913797737614626719603019685411005612856253595408163021877475450077572075100221620062978561338930288641994014355610095243132126598486696396178302000399524720396079218852311798128036483597924128365413619115488585665514789760816687634499597814556807603530105368332517459600965422172226569724934083282470755418375592127738146133018074399861487418163021793072457932717758432092115166563363561458755473762974086726182234604174740844779988780692518970999400680051047506986380519351516979663386795659047211085641745731411422805452693725431533707149166116623497228761881366370870268452756329824816208422302587092659669043073452273657513588155241520242717963852101033722211162579247751810411015261706360895158574149181164748103496845798023345617762596636264324794657869535392107596816249447139202763324739963931956685830691420520791176509073720984273140732275650714837163422426779360863540660395868779228343156304015202372081012971821691956620118423564707373856445621139377551362652704644769819385822045936585792027015280866431812159284970172378844457509860963930751205247508683755489809565625778666743363253412075173108925721294476043164696485747537925072884200117807458175694406257462846932670846600766332192644366346387339849586500904140724376615018371683322095759765307582731074430763408926722525189261910986799889851952217841805239743346477394077393159576502869501981680281277334604246592028613480648131157146587278576110499541057370729118293514666828334082528080724702095848455372750832388539070283263443600155790579255023901713489839448327223891514375453546156678872664418296743999047486515149641038541115992001659877388560970291946776238653365522070881765925467185174514655733645962063302213159294686520592875954699404533881414879356980705283921464842127041939036174575434398780355679345324939994047195297843863119026324295878526072217105547700715315144010538637158080555089547660946378854891108017440653418201012956389621697461367420206341094791972852230649491494324063295934980444147996026373626112726905303792612309263569848767385162973803150324498238213776959041298152400852478772873779525133255726018906072245877251038831206287991907464187041302831975285773993099706755111066556828048122338995340726307961615444297227996738329184948356047573064521199233027737021878906776723367170547484980189711431228166697291710254543514083642340264684832237945373491586213685577868306951837379925299239460564579755803766467017738249555400592370525872445290389790320551312348435518141500399458734890688783954218109888723602747397854694775539226157286325126107548367823446179120805965696532287620331852533718175632217151290050910909494063817890671316778992530420569976917442727887537994681325103731148764861565509598187550135040090421876905969936376257756343739796541698771908414904108370552366607182377065007898761625129009037598395250361669747487857031931407273669825835272242606123225859179185181191117253775042309287364950302099650511345450179743955377122950270463476272657069220267228817614547751194605858950316312068342839314623204820511938880737045337574800494906970528834031996940605840995166143314825939459768300874879987913557609280237180980039388757051365384605314913437885636372701063341483097457800645520849599582055917655634386114112999827000311821927848954234161626253302866217046494086051035155242164267301234694802327134854312408826632578592744698222980566680267306271151350532030199870320094429726865617749926605641477176076499378221254759456972878979822307626432914234950628859358738044645114532948142689723317554632344894792742183713023141984258099995716381450935117944859987547683165612491255316816103704911828184194892477896109739682474343417527220226485007332716864342023707217573791963152388316123138901077586530384563136722954512972731860501229346896069740093661737567301134957764885309394376940063719710587485148176192281779262337406068000356376648018804989588256371199994698085291089388748515167522769306088273081927816165694727570786076966418092611799937893104349877073864105566832518811342209758966723553585442246361058011624762127164691760603758088718733718842479918000986125877058882875792552236938780722021377155789918018308376138959857320027760323084732781668849142214837568397649277751035784737167861401626219518954092690083091596125567854962221850424293665561196063810573548601439753226015668289139703362037528491833039699227157423676197255442734679220062222671696232130751652801340911577342850980834586030482855635960556056236841928630834259296729636439259196027590339032323606613813093205098911331867547802920651761880077232392816695021870289682810721036848809838002989118228284980185155048329898410931748715651136653801765406219511236884939664240684734143118235633830467384704187829036837649726222510240819836519162968647759493982314193929751250378813294804838087818648041905239867471108826029782357138577223446379924971164658790708640549528292047360430917882210670031911057774209297368479381050855893232994036974979223746285937164804561100829581985894457419543977267430329166454639893828034743854896296007179813691746293424232622380779097953304267217088020196608903911231916164220346650702957007827689322348171265120382840304986736875058942087845791604810961746587970155242520040179330542708791616829428814022146073913361574301248156042304759943079873097045727584008561329548390011912925241369660895950201960941597784579441137492861345272061707562329263990536328273448283792000891598381302226144183170417583595743796158201903037829065493829911870964565647487389529739501794916885184780727957831764981996698490290598000245114278784803047404582518052859473903725617314005792329343802512850059919687362848880601332057248426092883843183010420894961268251790512807276480783470388600253023342800002304703571914779308421231376950892275468716507972092349840846812337778408832463997322196336219761048147290510699947982916022039008617147913599155685877313070543477703363750785834856390416909626866103653808828839602628140324799690035491663055446540173397077823041882874002320825055790386961386830765570739087579219901788985353593416974599191410014353239435572647122310036279383987351226409368956533308413418399098577011325248621191040845997260791124982047332304525684764911904687560224886975499231171489760060657571756488044872698674938072833832815955945506517999379515844581007675800467704175488209396446538954750365631702915336811594147785152958493122663318937333460085910379953151337226931233034136592464738258831477535933286461728620284752210526966726943540329166518809787617489867706763428205542760417783701482268886666587434849651682335290602797879326966947923753856753954582989892569493060524211198936037540996476144283090016406501691351610369421622265971913256587646416765381070281609457883766583501175286244280433586733196321109000402816233771494621921745060701983771372901077527185323374899300037723789756395336953308652589874151257272587987486501254993664063661283858732438979988607952882024898826064624574335403793020971291464014762104982555216821369023600693759883159766498743559888128709145080397504422451994451273434933910964249027488220507844938801884504904386121142272951354338665370625024266813175265229834709077056492774682318719867401242211217053769422656544738206563049607956202619561653581134046530242203408982177033031756449491492720298370590295196431823391458600493196203582841811533575746824484786633632232059087579849598344841639854168367215055766219768649438973084866226872641706285164942477199614714541275663909682125383651353521952139764515088027704409792771539839013538030080565519127297284941158819784323706998789527051373497418986794194804088750817305716846965087804935815333537721016061797939163127513399950437187016471964699713745142557614057824414132635689139352094545222705876950825662108973723863620503039232319469905029853718855449240771801339501191488777470183563054571260676668262012860789708052885037163088777825366606215497769932717209011066386375051919140102564166017777337330245568615664808541942334875329174299509945658186229177246312349587702833497121049144761808555673059709965298938376722602933535852894057058739513392151629638781171483779924123985080360001218702725389203102300751123738801511846102653615549900245740719572512213915275085567631719046857275716145170207766449824850169187044246637684225291818209387702135494619468586409387419060297227191493319591037057891634377911935514443086858270056798790812862914874477064096203239888876474342281750952680538940505433112075930728150593348635525487777442963225326289120005105942009379392399549768222904714335587064965943025883665161298876255240853799813319173541181397920169431341225855464506094308431894355976456616552243350757295794274103766488587493403745572938023109847623467233499594760052941076253544804607600806063492315687419590824313035155495322099282602206575716795686579274404530700878310553860840075533978970313868303268348968123830261107378525434730476155224319783326457731179933403040373373513663409359939556713528784760662130976010031445893240306115071698977633370081285021996081889866339554439030258689926816839459672349572981894713132669503720080825550314634827974834111135884327479840874856406704989600384782896014126394900096316936191822061604501251999538344900075456781099804476987941975749466091947916959084522070649368611024859576617679719912273442154392834558334485913297306149687463050858300178589163647727264373616866934235698778375400684831818105359191807090147530722705717027718640146392024267134962534073989786676885904328529992088901061477810844396953510495214390524762275536691861895423586264465164725740348030841559394619283212590085139714355818004331507117086865037471698474681961819268100298082475664418905351845646033186826702738190904752418448024312122874238653934017086873374556463443645085632505731346752773227640998162989971115011361849940254671486438090582719295319889678616480620657813783138224459920080909731816532435555059792303460051710222043788364485705803898922576121691786795769314871145350585237724501072510832249570059794020119350643510305688568246082138494920459453811812581825736849524777703220341825744979233777139161152867568397785641963636669540758862735103120386388954775830331682383170875177539060717378521153720999893078493738144598688821475846843537696741577274782076483996232679823975388834591135615695494497619841829196281769585395730856015357146391920884962079419788849671641593481052050858710399263519566383349271005947865683425462712430893507169269608487220667193961365500208793718669532672782433859614217392866701136490320043936895463681443550084616585257282179705882681426252239806728153122577322523327938614442576466221682889501747578160491590888486986413952574574417981777668428162319745575688857063620009672969964906294132424597878413674782384355992292957599025606272133217638318467921927254853725179624905946654971750248321718919983352554139549960613440945135063912560448331100229095455459868779391498683820423958166072743995598190911920585944019297389754958734961703000839661563087206444223638379252099015274749502115873742073269764203776964296057528352381794613150551737665105856274242718076573793899323417606096539619015279321213731467752665656665563262648200304204650779359810654065948808024247440092068079186241284126574359983902720032777339632477025162655404597530346242813174477583419225166728353026302670093240319294012281236946269041889392699809915794650841899872777464974521350123638079156477221164102550780694318110264365742612140703581132958639748389286696158157101918872246915899757974446368051307915707695178031057812180446808604258885258957502474048267815718369842503522659004754833798095789660916425455565990380991332902234007951931388391969465358626614736267112951367436937397323278176669260656847908458434257592787928921350031532312298293147204602982517875715301803422814972177220808817322728517063590028270807420546881710724894028229355135387259801435676527204916995565664049037929909899806932636810603860026476225075911244308932907821666690512655315131809317268282788637121740948256128007237130128275345653111893740753660953615156706961863983815828043076987086619917404521350508481525971244475840886105350424062492056983002524347066028789924820302354525617169585818271476045073801729294906399100444971566147560806094353685649968843289464395074043266462835570320225427620318439203836843781986815254869839478423063207607950575995797068006265411925792137097671558992165741166579806000823406002348927039276640883619196770138718620522358389403691812979046572135592699639665699565160272535288210179012315864025448352476162477980599847927834499817197182557732085388517809025485001746194188221500219729084713772439508357060846413203229354597109403144097046076106777627074615753206039514145099843069544849907261285374315521884205094839140077972052113910827700433833533195095289050030294256170489553443994111098268561032914807626322859352968954864624163264797120940408256574139730558579817592795684579438059220658895058041261695610070963907309083666004439202504322139014462699084814011176672110434345588598156748048117460923964382157747811149329705621520605486817468160076811391614113105794003617852541517200552077964551044754791847748054227907360598462456043406019493357667165955562926631792324350764081020489540627309119524703617586369707304815238370306308759632566956470290404936402049307854833321916357103544949299888067390298592507395901401441502542841938592559349497396214323731857557713305074567522366954657961936003512614522765507165626460919754145222041018228897254305726755428439389964453623380276774365218774539032393211163180834098215060648378716911568535740816976293148821572389780196770695202697003765056785071850033331273322015268099191299409061810263666149225513799905741479593420601854582820063321245261325008506832047328279230239895152945020063451638105810941102239536156290437878018245339806504994293906452955120444261885741882061731036442553358864706558163689369851297647325533594481086232464648030351316985095761294514040778603364410944828292472741221382736342742756006421014723581272582446712591180242335069384282988637703230238721301206701058421558702079650096771934426949772668550906655077064126007124879048779692651159626267887153103989087015621234810889476653679401501072304356090887981283160917876677210369519273529322623887080831983181918841137904043243409988480250085922793448986468738365936679417026102875460159987194566165470416808255718158250643035430102244076907735762508373942459764672386109089689892414160826570705396313057031967913834700469093586360166251234710179642805886327558510655653942850643467077146599446616384899847125627879899301234865243143627438171700746460808532039052870054242884593575882889607833889457727580760142131225453842753868968819796062311706638373745389766978772920651890261300367001668147716249037758503300878223042572801391341555905355459249704629195525911947584581014131812022033833116089251629389123769176947301494827730836780968354751066449063737025479074074245856157821593924037392070850810032699400228082009328323231154189214275133513018970997849560488937871683531281338761559984889674194173148231882330832600483976903999007546002498462597464299971040955904972020017958705024723522441387421870472997388097191293448377911973265241173534257086399454324450485089946294663046477667154441805236317818458906629516169208154526151315617330670283223218993091900911765682141730466091313452218042531797723946292358955418951289110906622091567226488055045979246380762361941436514821475222262512680337778902784842389712032032130084017679701773886952203168257322864970051809257340534140265340200866802112386503407620820264688667366957282116700299653886224110191383006293259473815849306533516420046463767221456140174501544468412399409875186524218934915438003721881045821282703695252798667918656886609245099391504125431711846592149184051817465437349977174347837606342760204652088659164519539922168629606647891302584313333437561767097111434016423162643732303555217933863437776784586509910921216797793093304330231034562622395264009404026855934414285180439964826510838242640371415473486249048729519858741002205884017462988017928172952645887687784314388566048087532515201377819448609142557022770281845499435897397281102140095532371776104076975732393045106245693068996512823173232489771857906986985204778673860364231244043612467408169586743226755522055777584290442703332547583332732967539508392379151251321124704491640230355857776539611337747118874218276417528225889674707284885735356358382854200935084500745010833537679268995256161120875502448514567760351387650311731287040101064712539560262530297789672721086032881550616445083241975850148461266940099398925243382131479074052311643785629349349880883900832357058608177198562045001265455158322670854789245768692247464561027993647527164672568939500013444099092189846238207412425584187502950907741807785297907295647474777842348427192411545174615971256410794586811930576920597061283872380688225040931478778844020901470946467312081133168383151995754191710819056338637795809958635796220949489786910647430131255248202082854990010963954915193148727218306105613718402254220252120966462962463276648846953811793913954119951607653290213646590366257862538126290875136128539132829274729123300670065575643732429949108873614165185893325426741854073363226249692874485150925886864130547106881249890867267498019733417458259885949020362765524694742412144456254270044159576397383977902083490960194766511852529279622877032324846136135703995030201160350261640251358015958859079290501427051917053220092317924591467349957486672816970367146281626571039631839017196390467313370078725735613114129599537865596428324977661784861101087632613962743201206743346610160974347425620162114921023690344574221474983119943114407206893107461402235276756247259833002706319719088651822495170773670101048510985648393283651280031657365265668206594927455951998307908821384284578377786987830102020407192211890338029704955782314718971341677121917654728886960073281135057236117551596007829291384717912022425858119805221912896124810881753204662239669935353419459999008531250745154889933444822638878124608978432471852854623282403280920181481186464310792655039504154593225406285433355623610861835852107682352875496220312435855448925363298214142647974637259090049401236137298275444870575949791750744411457589313632569792802726058546026593513791944965772645398373453284070590856126558837292055546988436660443564983511472430877083527754906745260731762414650843380006266310470712004781161897897983562336143779820591891375214738147796050153044109677157374732113871428801990290704386758852511753497780559721643875320740234107435351389002122886562278711700400998034025420496659471509050546405003810900479545359277796814742422888166411785591096780582395263750564539544648991518360267309909793899802295658384215335624896772299185838588471595721894064341817922979846887606306363202934778363118638607195732210319573692213320226496212377097232776650280948653029712615343062182437706434492764120595897200779999780868894812718948887128501298956774390296751240376170729454946365759048694518270378730264607614471972985991149551940402652477921927044089937950348975699766032253467964963737678221848200983819412892148330385997139587788295876113804291626359032297511319134899061087376259605564672155914921802313771988654778693375972879181050132446523746060449231993904233982672262835153220072712109290775578271228853364184185228698342485321632136502937549482654279517678052996050785243384384058128780420660529253115640056282090940037042135483376886732494354664928950500878867031579320450414382992620009252978018553646568000962682388709432035209782586463767979368992024543452334855686772326356983596758925801126535416178710682880074666000622193730746818392066059256325819081690408769018168017173064110788053139886769597301683514564798990205810253947331763155781800208086924188690932284987947630392059596888534627059112301771760501487361458521987196213591855744144613616302585063419358325651139947839321964023493397425927178172848197915030663878665557892938749011612605284649464267004525652064304741934191644127769757359217920235087660873154796569350159265387172420905034663776646500958039664986193224765031663610953836459399080886452351477709273172155363796168648962409233752840696835447043851832483645383284548249948048507276208964256777184422574004963052989715081256327376718992437219942297671010004924320058004897484941275968437270536703157455329406363805822341831237917998873175813772145577116894769354547761401461155314249393178873456519975392121918019012831439405169113792038871988339492614357476912228217660535702146783049238999365845994575191094951906196379740519757090907804226553443599071553295378092984118203113032396541138588441038826629293694077894093015806320724193918502876739928855275221924314853301197933748392413352237681326865802135963339166417905037052807049658315100181874653664359831865934884969520601418977194151998242549054131632967122552724854869127759759634291858587983843705499811769987117567468687946038714975392564315003961838292191737956854765660172117108728297508105641492940809020929325666817806570006830692366760736425478289110751151782561008808977146996309744817294166513273638069988920283912595811449273074248519927565105178767834291852674929468558435489239974000862490414944937456643825941231672457623789548791378557960240551917898552708591002918250529601549989541849633919157655470608074666270535483794207125576285415223668173099762278406527318388201878640424556621653721019266410843331116329388659400568962882971082297331707823855230753956073037891910721750189880384013187346223372171098013621513884886508862429098931596287249921691399542732147012069775511068713146346520256362219959105914129473554905496655303859983691769785915436781746168690034710919369005590137970947358525369855659305331970094684472321122713072727550846610760770599690497959338314058037155309683378375263488274716507235493595329132691627180116503218155620267384747321312021432845876715701713708982232692834099148408860495140307534840758730328590908191410138953864509819255932336894201926818088554661558271492593039551678828091962105082644480974005499881334590682565442542251470440607391935005716756962969633396116680693840548065797448446191814107477730444383216910054354698420964162392835082489955747930497798810371744180848476136862551414125951348575757687024835027211380965422039072283636251413370710568492499449854565225776485666139900068764217000475005875487362029073322005180003839476317508324140165184626463378265344239891535609714966252524456542011112110268517384646038893930789182908202749173592508621521965900014603594125261572859175616043119293876481256072942355007918872108162926697168795532222265305459300668777886829315743812016199414387246146683517071886869678074958527306200955866533501217590227882953219735671906412160421559502336345619794621582753801156419042014314756642399090473599915500084217999604434277409457751863380315517962339407696607173148422379600729174630189562956213451379531368453527794205273942534410801452384204033170245702779681536228618272373239264244598120007230512276293104523529217928549077467552158120984625533516460163222926068748233473110966560180056702595162762215914091365195281331960134081407474109223336704920381376694266546564087520457945062098409146620693074310679187424255721361516614781361194016624696895842695903803343579910106063298889692578541626802346560583100633747354337407934313565705254519304973967146885442085857802708776383358276365405086853295174806607132271222643953230617934451814439436185047484901159323083380287884219035205579366934892797076911345721526124885797554648608556958007202098342427437432519797256899166093398874274460025233125486206529441200438687836975825643669634856696299955576117061673759191975358200811003771452160907340515326715482086200007493660885883881039539696860001").unwrap());
        let hundred_thousand_digits = subfactorial(25_206);
        assert_eq!(length(&hundred_thousand_digits, FLOAT_PRECISION), 100_000);
    }

    #[test]
    fn test_calculate_termial() {
        assert_eq!(termial(0.into()), Integer::from(0));
        assert_eq!(termial(1.into()), Integer::from(1));
        assert_eq!(termial(2.into()), Integer::from(3));
        assert_eq!(termial(3.into()), Integer::from(6));
        assert_eq!(termial(4.into()), Integer::from(10));
        assert_eq!(termial(5.into()), Integer::from(15));
        assert_eq!(termial(6.into()), Integer::from(21));
        assert_eq!(termial(7.into()), Integer::from(28));
        assert_eq!(termial(8.into()), Integer::from(36));
        assert_eq!(termial(9.into()), Integer::from(45));
        assert_eq!(termial(10.into()), Integer::from(55));
        assert_eq!(
            termial(9572950215078573219358678320u128.into()),
            Integer::from_str("45820687910186450629655988665746507398291523758298350360").unwrap()
        );
        assert_eq!(
            termial(Integer::from_str(&"9".repeat(10000)).unwrap()),
            Integer::from_str("49999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000").unwrap()
        );
    }
    #[test]
    fn test_calculate_multitermial() {
        assert_eq!(multitermial(0.into(), 2), Integer::from(0));
        assert_eq!(multitermial(1.into(), 2), Integer::from(1));
        assert_eq!(multitermial(2.into(), 2), Integer::from(2));
        assert_eq!(multitermial(3.into(), 2), Integer::from(4));
        assert_eq!(multitermial(4.into(), 2), Integer::from(6));
        assert_eq!(multitermial(5.into(), 2), Integer::from(9));
        assert_eq!(multitermial(6.into(), 2), Integer::from(12));
        assert_eq!(multitermial(7.into(), 2), Integer::from(16));
        assert_eq!(multitermial(8.into(), 2), Integer::from(20));
        assert_eq!(multitermial(9.into(), 2), Integer::from(25));
        assert_eq!(multitermial(10.into(), 2), Integer::from(30));
        assert_eq!(
            multitermial(9572950215078573219358678320u128.into(), 2),
            Integer::from_str("22910343955093225314827994335266491252915405183988844760").unwrap()
        );
        assert_eq!(multitermial(1000.into(), 2), Integer::from(250500));
        assert_eq!(multitermial(1000.into(), 3), Integer::from(167167));
        assert_eq!(multitermial(1000.into(), 5), Integer::from(100500));
        assert_eq!(multitermial(1000.into(), 10), Integer::from(50500));
        assert_eq!(multitermial(1000.into(), 100), Integer::from(5500));
        assert_eq!(multitermial(1000.into(), 500), Integer::from(1500));
    }

    #[test]
    fn test_fractional_factorial() {
        assert_eq!(
            fractional_factorial(Float::with_val(FLOAT_PRECISION, 0.0)).to_f64(),
            1.0
        );
        assert_eq!(
            fractional_factorial(Float::with_val(FLOAT_PRECISION, 0.000001)).to_f64(),
            0.9999994227853242
        );
        assert_eq!(
            fractional_factorial(Float::with_val(FLOAT_PRECISION, 0.1)).to_f64(),
            0.9513507698668732
        );
        assert_eq!(
            fractional_factorial(Float::with_val(FLOAT_PRECISION, 15.389)).to_f64(),
            3816538254129.559 // .566
        );
        assert_eq!(
            fractional_factorial(Float::with_val(FLOAT_PRECISION, 170.624376)).to_f64(),
            1.7976842943982611e308 // 1478
        );
    }
    #[test]
    #[ignore = "future improvement"]
    fn test_fractional_factorial_perfect() {
        assert_eq!(
            fractional_factorial(Float::with_val(FLOAT_PRECISION, 0.0)).to_f64(),
            1.0
        );
        assert_eq!(
            fractional_factorial(Float::with_val(FLOAT_PRECISION, 0.000001)).to_f64(),
            0.9999994227853242
        );
        assert_eq!(
            fractional_factorial(Float::with_val(FLOAT_PRECISION, 0.1)).to_f64(),
            0.9513507698668732
        );
        assert_eq!(
            fractional_factorial(Float::with_val(FLOAT_PRECISION, 15.389)).to_f64(),
            3816538254129.566
        );
        assert_eq!(
            fractional_factorial(Float::with_val(FLOAT_PRECISION, 170.624376)).to_f64(),
            1.7976842943981478e308
        );
    }

    #[test]
    fn test_fractional_multifactorial() {
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 0.0), 1).to_f64(),
            1.0
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 0.000001), 1).to_f64(),
            0.9999994227853242
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 0.1), 1).to_f64(),
            0.9513507698668732
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 15.389), 1).to_f64(),
            3816538254129.559 // 566
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 170.624376), 1).to_f64(),
            1.7976842943982611e308 // 1478
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 0.0), 2).to_f64(),
            1.0
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 0.000001), 2).to_f64(),
            1.000000057965408
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 0.1), 2).to_f64(),
            1.0022813772211305 // 6
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 15.389), 2).to_f64(),
            3753266.6800373434 // 77
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 170.624376), 2).to_f64(),
            4.645270661441449e154 // 321
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 170), 5).to_f64(),
            1.7184810657031144e62
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 2.6), 5).to_f64(),
            2.4698196281039353
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 170), 50).to_f64(),
            28560000.0
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 170), 100).to_f64(),
            11900.0
        );
    }
    #[test]
    #[ignore = "future_improvement"]
    fn test_fractional_multifactorial_perfect() {
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 0.0), 1).to_f64(),
            1.0
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 0.000001), 1).to_f64(),
            0.9999994227853242
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 0.1), 1).to_f64(),
            0.9513507698668732
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 15.389), 1).to_f64(),
            3816538254129.566
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 170.624376), 1).to_f64(),
            1.7976842943981478e308
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 0.0), 2).to_f64(),
            1.0
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 0.000001), 2).to_f64(),
            1.000000057965408
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 0.1), 2).to_f64(),
            1.0022813772211306
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 15.389), 2).to_f64(),
            3753266.6800373477
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 170.624376), 2).to_f64(),
            4.645270661441321e154
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 170), 5).to_f64(),
            1.7184810657031144e62
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 2.6), 5).to_f64(),
            2.4698196281039353
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 170), 50).to_f64(),
            28560000.0
        );
        assert_eq!(
            fractional_multifactorial(Float::with_val(FLOAT_PRECISION, 170), 100).to_f64(),
            11900.0
        );
    }

    #[test]
    fn test_fractional_termial() {
        assert_eq!(
            fractional_termial(Float::with_val(FLOAT_PRECISION, 0.0)).to_f64(),
            0.0
        );
        assert_eq!(
            fractional_termial(Float::with_val(FLOAT_PRECISION, 0.000001)).to_f64(),
            5.000005e-7
        );
        assert_eq!(
            fractional_termial(Float::with_val(FLOAT_PRECISION, 0.1)).to_f64(),
            0.055
        );
        assert_eq!(
            fractional_termial(Float::with_val(FLOAT_PRECISION, 15.389)).to_f64(),
            126.1051605
        );
        assert_eq!(
            fractional_termial(Float::with_val(FLOAT_PRECISION, 170.624376)).to_f64(),
            14641.65103069469
        );
    }

    /// Formats the output of [`approximate_factorial`], by combining the 10 exponents of the number and the extra exponent.
    ///
    /// Moved here, because it only serves now as a better way to write tests (no need to write the full Float)
    fn format_approximate((x, e): (Float, Integer)) -> String {
        let (x, e) = (x, e);
        let x = x.to_f64();
        format!("{x} × 10^{e}")
    }

    #[test]
    fn test_approximate_factorial() {
        // NOTE: the last digit may not be correct
        assert_eq!(
            format_approximate(approximate_factorial(100_001.into(), FLOAT_PRECISION)),
            "2.8242576502544274 × 10^456578"
        );
        assert_eq!(
            format_approximate(approximate_factorial(
                2_546_372_899u128.into(),
                FLOAT_PRECISION
            )),
            "7.754784101805052 × 10^22845109185"
        );
        assert_eq!(
            format_approximate(approximate_factorial(
                500_000_000_000u128.into(),
                FLOAT_PRECISION
            )),
            "4.286111886996677 × 10^5632337761222"
        );
        assert_eq!(
            format_approximate(approximate_factorial(
                712_460_928_486u128.into(),
                FLOAT_PRECISION
            )),
            "2.988979640465335 × 10^8135211294800"
        );
        assert_eq!(
            format_approximate(approximate_factorial(
                8_392_739_232_838_237_120u128.into(),
                FLOAT_PRECISION
            )),
            "5.321682559738788 × 10^155178468932549925384"
        );
        assert_eq!(
            format_approximate(approximate_factorial(
                78_473_843_792_461_001_798_392_739_232_838_237_120u128.into(),
                FLOAT_PRECISION
            )),
            "1.726535267725453 × 10^2939663967042394848929844071091736224040"
        );
        assert_eq!(
            format_approximate(approximate_factorial(u128::MAX.into(), FLOAT_PRECISION)),
            "4.780505917797121 × 10^12963922773915897352139996524992575205341"
        );
        assert_eq!(
            format_approximate(approximate_factorial(
                Integer::from_str(
                    "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
                )
                .unwrap()
            , FLOAT_PRECISION)),
            "6.185167193060592 × 10^197565705518096748172348871081083394917705602994196333433885546216834135350791129225270775050661568251681293893255233696266358320712841036093430778935337187734147872913431329670406629130341173311668935"
        );
        assert_eq!(
            format_approximate(approximate_factorial(
                Integer::from_str(&format!("1{}", "0".repeat(300))).unwrap(),
                FLOAT_PRECISION
            )),
            // NOTE: Only the first 5 decimals are correct
            "4.6075702908405205 × 10^299565705518096748172348871081083394917705602994196333433885546216834135350791129225270775050661568251681293893255233696266358320712841036093430778935337187734147872913431329670406629130341173311668836392261509485715565133323135341391486443851787651234656456564268274616437771860439695135334763390446212"
        );
    }
    #[test]
    #[ignore = "future_improvement"]
    fn test_approximate_factorial_perfect() {
        // NOTE: all decimal are correct
        assert_eq!(
            format_approximate(approximate_factorial(100_001.into(), FLOAT_PRECISION)),
            "2.8242576502544275 × 10^456578"
        );
        assert_eq!(
            format_approximate(approximate_factorial(
                2_546_372_899u128.into(),
                FLOAT_PRECISION
            )),
            "7.7547841018050521 × 10^22845109185"
        );
        assert_eq!(
            format_approximate(approximate_factorial(
                500_000_000_000u128.into(),
                FLOAT_PRECISION
            )),
            "4.2861118869966772 × 10^5632337761222"
        );
        assert_eq!(
            format_approximate(approximate_factorial(
                712_460_928_486u128.into(),
                FLOAT_PRECISION
            )),
            "2.988979640465335 × 10^8135211294800"
        );
        assert_eq!(
            format_approximate(approximate_factorial(
                8_392_739_232_838_237_120u128.into(),
                FLOAT_PRECISION
            )),
            "5.321682559738788 × 10^155178468932549925384"
        );
        assert_eq!(
            format_approximate(approximate_factorial(
                78_473_843_792_461_001_798_392_739_232_838_237_120u128.into(),
                FLOAT_PRECISION
            )),
            "1.726535267725453 × 10^2939663967042394848929844071091736224040"
        );
        assert_eq!(
            format_approximate(approximate_factorial(u128::MAX.into(), FLOAT_PRECISION)),
            "4.780505917797121 × 10^12963922773915897352139996524992575205341"
        );
        assert_eq!(
            format_approximate(approximate_factorial(
                Integer::from_str(
                    "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
                )
                .unwrap()
            , FLOAT_PRECISION)),
            "6.185167193060592 × 10^197565705518096748172348871081083394917705602994196333433885546216834135350791129225270775050661568251681293893255233696266358320712841036093430778935337187734147872913431329670406629130341173311668935"
        );
        assert_eq!(
            format_approximate(approximate_factorial(
                Integer::from_str(&format!("1{}", "0".repeat(300))).unwrap(),
                FLOAT_PRECISION
            )),
            "4.6075738185461799 × 10^299565705518096748172348871081083394917705602994196333433885546216834135350791129225270775050661568251681293893255233696266358320712841036093430778935337187734147872913431329670406629130341173311668836392261509485715565133323135341391486443851787651234656456564268274616437771860439695135334763390446212"
        );
    }
    #[test]
    fn test_approximate_multifactorial() {
        // NOTE: the last digit may not be correct
        assert_eq!(
            format_approximate(approximate_multifactorial(
                100_001.into(),
                2,
                FLOAT_PRECISION
            )),
            "2.669462450117582 × 10^228290"
        );
        assert_eq!(
            format_approximate(approximate_multifactorial(
                2_546_372_899u128.into(),
                2,
                FLOAT_PRECISION
            )),
            "1.766995271233595 × 10^11422554595"
        );
        assert_eq!(
            format_approximate(approximate_multifactorial(
                500_000_000_000u128.into(),
                2,
                FLOAT_PRECISION
            )),
            "1.948965818007459 × 10^2816168880614"
        );
        assert_eq!(
            format_approximate(approximate_multifactorial(
                712_460_928_486u128.into(),
                2,
                FLOAT_PRECISION
            )),
            "1.778204523968013 × 10^4067605647403"
        );
        assert_eq!(
            format_approximate(approximate_multifactorial(
                8_392_739_232_838_237_120u128.into(),
                2,
                FLOAT_PRECISION
            )),
            "1.3900498788571092 × 10^77589234466274962697"
        );
        assert_eq!(
            format_approximate(approximate_multifactorial(
                78_473_843_792_461_001_798_392_739_232_838_237_120u128.into(),
                2,
                FLOAT_PRECISION
            )),
            "4.3782335812047535 × 10^1469831983521197424464922035545868112029" // 3
        );
        assert_eq!(
            format_approximate(approximate_multifactorial(
                u128::MAX.into(),
                2,
                FLOAT_PRECISION
            )),
            "2.652569807741017 × 10^6481961386957948676069998262496287602680"
        );
        assert_eq!(
            format_approximate(approximate_multifactorial(
                Integer::from_str(
                    "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
                )
                .unwrap(),2
            , FLOAT_PRECISION)),
            "2.784233733852614 × 10^98782852759048374086174435540541697458852801497098166716942773108417067675395564612635387525330784125840646946627616848133179160356420518046715389467668593867073936456715664835203314565170586655834517"
        );
        assert_eq!(
            format_approximate(approximate_multifactorial(
                Integer::from_str(&format!("1{}", "0".repeat(300))).unwrap(),
                2,
                FLOAT_PRECISION
            )),
            // NOTE: Only the first 5 decimals are correct
            "2.4030665584107203 × 10^149782852759048374086174435540541697458852801497098166716942773108417067675395564612635387525330784125840646946627616848133179160356420518046715389467668593867073936456715664835203314565170586655834418196130754742857782566661567670695743221925893825617328228282134137308218885930219847567667381695223181"
        );
    }
    #[test]
    #[ignore = "future_improvement"]
    fn test_approximate_multifactorial_perfect() {
        // NOTE: all digits are correct
        assert_eq!(
            format_approximate(approximate_multifactorial(
                100_001.into(),
                2,
                FLOAT_PRECISION
            )),
            "2.669462450117582 × 10^228290"
        );
        assert_eq!(
            format_approximate(approximate_multifactorial(
                2_546_372_899u128.into(),
                2,
                FLOAT_PRECISION
            )),
            "1.766995271233595 × 10^11422554595"
        );
        assert_eq!(
            format_approximate(approximate_multifactorial(
                500_000_000_000u128.into(),
                2,
                FLOAT_PRECISION
            )),
            "1.948965818007459 × 10^2816168880614"
        );
        assert_eq!(
            format_approximate(approximate_multifactorial(
                712_460_928_486u128.into(),
                2,
                FLOAT_PRECISION
            )),
            "1.778204523968013 × 10^4067605647403"
        );
        assert_eq!(
            format_approximate(approximate_multifactorial(
                8_392_739_232_838_237_120u128.into(),
                2,
                FLOAT_PRECISION
            )),
            "1.3900498788571092 × 10^77589234466274962697"
        );
        assert_eq!(
            format_approximate(approximate_multifactorial(
                78_473_843_792_461_001_798_392_739_232_838_237_120u128.into(),
                2,
                FLOAT_PRECISION
            )),
            "4.3782335812047533 × 10^1469831983521197424464922035545868112029"
        );
        assert_eq!(
            format_approximate(approximate_multifactorial(
                u128::MAX.into(),
                2,
                FLOAT_PRECISION
            )),
            "2.652569807741017 × 10^6481961386957948676069998262496287602680"
        );
        assert_eq!(
            format_approximate(approximate_multifactorial(
                Integer::from_str(
                    "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
                )
                .unwrap(),2
            , FLOAT_PRECISION)),
            "2.784233733852614 × 10^98782852759048374086174435540541697458852801497098166716942773108417067675395564612635387525330784125840646946627616848133179160356420518046715389467668593867073936456715664835203314565170586655834517"
        );
        assert_eq!(
            format_approximate(approximate_multifactorial(
                Integer::from_str(&format!("1{}", "0".repeat(300))).unwrap(),
                2,
                FLOAT_PRECISION
            )),
            "2.4030683314272798 × 10^149782852759048374086174435540541697458852801497098166716942773108417067675395564612635387525330784125840646946627616848133179160356420518046715389467668593867073936456715664835203314565170586655834418196130754742857782566661567670695743221925893825617328228282134137308218885930219847567667381695223181"
        );
    }
    #[test]
    fn test_approximate_subfactorial() {
        // NOTE: the last digit may not be correct
        assert_eq!(
            format_approximate(approximate_subfactorial(100_001.into(), FLOAT_PRECISION)),
            "1.0389863260997696 × 10^456578"
        );
        assert_eq!(
            format_approximate(approximate_subfactorial(
                2_546_372_899u128.into(),
                FLOAT_PRECISION
            )),
            "2.852825641777228 × 10^22845109185"
        );
        assert_eq!(
            format_approximate(approximate_subfactorial(
                500_000_000_000u128.into(),
                FLOAT_PRECISION
            )),
            "1.5767724457866137 × 10^5632337761222"
        );
        assert_eq!(
            format_approximate(approximate_subfactorial(
                712_460_928_486u128.into(),
                FLOAT_PRECISION
            )),
            "1.099584159807206 × 10^8135211294800"
        );
        assert_eq!(
            format_approximate(approximate_subfactorial(
                8_392_739_232_838_237_120u128.into(),
                FLOAT_PRECISION
            )),
            "1.957737606168516 × 10^155178468932549925384"
        );
        assert_eq!(
            format_approximate(approximate_subfactorial(
                78_473_843_792_461_001_798_392_739_232_838_237_120u128.into(),
                FLOAT_PRECISION
            )),
            "6.3515682945362615 × 10^2939663967042394848929844071091736224039"
        );
        assert_eq!(
            format_approximate(approximate_subfactorial(u128::MAX.into(), FLOAT_PRECISION)),
            "1.7586498455559778 × 10^12963922773915897352139996524992575205341"
        );
        assert_eq!(
            format_approximate(approximate_subfactorial(
                Integer::from_str(
                    "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
                )
                .unwrap()
            , FLOAT_PRECISION)),
            "2.275395850535069 × 10^197565705518096748172348871081083394917705602994196333433885546216834135350791129225270775050661568251681293893255233696266358320712841036093430778935337187734147872913431329670406629130341173311668935"
        );
        assert_eq!(
            format_approximate(approximate_subfactorial(
                Integer::from_str(&format!("1{}", "0".repeat(300))).unwrap(),
                FLOAT_PRECISION
            )),
            // NOTE: Only the first 5 decimals are correct
            "1.6950303837525507 × 10^299565705518096748172348871081083394917705602994196333433885546216834135350791129225270775050661568251681293893255233696266358320712841036093430778935337187734147872913431329670406629130341173311668836392261509485715565133323135341391486443851787651234656456564268274616437771860439695135334763390446212"
        );
    }
    #[test]
    #[ignore = "future_improvement"]
    fn test_approximate_subfactorial_perfect() {
        // NOTE: all decimal are correct
        assert_eq!(
            format_approximate(approximate_subfactorial(100_001.into(), FLOAT_PRECISION)),
            "1.0389863260997696 × 10^456578"
        );
        assert_eq!(
            format_approximate(approximate_subfactorial(
                2_546_372_899u128.into(),
                FLOAT_PRECISION
            )),
            "2.852825641777228 × 10^22845109185"
        );
        assert_eq!(
            format_approximate(approximate_subfactorial(
                500_000_000_000u128.into(),
                FLOAT_PRECISION
            )),
            "1.5767724457866138 × 10^5632337761222"
        );
        assert_eq!(
            format_approximate(approximate_subfactorial(
                712_460_928_486u128.into(),
                FLOAT_PRECISION
            )),
            "1.099584159807206 × 10^8135211294800"
        );
        assert_eq!(
            format_approximate(approximate_subfactorial(
                8_392_739_232_838_237_120u128.into(),
                FLOAT_PRECISION
            )),
            "1.957737606168516 × 10^155178468932549925384"
        );
        assert_eq!(
            format_approximate(approximate_subfactorial(
                78_473_843_792_461_001_798_392_739_232_838_237_120u128.into(),
                FLOAT_PRECISION
            )),
            "6.3515682945362619 × 10^2939663967042394848929844071091736224039"
        );
        assert_eq!(
            format_approximate(approximate_subfactorial(u128::MAX.into(), FLOAT_PRECISION)),
            "1.7586498455559779 × 10^12963922773915897352139996524992575205341"
        );
        assert_eq!(
            format_approximate(approximate_subfactorial(
                Integer::from_str(
                    "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
                )
                .unwrap()
            , FLOAT_PRECISION)),
            "2.275395850535069 × 10^197565705518096748172348871081083394917705602994196333433885546216834135350791129225270775050661568251681293893255233696266358320712841036093430778935337187734147872913431329670406629130341173311668935"
        );
        assert_eq!(
            format_approximate(approximate_subfactorial(
                Integer::from_str(&format!("1{}", "0".repeat(300))).unwrap(),
                FLOAT_PRECISION
            )),
            "1.6950316815229372 × 10^299565705518096748172348871081083394917705602994196333433885546216834135350791129225270775050661568251681293893255233696266358320712841036093430778935337187734147872913431329670406629130341173311668836392261509485715565133323135341391486443851787651234656456564268274616437771860439695135334763390446212"
        );
    }
    #[test]
    fn test_approximate_termial() {
        // NOTE: the last digit may not be correct
        assert_eq!(
            format_approximate(approximate_termial(100_001.into(), 1, FLOAT_PRECISION)),
            "5.000150001 × 10^9"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                2_546_372_899u128.into(),
                1,
                FLOAT_PRECISION
            )),
            "3.2420074716540186 × 10^18"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                500_000_000_000u128.into(),
                1,
                FLOAT_PRECISION
            )),
            "1.2500000000025 × 10^23"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                712_460_928_486u128.into(),
                1,
                FLOAT_PRECISION
            )),
            "2.538002873099228 × 10^23"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                8_392_739_232_838_237_120u128.into(),
                1,
                FLOAT_PRECISION
            )),
            "3.521903591521108 × 10^37"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                78_473_843_792_461_001_798_392_739_232_838_237_120u128.into(),
                1,
                FLOAT_PRECISION
            )),
            "3.079072079781785 × 10^75"
        );
        assert_eq!(
            format_approximate(approximate_termial(u128::MAX.into(), 1, FLOAT_PRECISION)),
            "5.789604461865809 × 10^76"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                Integer::from_str(
                    "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
                )
                .unwrap(),1
            , FLOAT_PRECISION)),
            "5 × 10^395"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                Integer::from_str(&format!("1{}", "0".repeat(300))).unwrap(),
                1,
                FLOAT_PRECISION
            )),
            "5 × 10^599"
        );
        let mut max = Float::with_val(FLOAT_PRECISION, rug::float::Special::Infinity);
        max.next_down();
        assert_eq!(
            format_approximate(approximate_termial(
                max.to_integer().unwrap(),
                1,
                FLOAT_PRECISION
            )),
            "2.202016314604954 × 10^646456992"
        );
        assert_eq!(
            format_approximate(approximate_termial(100_001.into(), 2, FLOAT_PRECISION)),
            "2.50010000075 × 10^9"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                2_546_372_899u128.into(),
                2,
                FLOAT_PRECISION
            )),
            "1.6210037364636025 × 10^18"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                500_000_000_000u128.into(),
                2,
                FLOAT_PRECISION
            )),
            "6.250000000025 × 10^22"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                712_460_928_486u128.into(),
                2,
                FLOAT_PRECISION
            )),
            "1.2690014365513953 × 10^23"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                8_392_739_232_838_237_120u128.into(),
                2,
                FLOAT_PRECISION
            )),
            "1.760951795760554 × 10^37"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                78_473_843_792_461_001_798_392_739_232_838_237_120u128.into(),
                2,
                FLOAT_PRECISION
            )),
            "1.5395360398908926 × 10^75"
        );
        assert_eq!(
            format_approximate(approximate_termial(u128::MAX.into(), 2, FLOAT_PRECISION)),
            "2.8948022309329047 × 10^76"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                Integer::from_str(
                    "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
                )
                .unwrap()
                ,2
            , FLOAT_PRECISION)),
            "2.5 × 10^395"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                Integer::from_str(&format!("1{}", "0".repeat(300))).unwrap(),
                2,
                FLOAT_PRECISION
            )),
            "2.5 × 10^599"
        );
        assert_eq!(
            format_approximate(approximate_termial(u128::MAX.into(), 2, FLOAT_PRECISION)),
            "2.8948022309329047 × 10^76"
        );
        assert_eq!(
            format_approximate(approximate_termial(u128::MAX.into(), 5, FLOAT_PRECISION)),
            "1.1579208923731619 × 10^76"
        );
        assert_eq!(
            format_approximate(approximate_termial(u128::MAX.into(), 20, FLOAT_PRECISION)),
            "2.8948022309329047 × 10^75"
        );
        assert_eq!(
            format_approximate(approximate_termial(u128::MAX.into(), 200, FLOAT_PRECISION)),
            "2.8948022309329047 × 10^74"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                u128::MAX.into(),
                20000,
                FLOAT_PRECISION
            )),
            "2.8948022309329047 × 10^72"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                u128::MAX.into(),
                2000000,
                FLOAT_PRECISION
            )),
            "2.8948022309329047 × 10^70"
        );
    }
    #[test]
    #[ignore = "future_improvement"]
    fn test_approximate_termial_perfect() {
        // NOTE: all decimal are correct
        assert_eq!(
            format_approximate(approximate_termial(100_001.into(), 1, FLOAT_PRECISION)),
            "5.000150001 × 10^9"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                2_546_372_899u128.into(),
                1,
                FLOAT_PRECISION
            )),
            "3.2420074716540186 × 10^18"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                500_000_000_000u128.into(),
                1,
                FLOAT_PRECISION
            )),
            "1.2500000000025 × 10^23"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                712_460_928_486u128.into(),
                1,
                FLOAT_PRECISION
            )),
            "2.538002873099228 × 10^23"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                8_392_739_232_838_237_120u128.into(),
                1,
                FLOAT_PRECISION
            )),
            "3.521903591521108 × 10^37"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                78_473_843_792_461_001_798_392_739_232_838_237_120u128.into(),
                1,
                FLOAT_PRECISION
            )),
            "3.079072079781785 × 10^75"
        );
        assert_eq!(
            format_approximate(approximate_termial(u128::MAX.into(), 1, FLOAT_PRECISION)),
            "5.78960446186581 × 10^76"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                Integer::from_str(
                    "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
                )
                .unwrap(),1
            , FLOAT_PRECISION)),
            "5 × 10^395"
        );
        assert_eq!(
            format_approximate(approximate_termial(
                Integer::from_str(&format!("1{}", "0".repeat(300))).unwrap(),
                1,
                FLOAT_PRECISION
            )),
            "5 × 10^599"
        );
        let mut max = Float::with_val(FLOAT_PRECISION, rug::float::Special::Infinity);
        max.next_down();
        assert_eq!(
            format_approximate(approximate_termial(
                max.to_integer().unwrap(),
                1,
                FLOAT_PRECISION
            )),
            "2.202016314604954 × 10^646456992"
        );
    }

    #[test]
    fn test_approximate_digits() {
        assert_eq!(
            approximate_multifactorial_digits(100_001.into(), 1, FLOAT_PRECISION),
            456_579u128
        );
        assert_eq!(
            approximate_multifactorial_digits(7_834_436_739u128.into(), 1, FLOAT_PRECISION),
            74_111_525_394u128
        );
        assert_eq!(
            approximate_multifactorial_digits(738_247_937_346_920u128.into(), 1, FLOAT_PRECISION),
            10_655_802_631_914_633u128
        );
        assert_eq!(
            approximate_multifactorial_digits(
                827_829_849_020_729_846u128.into(),
                1,
                FLOAT_PRECISION
            ),
            14_473_484_525_026_753_452u128
        );
        assert_eq!(
            approximate_multifactorial_digits(
                1_000_000_000_000_000_000u128.into(),
                1,
                FLOAT_PRECISION
            ),
            17_565_705_518_096_748_182u128
        );
        assert_eq!(
            approximate_multifactorial_digits(
                1_000_000_000_000_000_000_000_000_000_000_000_000u128.into(),
                1,
                FLOAT_PRECISION
            ),
            35_565_705_518_096_748_172_348_871_081_083_394_936u128 // NOTE: Last digit is wrong
        );
        assert_eq!(
            approximate_multifactorial_digits(u128::MAX.into(), 1, FLOAT_PRECISION),
            Integer::from_str("12963922773915897352139996524992575205342").unwrap()
        );
        assert_eq!(
            approximate_multifactorial_digits(
                Integer::from_str(
                    "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
                )
                .unwrap(),
                1
            , FLOAT_PRECISION),
            Integer::from_str("197565705518096748172348871081083394917705602994196333433885546216834135350791129225270775050661568251681293893255233696266358320712841036093430778935337187734147872913431329670406629130341173311668936").unwrap()
        );
        assert_eq!(
            approximate_multifactorial_digits(100_001.into(), 2, FLOAT_PRECISION),
            228_291u128
        );
        assert_eq!(
            approximate_multifactorial_digits(7_834_436_739u128.into(), 2, FLOAT_PRECISION),
            37_055_762_699u128
        );
        assert_eq!(
            approximate_multifactorial_digits(738_247_937_346_920u128.into(), 2, FLOAT_PRECISION),
            5_327_901_315_957_320u128 // NOTE: Last digit is wrong
        );
        assert_eq!(
            approximate_multifactorial_digits(
                827_829_849_020_729_846u128.into(),
                2,
                FLOAT_PRECISION
            ),
            7_236_742_262_513_376_731u128
        );
        // TODO(test): test digit approximations for n-factorials (need to find a good reference)
    }

    #[test]
    #[ignore = "future_improvement"]
    fn test_approximate_digits_perfect() {
        // NOTE: All correct
        assert_eq!(
            approximate_multifactorial_digits(100_001.into(), 1, FLOAT_PRECISION),
            456_579u128
        );
        assert_eq!(
            approximate_multifactorial_digits(7_834_436_739u128.into(), 1, FLOAT_PRECISION),
            74_111_525_394u128
        );
        assert_eq!(
            approximate_multifactorial_digits(738_247_937_346_920u128.into(), 1, FLOAT_PRECISION),
            10_655_802_631_914_633u128
        );
        assert_eq!(
            approximate_multifactorial_digits(
                827_829_849_020_729_846u128.into(),
                1,
                FLOAT_PRECISION
            ),
            14_473_484_525_026_753_452u128
        );
        assert_eq!(
            approximate_multifactorial_digits(
                1_000_000_000_000_000_000u128.into(),
                1,
                FLOAT_PRECISION
            ),
            17_565_705_518_096_748_182u128
        );
        assert_eq!(
            approximate_multifactorial_digits(
                1_000_000_000_000_000_000_000_000_000_000_000_000u128.into(),
                1,
                FLOAT_PRECISION
            ),
            35_565_705_518_096_748_172_348_871_081_083_394_937u128
        );
        assert_eq!(
            approximate_multifactorial_digits(u128::MAX.into(), 1, FLOAT_PRECISION),
            Integer::from_str("12963922773915897352139996524992575205342").unwrap()
        );
        assert_eq!(
            approximate_multifactorial_digits(
                Integer::from_str(
                    "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
                )
                .unwrap(),
                1
            , FLOAT_PRECISION),
            Integer::from_str("197565705518096748172348871081083394917705602994196333433885546216834135350791129225270775050661568251681293893255233696266358320712841036093430778935337187734147872913431329670406629130341173311668936").unwrap()
        );
        assert_eq!(
            approximate_multifactorial_digits(100_001.into(), 2, FLOAT_PRECISION),
            228_291u128
        );
        assert_eq!(
            approximate_multifactorial_digits(7_834_436_739u128.into(), 2, FLOAT_PRECISION),
            37_055_762_699u128
        );
        assert_eq!(
            approximate_multifactorial_digits(738_247_937_346_920u128.into(), 2, FLOAT_PRECISION),
            5_327_901_315_957_321u128
        );
        assert_eq!(
            approximate_multifactorial_digits(
                827_829_849_020_729_846u128.into(),
                2,
                FLOAT_PRECISION
            ),
            7_236_742_262_513_376_731u128
        );
    }

    #[test]
    fn test_approximate_termial_digits() {
        assert_eq!(
            approximate_termial_digits(100_001.into(), 1, FLOAT_PRECISION),
            9
        );
        assert_eq!(
            approximate_termial_digits(7_834_436_739u128.into(), 1, FLOAT_PRECISION),
            19
        );
        assert_eq!(
            approximate_termial_digits(738_247_937_346_920u128.into(), 1, FLOAT_PRECISION),
            29
        );
        assert_eq!(
            approximate_termial_digits(827_829_849_020_729_846u128.into(), 1, FLOAT_PRECISION),
            35
        );
        assert_eq!(
            approximate_termial_digits(1_000_000_000_000_000_000u128.into(), 1, FLOAT_PRECISION),
            35
        );
        assert_eq!(
            approximate_termial_digits(
                1_000_000_000_000_000_000_000_000_000_000_000_000u128.into(),
                1,
                FLOAT_PRECISION
            ),
            71
        );
        assert_eq!(
            approximate_termial_digits(u128::MAX.into(), 1, FLOAT_PRECISION),
            76
        );
        assert_eq!(
            approximate_termial_digits(
                Integer::from_str(
                    "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
                )
                .unwrap(),1,
             FLOAT_PRECISION),
            395
        );
        assert_eq!(
            approximate_termial_digits(
                Integer::from_str(&format!("1{}", "0".repeat(1000000))).unwrap(),
                1,
                FLOAT_PRECISION
            ),
            1999999
        );
        assert_eq!(
            approximate_termial_digits(
                1_000_000_000_000_000_000_000_000_000_000_000_000u128.into(),
                2,
                FLOAT_PRECISION
            ),
            71
        );
        assert_eq!(
            approximate_termial_digits(
                1_000_000_000_000_000_000_000_000_000_000_000_000u128.into(),
                10,
                FLOAT_PRECISION
            ),
            70
        );
        assert_eq!(
            approximate_termial_digits(
                1_000_000_000_000_000_000_000_000_000_000_000_000u128.into(),
                10000,
                FLOAT_PRECISION
            ),
            67
        );
    }

    #[test]
    fn test_negative_multifacorial_factor() {
        // rem == 0
        assert_eq!(negative_multifacorial_factor(6.into(), 3), None);
        // rem < k
        assert_eq!(
            negative_multifacorial_factor(Integer::from(-1), 3),
            Some(Integer::ONE.clone())
        );
        // rem == k
        assert_eq!(negative_multifacorial_factor(5.into(), -5), None);
        // rem > k
        assert_eq!(
            negative_multifacorial_factor(1.into(), -3),
            Some(Integer::NEG_ONE.clone())
        );
    }

    #[test]
    fn test_adjust_approximate() {
        let input = (Float::with_val(FLOAT_PRECISION, 100.0), Integer::from(2));
        let (x, e) = adjust_approximate(input);
        assert_eq!(x, 1.0);
        assert_eq!(e, 4);
    }

    #[test]
    #[should_panic]
    fn test_approximate_factorial_with_n_is_non_positive() {
        let _ = approximate_factorial(0.into(), FLOAT_PRECISION);
    }

    #[test]
    #[should_panic]
    fn test_approximate_multifactorial_with_n_is_non_positive() {
        let _ = approximate_multifactorial(0.into(), 1, FLOAT_PRECISION);
    }

    #[test]
    #[should_panic]
    fn test_approximate_multifactorial_with_k_is_non_positive() {
        let _ = approximate_multifactorial(1.into(), 0, FLOAT_PRECISION);
    }

    #[test]
    #[should_panic]
    fn test_approximate_multifactorial_digits_with_n_is_non_positive() {
        let _ = approximate_multifactorial_digits(0.into(), 1, FLOAT_PRECISION);
    }

    #[test]
    #[should_panic]
    fn test_approximate_multifactorial_digits_with_k_is_non_positive() {
        let _ = approximate_multifactorial_digits(1.into(), 0, FLOAT_PRECISION);
    }
}