Euclidean Algorithm Function Parameters

Question

I wrote a program for a class where I need to recursively evaluate the extended Euclidean algorithm for a and b, returning G, the largest common factor, as well as s and t from as + bt = gcd (a, b). I am pretty sure that I have a function that is written correctly, but I am having problems with the values ​​passed to and from the function. I haven't coded after a while and recently wrote pseudo code, so I'm a little rusty.

For example, I wrote when b = 0, return (a, 1, 0), but when I enter b as 0, I return (0, 0, 0) and cannot understand 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

 return (g, s, t); 

Don't do what you think. It is not possible to return multiple values ​​from such a function. See the comma operator if you want to explain what this code does.

Here are some ways you could handle it. Perhaps the easiest is to return your values ​​through the links 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 have references, which means that assigning them changes the values ​​of the variables associated with the links when the function is called.

Answer 2

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

 #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 .

In the corresponding note, you can also replace

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

by

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

or even

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

The C ++ Standard Library provides many algorithmic tools that must be learned for the full use of C ++.

Answer 3

You cannot return such tuples.

In C ++, a comma operator will throw stuff to the left. In your particular case, the "tuple" (a,b,c) actually just c . A more specific example:

 if (b == 0) { return (a, 1, 0); } 

actually matches

 if (b == 0) { return 0; } 

To return several things at once, you will have to use structures or classes.