6
\$\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\$
  • \$\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 '15 at 13:51
  • 1
    \$\begingroup\$ Thanks. However, I believe in my case I need it to be exact. :( \$\endgroup\$ – Jared Mackey Oct 8 '15 at 13:52
  • 1
    \$\begingroup\$ I'll try to write an answer today, I got something for you! :) \$\endgroup\$ – IEatBagels Oct 8 '15 at 14:18
  • \$\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 '15 at 17:27
  • \$\begingroup\$ Yeah, factorials up to about 2000! are really quick. Then they start to slow down. \$\endgroup\$ – Jared Mackey Oct 8 '15 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.