Writing gcd w/o tail recursion in Rust

(The answer is not "use the builtin gcd". I'm trying to understand writing TCO functions in Rust.)

I'm writing GCD in Rust. I have this so far:

struct Ch01 {}

impl Ch01 {
    pub fn gcd(m: i64, n: i64) -> i64 {
        struct Args {
            m: i64,
            n: i64,
        };
        let mut args = Args { m: m, n: n };
        loop {
            if args.m == 0 {
                return args.n;
            } else {
                args = Args {
                    m: args.n % args.m,
                    n: args.m,
                }
            }
        }
    }
}

#[test]
fn test_00() {
    let m = 3822;
    let n = 28;
    println!("gcd({}, {}) = {}", m, n, Ch01::gcd(m, n));
}

I find this to be rather verbose. I don't like the "struct Args". However, without the "struct Args", I would need a temporary variable (since we can't simultaneously update m & n).

Advice on how to better write GCD / tail recursive functions in Rust?

Here is an impl using a tmp variable instead of Struct Args

    pub fn gcd(m: i64, n: i64) -> i64 {
        let mut m = m;
        let mut n = n;
        loop {
            if m == 0 {
                return n;
            } else {
                let old_m = m;
                m = n % m;
                n = old_m;
            }
        }
    }

This still seems verbose compared to a 1 line tail recursive version.

With TCO, we would be able to write:

    pub fn gcd(m: i64, n: i64) -> i64 {
        match m {
           0 => return n;
           _ => return Self::gcd(n % m, m);
        }
    }

which would reduce to 1 line if we also had ternary operators.

You can make m and n mutable, it will eliminate 2 variables, also your loop can be expressed as a while loop.

pub fn gcd(mut m: i64, mut n: i64) -> i64 {
    while m != 0 {
        let old_m = m;
        m = n % m;
        n = old_m;
    }
    n
}

After doing this in the playground I googled "greatest common divisor implementation" on google and the first link was to rosettacode, there are 3 implementations in Rust without crates (link).
The only difference is the use of abs, I didn't think about negative gcd.

1 Like

Thanks, I like this impl a lot.

I did not know func arguments would be tagged mutable.

It looks like the only "inefficiency" of a TCO vs a Rust impl is the necessity of temporary variables / lack of multiple updates at once. Is there anyway around this, or is this a fundamental limitation?

When this postponed RFC gets added to the language you'll be able to do:

(m, n) = (n % m, m)
1 Like

In this specific case (though I would not recommend doing it), you can mem::swap m and n to avoid the temp variable:

mem::swap(&mut m, &mut n);
m %= n;
// n = old m; m = old n (m) % old m (n)

This is opaquely clever, like the "swap two variables without a temporary variable" bit fiddling tricks. Don't write this, the optimizer can trivially peephole optimize this kind of thing. These kinds of microoptimizatioms are only of academic interest for regular (read: not developing optimization passes) developers at this point.

1 Like

Actually, mem::swap() is implemented using temp variable. In fact, it uses ptr::{read, write} to avoid lifetime problem. For example if you want to swap two variables of File a and b, after let tmp = a; the variable a becomes inaccessible so compiler throws error at a = b;.

It's not the "temp var in memory" that I'm trying to eliminate (I bet in TCO there might even be old/new pairs for EACH variable).

It's the "temp var in source code" I'm trying to avoid.

The XY problem is: I'm trying to do more "functional-ish" programming in Rust. Functional programs often use TCO reducing a problem to a smaller sub problem. I'm trying to figure out the best way to rewrite this in Rust.