Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
extended_euclid_algorithm.cpp File Reference

GCD using extended Euclid's algorithm More...

#include <algorithm>
#include <iostream>
Include dependency graph for extended_euclid_algorithm.cpp:

Functions

template<typename T , typename T2 >
void update_step (T *r, T *r0, const T2 quotient)
 
template<typename T1 , typename T2 >
void extendedEuclid_1 (T1 A, T1 B, T1 *GCD, T2 *x, T2 *y)
 
template<typename T , typename T2 >
void extendedEuclid (T A, T B, T *GCD, T2 *x, T2 *y)
 
int main ()
 Main function.
 

Detailed Description

GCD using extended Euclid's algorithm

Finding coefficients of a and b ie x and y in Bézout's identity

\[\text{gcd}(a, b) = a \times x + b \times y \]

This is also used in finding Modular multiplicative inverse of a number. (A * B)M == 1 Here B is the MMI of A for given M, so extendedEuclid (A, M) gives B.

Function Documentation

◆ extendedEuclid()

template<typename T , typename T2 >
void extendedEuclid ( A,
B,
T *  GCD,
T2 *  x,
T2 *  y 
)

Implementation using recursive algorithm

Parameters
[in]Aunsigned
[in]Bunsigned
[out]GCDunsigned
[in,out]xsigned
[in,out]ysigned
70  {
71  if (B > A)
72  std::swap(A, B); // Ensure that A >= B
73 
74  if (B == 0) {
75  *GCD = A;
76  *x = 1;
77  *y = 0;
78  } else {
79  extendedEuclid(B, A % B, GCD, x, y);
80  T2 temp = *x;
81  *x = *y;
82  *y = temp - (A / B) * (*y);
83  }
84 }
Here is the call graph for this function:

◆ extendedEuclid_1()

template<typename T1 , typename T2 >
void extendedEuclid_1 ( T1  A,
T1  B,
T1 *  GCD,
T2 *  x,
T2 *  y 
)

Implementation using iterative algorithm from Wikipedia

Parameters
[in]Aunsigned
[in]Bunsigned
[out]GCDunsigned
[out]xsigned
[out]ysigned
41  {
42  if (B > A)
43  std::swap(A, B); // Ensure that A >= B
44 
45  T2 s = 0, s0 = 1;
46  T2 t = 1, t0 = 0;
47  T1 r = B, r0 = A;
48 
49  while (r != 0) {
50  T1 quotient = r0 / r;
51  update_step(&r, &r0, quotient);
52  update_step(&s, &s0, quotient);
53  update_step(&t, &t0, quotient);
54  }
55  *GCD = r0;
56  *x = s0;
57  *y = t0;
58 }
Here is the call graph for this function:

◆ update_step()

template<typename T , typename T2 >
void update_step ( T *  r,
T *  r0,
const T2  quotient 
)
inline

function to update the coefficients per iteration

\[r_0,\,r = r,\, r_0 - \text{quotient}\times r\]

Parameters
[in,out]rsigned or unsigned
[in,out]r0signed or unsigned
[in]quotientunsigned
24  {
25  T temp = *r;
26  *r = *r0 - (quotient * temp);
27  *r0 = temp;
28 }
update_step
void update_step(T *r, T *r0, const T2 quotient)
Definition: extended_euclid_algorithm.cpp:24
std::swap
T swap(T... args)
extendedEuclid
void extendedEuclid(T A, T B, T *GCD, T2 *x, T2 *y)
Definition: extended_euclid_algorithm.cpp:70