# Recursive factorial calculations in Rust

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.

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