Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for an old version of Boost. Click here to view this page for the latest version.
PrevUpHomeNext

Extended Euclidean Algorithm

Introduction
Synopsis
Usage
References

The extended Euclidean algorithm solves the integer relation mx + ny = gcd(m, n) for x and y.

#include <boost/integer/extended_euclidean.hpp>

namespace boost { namespace integer {

template<class Z>
struct euclidean_result_t {
  Z gcd;
  Z x;
  Z y;
};


template<class Z>
euclidean_result_t<Z> extended_euclidean(Z m, Z n);

}}
int m = 12;
int n = 15;
auto res = extended_euclidean(m, n);

int gcd = res.gcd;
int x = res.x;
int y = res.y;
// mx + ny = gcd(m,n) should now hold

Wagstaff, Samuel S., The Joy of Factoring, Vol. 68. American Mathematical Soc., 2013.


PrevUpHomeNext