Extended Euclidean algorithm (C Plus Plus)

From LiteratePrograms

Other implementations: C++ | Python

This article describes a C++ implementation of Extended Euclidean algorithm.

Given a,b, Find x,y,g that solve the equation:

ax + by = g = gcd(a,b)

The algorithm is better described in the Python version.

Source

<<eea>>=
void eea (int a, int b,
        int& gcd, int& x, int& y) {
        x=0, y=1; 
        int u=1, v=0, m, n, q, r;
        gcd = b;
        while (a!=0) {
                q=gcd/a; r=gcd%a;
                m=x-u*q; n=y-v*q;
                gcd=a; a=r; x=u; y=v; u=m; v=n;
        }
}

The test driver is also given.

<<eea.cpp>>=
#include <iostream>
using namespace std;
eea
int main() {
  int gcd, x, y; 
  eea(352, 168, gcd, x, y);
  cout << x << " " << y << " " << gcd << endl;
  eea(168, 352, gcd, x, y);
  cout << x << " " << y << " " << gcd << endl;
  eea(3458, 4864, gcd, x, y);
  cout << x << " " << y << " " << gcd << endl;
  return 0;
}

Execution result

$ g++ eea.cpp; ./a.out 
-10 21 8
21 -10 8
-45 32 38

• The first test case shows that -10 *352 + 21 * 168 = 8 and 8 is gcd(352, 168).
• The second result means that the order of input numbers has no significant meaning.
• The last result shows that -45 * 3458 + 32 * 4864 = 38 and 38 is gcd(3458, 4864).

Download code