SDraw (version 2.1.13)

extended.gcd: Extended Greatest Common Denominator (GCD) algorithm.

Description

Implements the extended Euclidean algorithm which computes the greatest common divisor and solves Bezout's identity.

Usage

extended.gcd(a, b)

Arguments

a

A vector of integers

b

A vector of integers. length(a) must equal length(b).

Value

a data frame containing 5 columns; a, t, b, s, and gcd. Number of rows in output equals length of input a.

Details

This routine computes the element-wise gcd and coefficients s and t such that a*t + b*s = d. In other words, if x = extended.gcd(a,b), then x$a*x$t + x$b*x$s == x$gcd

The Wikipedia page, from which this algorithm was stolen, has the following statement, 'The quotients of a and b by their greatest common divisor, which are output, may have an incorrect sign. This is easy to correct at the end of the computation, but has not been done here for simplifying the code.' I have absolutely no idea what that means, but include it as a warning. For purposes of SDraw, elements of a and b are always positive, and I have never observed "incorrect signs". But, there may be some pathological cases where "incorrect signs" occur, and the user should "correct" for this. This routine does check that the output gcd is positive, and corrects this and the signs of s and t if so.

References

Code is based on the following Wikipedia pseudo-code: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Examples

# NOT RUN {
 x <- extended.gcd( c(16,27,27,46), c(9,16,9,240) )
 
 #  Check
 cbind(x$a*x$t + x$b*x$s, x$gcd)
 
# }