This code works for small numbers but factorials get big quick and I tried using num::BigInt in the playground but could not get a working program after trying the suggestions from the compiler any suggestions on how to use BigInt or multiply natively past u128 would be appreciated I am trying to determing lattice paths for a 20x20 grid.
fn factorial(num: u128) -> u128 {
let mut result = num;
if num == 0 {
result = 1;
} else {
for i in 1..num {
result *=i;
}
}
result
}
fn lattice_paths(x: u128, y: u128) -> u128 {
let n = x + y;
let k = y;
let top_part = factorial(n);
let bottom_part = factorial(k) * factorial(n-k);
let result = top_part / bottom_part ;
result
}
fn main() {
let x: u128 = 2;
let y: u128 = 2;
println!("Lattice paths for a {}, {} grid = \n{:?}", x, y, lattice_paths(x, y));
}
I changed the category to Help and added ``` on a separate line above and below your code to format it. Please do this in the future so we can read the code more easily.
Please post the code that you tried with BigInt and the full compiler error. Otherwise we won't be able to help you understand the error. You said you used a playground, so please share the playground.
Try computing the binomial recursion with the usual recursion and dynamic programming instead (i.e., fill in Pascal's triangle). If you want to use multiplication you need to use a different formula, since 40! is 160 bits. You could use the fact that n choose k is (n/k)(n-1 choose k-1): compute the binomial coefficient, multiply by n, then divide by k. This will not overflow in this particular case.
If you just need the binomial coefficient, use rug.
use num_bigint::BigUint;
// (2^8)! > 10^504, thus unnecessary
fn factorial(n: u8) -> BigUint {
if n == 0 {
return BigUint::from(1u8);
}
let mut result = BigUint::from(n);
for i in 2..n {
result *= BigUint::from(i);
}
result
}
fn lattice_paths(x: u8, y: u8) -> BigUint {
let n = x + y;
let k = y;
let top_part = factorial(n);
let bottom_part = factorial(k) * factorial(n - k);
top_part / bottom_part
}
fn main() {
let x = 20;
let y = 20;
// prints 137846528820
println!(
"Lattice paths for a {x}, {y} grid = \n{:?}",
lattice_paths(x, y)
);
}
Integer literals like 0 or 1 cannot be of type BigUint, you must explicitly convert. Additionally, since a generic 1 literal cannot have its type inferred, you must provide a type. (I used u8, it's just the shortest unsigned integer to name at only two characters)
A range of BigUints is not an iterator, so the range in my code is actually a range of u8s.
The lattice_paths function just needed to have its signature changed, none of its body is even different.
Alternate, and IMO better way to write the factorial function
fn factorial(n: u8) -> BigUint {
// n == 0 does return 1
(2..=n)
.map(BigUint::from)
.product()
}