11. Extended Euclidean algorithm | R Documentation |
Computation of the Extended Euclidean algorithm for vli (Very Large Integers) objects. Given two positive integers, x
and y
, the Extended Euclidean algorithm looks for two integers a
and b
(called Bezout's coefficients) such that (a * x) + (b * y) = 1
. To do this, the algorithm needs to compute the greatest common divisor of x
and y
, so it is also returned by the function.
exteuclid(x, y)
## Default S3 method:
exteuclid(x, y)
## S3 method for class 'numeric'
exteuclid(x, y)
## S3 method for class 'vli'
exteuclid(x, y)
x |
object of class vli or 32 bits integer |
y |
object of class vli or 32 bits integer |
The returned object is a list of 3 elements. To access the numbers, it is necessary to use the list operator [[i]]
, where "i
" has to be 1 for the greatest common divisor, 2 for the first Bezout coefficient and 3 for the second Bezout coefficient (see the example).
list of 3 objects of class vli: the first is the greatest common divisor of x
and y
, and the other two are the Bezout's coefficients
Javier Leiva Cuadrado
x <- as.vli("232636113097")
y <- as.vli("52442092785616")
result <- exteuclid(x, y)
( result[[2]] * x ) + ( result[[3]] * y )
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.