Gcd for BigUInt

[bruce-wayne]

I'm trying to write a gcd function using BigUInt from create num-bigint.

fn gcd<'a>(mut a: &'a BigUint, mut b: &'a BigUint) -> &'a BigUint {
    while *b != Zero::zero() {
        let t = b;
        b = &a.modpow(&One::one(), b);
        a = t;
    }
    return a;
}

but I get a compilation error:

error[E0716]: temporary value dropped while borrowed
  --> src/lib.rs:63:18
   |
60 |     fn gcd<'a>(mut a: &'a BigUint, mut b: &'a BigUint) -> &'a BigUint {
   |            -- lifetime `'a` defined here
...
63 |             b = &a.modpow(&One::one(), b);
   |             -----^^^^^^^^^^^^^^^^^^^^^^^^- temporary value is freed at the end of this statement
   |             |    |
   |             |    creates a temporary which is freed while still in use
   |             assignment requires that borrow lasts for `'a`

How to fix this? I don't want to clone the BigUInt repeatedly since those are supposed to be big.

Note: Zero::zero() and One::one() are from num-traits create.

[quinedot]

Use this:

num::BigInt - Rust

If you want to do it yourself and don't want to modify the inputs, you're still going to have to return a new owned value; the current signature only allows returning one of the inputs (or something 'static).

[bruce-wayne]

num-integer crate has a gcd for the BigUint type, so, I'll use that instead. I was hoping for a way out of the problem without copying.

[Michael-F-Bryan]

@bruce-wayne

fn gcd<'a>(mut a: &'a BigUint, mut b: &'a BigUint) -> &'a BigUint {

This function signature looks wrong.

It says that you take a reference to two BigUints and return a reference to the greatest common denominator. References need to borrow from existing values, and because the only existing values we have access to are a and b, this function signature will only ever work if one number is the greatest common divisor of the other... which is probably not what you want.

Your solutions are either a) return a new BigUint, or b) mutate one of the existing BigUints in-place. It doesn't look like BigUint has methods/operator implementations that mutate in-place^[1], so you will need to return a new, owned BigUint.

---

1. It implements things like AddAssign (a += b) and RemAssign (a %= b), but their implementations reduce to something like *self = &*self % other so you end up making a allocations instead of reusing the existing one. ↩︎