NTTL Function - GCD

Description: Calculate the Greatest Common Divisor of two numbers

Header(s)

Header	Description
#include <gcd.h>	The default header. This header will, in turn, include 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 GCD [1].
#include <gcdRSB.h>	Implements GCD 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: template< class T >
T GCD( const T& a, const T& b ); template< class T >
T GCDEuclid( const T& a, const T& b ); template< class T >
T GCDRSB( T u, T v )

Parameters

Name	Type	Description
a, b	T	The numbers. Note that they must be of the same type [3].

Returns: ( T ) The GCD of a and b.

Example

#include <nttl/gcd.h>
...
long d = GCD( 1235, 2325 );

See Also: 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]

See [Knuth2], pp 316-320.

[2]

See [Sorenson1]. This is also mentioned in [Knuth2], pp.321-323, and other places, but the paper by Sorenson is the easiest to follow.

[3]

In general, the requirement that both arguments be of the same type is not a problem. For example, lets assume that you are using the large number class ln, and want to do the following:

ln a;
long b;
...
ln d = GCD( a, b );

This will result in a compile-time error, since the types of a and b are not the same. There are two possible solutions here (and in general): cast b up to type ln:

ln d = GCD( a, ln( b ) );

or reduce a down to a long:

ln d = GCD( ( a % b ), b );

In practice, reducing a down to a long is probably the more efficient solution.

To Do: It would be desirable to have a and b of different types. This would have to be coded carefully, to avoid overflow.