Euclid's Algorithm Function parameters

Question

I've written a program for class where I need to recursively evaluate the extended euclid's algorithm for a and b, returning G, the greatest common divisor, as well as s and t from as+bt=gcd(a,b). I'm fairly certain I have the function written correctly but I am having issues with values being passed to and from the function. I haven't coded in a while and have only written pseudocode recently so I'm a little rusty.

For example, I have written when b=0, return (a, 1, 0), but when I input b as 0 I get returned (0, 0, 0) and cannot figure out why this is happening. Any help or guidance would be greatly appreciated.

#include <iostream>
using namespace std;
int ExtGCD (int a, int b)
{
    int g, s, t, g1, s1, t1;
    if (b == 0) {
        return (a, 1, 0);
    }
    (g1, s1, t1) = ExtGCD(b, a%b);
    g = g1;
    s = s1;
    t = s1 - ((a/b)*t1);
    return (g, s, t);
}

int main(int argc, char* argv[])
{
    int a,b, g2, s2, t2, temp;
    cout << "Please input a: ";
    cin >> a;
    cout << "Please input b: ";
    cin >> b;
    if (b > a) {
        temp = a; a = b; b = temp;
    }
    (g2, s2, t2) = ExtGCD (a, b);
    cout << "G = "<< g2 << ", S = " << s2 << ", T = " << t2;
    return 0;
}

Answer 1

C++11 introduces tuples, which allow you to write your code like this, with minimal modifications:

#include <iostream>
#include <tuple>

using namespace std;
std::tuple<int, int, int> ExtGCD (int a, int b)
{
    int g, s, t, g1, s1, t1;
    if (b == 0) {
        return std::make_tuple(a, 1, 0);
    }
    std::tie(g1, s1, t1) = ExtGCD(b, a%b);
    g = g1;
    s = s1;
    t = s1 - ((a/b)*t1);
    return std::make_tuple(g, s, t);
}

int main(int argc, char* argv[])
{
    int a,b, g2, s2, t2, temp;
    cout << "Please input a: ";
    cin >> a;
    cout << "Please input b: ";
    cin >> b;
    if (b > a) {
        temp = a; a = b; b = temp;
    }
    std::tie(g2, s2, t2) = ExtGCD (a, b);
    cout << "G = "<< g2 << ", S = " << s2 << ", T = " << t2;
    return 0;
}

See http://en.cppreference.com/w/cpp/utility/tuple/tie and http://en.cppreference.com/w/cpp/utility/tuple.

On a related note, you can also replace

if (b > a) {
    temp = a; a = b; b = temp;
}

by

if (b > a)
    std::swap(a, b);

or even by

std::tie(b, a) = std::minmax({a, b});

The C++ standard library provides many algorithmic facilities that should be learned to enjoy C++ to its full potential.

Answer 2

return (g, s, t);

doesn't do what you think it does. It's not possible to return multiple values from a function like that. Look up the comma operator if you want an explanation of what that code does.

There's a few different ways you could handle this. Perhaps the simplest is to return your values via references passed to the function. Like this

#include <iostream>
using namespace std;

void ExtGCD (int a, int b, int& g, int& s, int& t)
{
    int g1, s1, t1;
    if (b == 0) {
        g = a;
        s = 1;
        t = 0;
        return;
    }
    ExtGCD(b, a%b, g1, s1, t1);
    g = g1;
    s = s1;
    t = s1 - ((a/b)*t1);
}

int main(int argc, char* argv[])
{
    int a,b, g2, s2, t2, temp;
    cout << "Please input a: ";
    cin >> a;
    cout << "Please input b: ";
    cin >> b;
    if (b > a) {
        temp = a; a = b; b = temp;
    }
    ExtGCD (a, b, g2, s2, t2);
    cout << "G = "<< g2 << ", S = " << s2 << ", T = " << t2;
    return 0;
}

In this code g, s and t are references, which means assignments to them change the values of the variables bound to the references when the function is called.