5
\$\begingroup\$

I am trying to calculate very large factorials. I am looking to speed it up as 10000! takes approximately a minute and a half.

extern crate num;
use num::bigint::BigInt;
use num::bigint::ToBigInt;

fn tree_fact(n: u64) -> BigInt {
    if n < 2 {
        return 1.to_bigint().unwrap();
    }
    return factorial(1, n)
}


fn factorial(low: u64, high: u64) -> BigInt {
    if low +1 < high {
        let mid = (low + high) / 2;
        return factorial(low, mid) * factorial(mid + 1, high)
    }
    if low == high {
        return low.to_bigint().unwrap();
    }
    return low.to_bigint().unwrap() * high.to_bigint().unwrap();

}


fn main() {
    let fac_value = tree_fact(10000);
    println!("{}", fac_value);
}

I am also concerned with following best practices as I am new to programming in Rust so feel free to point out where I am bending any rules.

\$\endgroup\$
9
  • \$\begingroup\$ I don't know your context, but sometimes an approximation of a very large factorial can be enough and can be calculated much much faster. In this case there is the Stirling's approximation formula you might want to look at :) \$\endgroup\$
    – IEatBagels
    Oct 8, 2015 at 13:51
  • 1
    \$\begingroup\$ Thanks. However, I believe in my case I need it to be exact. :( \$\endgroup\$ Oct 8, 2015 at 13:52
  • 1
    \$\begingroup\$ I'll try to write an answer today, I got something for you! :) \$\endgroup\$
    – IEatBagels
    Oct 8, 2015 at 14:18
  • 1
    \$\begingroup\$ I figured that your algorithm is more efficient than the one I thought about. But, I find it hard to believe 10000! factorial is so long to compute, on my computer the basic factorial method takes some milliseconds \$\endgroup\$
    – IEatBagels
    Oct 8, 2015 at 17:27
  • \$\begingroup\$ Yeah, factorials up to about 2000! are really quick. Then they start to slow down. \$\endgroup\$ Oct 8, 2015 at 17:39

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.