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.

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.