NTTL Function - ExtendedGCD

Description

Compute the extended GCD (EGCD).  That is, given a and b, find d, u, and v such that

d = a * u + b * v

Header(s)

Header	Description
#include <gcd.h>	The default header.  This header will, in turn, includes one of the two headers below.  As shipped, this would be <gcdEuclid.h>, but this may be changed when the package is installed.
#include <gcdEuclid.h>	This header implements the usual Euclidean algorithm for EGCD [1].
#include <gcdRSB.h>	Implements EGCD using the Right Shift Binary algorithm.   While this can be much faster than the Euclidean algorithm, it has a worst case runtime that is much worse [2].

Signature(s)

template< class T >
T EGCD( const T& a, const T& b, T *u, T *v )

 

template< class T >
T EGCDRSBbad( T u, T v, T* u1, T* u2 )

 

template< class T >
T EGCDEuclid( const T& a, const T& b, T *u, T *v )

Parameters

Name	Type	Description
a, b	T	The numbers for which the EGCD is calculated.
u, v	T *	Pointers to the variables to hold the values of u and v, as described above.

Returns

( T )  The GCD of a and b.

Example

#include <nttl/gcd.h> ... long u, v; long d = EGCD( 125, 62735, &u, &v );

See Also

The GCD function shares the same headers as the EGCD function.

 

Algorithm Selection describes the method that nttl uses to implement alternate algorithms for the same function.  This is the architecture used to implement the three GCD headers.

Notes

[1]	The algorithm implemented here comes directly from [COHEN], p 16.  See also [Knuth2], pp 323-327.
[2]	I need a reference for the extended binary algorithm.