Description Usage Arguments Details Value Author(s) References Examples
Implements the extended Euclidean algorithm which computes the greatest common divisor and solves Bezout's identity.
1 | extended.gcd(a, b)
|
a |
A vector of integers |
b |
A vector of integers. |
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.
a data frame containing 5 columns; a
, t
,
b
, s
, and gcd
.
Number of rows in output equals length of input a
.
Trent McDonald
Code is based on the following Wikipedia pseudo-code: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
1 2 3 4 5 | 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)
|
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.