[FIXED] How to avoid cloning a big integer in rust

Issue

I used the num::BigUInt type to avoid integer overflows when calculating the factorial of a number.

However, I had to resort to using .clone() to pass rustc's borrow checker.

How can I refactor the factorial function to avoid cloning what could be large numbers many times?

use num::{BigUint, FromPrimitive, One};

fn main() {
    for n in -2..33 {
        let bign: Option<BigUint> = FromPrimitive::from_isize(n);
        match bign {
            Some(n) => println!("{}! = {}", n, factorial(n.clone())),
            None => println!("Number must be non-negative: {}", n),
        }
    }
}

fn factorial(number: BigUint) -> BigUint {
    if number < FromPrimitive::from_usize(2).unwrap() {
        number
    } else {
        number.clone() * factorial(number - BigUint::one())
    }
}

I tried to use a reference to BigUInt in the function definition but got some errors saying that BigUInt did not support references.

Solution

The first clone is easy to remove. You are trying to use n twice in the same expression, so don't use just one expression:

print!("{}! = ", n);
println!("{}", factorial(n));

is equivalent to println!("{}! = {}", n, factorial(n.clone())) but does not try to move n and use a reference to it at the same time.

The second clone can be removed by changing factorial not to be recursive:

fn factorial(mut number: BigUint) -> BigUint {
    let mut result = BigUint::one();
    let one = BigUint::one();

    while number > one {
        result *= &number;
        number -= &one;
    }

    result
}

This might seem unidiomatic however. There is a range function, that you could use with for, however, it uses clone internally, defeating the point.

Answered By - mcarton

Answer Checked By - David Marino (PHPFixing Volunteer)