gcd {cheapr} | R Documentation |
Greatest common divisor and smallest common multiple
Description
Fast greatest common divisor and smallest common multiple using the Euclidean algorithm.
gcd()
returns the greatest common divisor.
scm()
returns the smallest common multiple.
gcd2()
is a vectorised binary version of gcd
.
scm2()
is a vectorised binary version of scm
.
Usage
gcd(
x,
tol = sqrt(.Machine$double.eps),
na_rm = TRUE,
round = TRUE,
break_early = TRUE
)
scm(x, tol = sqrt(.Machine$double.eps), na_rm = TRUE)
gcd2(x, y, tol = sqrt(.Machine$double.eps), na_rm = TRUE)
scm2(x, y, tol = sqrt(.Machine$double.eps), na_rm = TRUE)
Arguments
x |
A numeric vector. |
tol |
Tolerance. This must be a single positive number strictly less than 1. |
na_rm |
If |
round |
If |
break_early |
This is experimental and
applies only to floating-point numbers.
When |
y |
A numeric vector. |
Details
Method
GCD (Greatest Common Divisor)
The GCD is calculated using a binary function that takes input
GCD(gcd, x[i + 1])
where the output of this function is passed as input
back into the same function iteratively along the length of x
.
The first gcd value is x[1]
.
Zeroes are handled in the following way:
GCD(0, 0) = 0
GCD(a, 0) = a
This has the nice property that zeroes are essentially ignored.
SCM (Smallest Common Multiple)
This is calculated using the GCD and the formula is:
SCM(x, y) = (abs(x) / GCD(x, y) ) * abs(y)
If you want to calculate the gcd & lcm for 2 values
or across 2 vectors of values, use gcd2
and scm2
.
A note on performance
A very common solution to finding the GCD of a vector of values is to use
Reduce()
along with a binary function like gcd2()
.
e.g. Reduce(gcd2, seq(5, 20, 5))
.
This is exactly identical to gcd(seq(5, 20, 5))
, with gcd()
being much
faster and overall cheaper as it is written in C++ and heavily optimised.
Therefore it is recommended to always use gcd()
.
For example we can compare the two approaches below,
x <- seq(5L, length = 10^6, by = 5L)
bench::mark(Reduce(gcd2, x), gcd(x))
This example code shows gcd()
being ~200x faster on my machine than
the Reduce
+ gcd2
approach, even though gcd2
itself is written in C++
and has little overhead.
Value
A number representing the GCD or SCM.
Examples
library(cheapr)
library(bench)
# Binary versions
gcd2(15, 25)
gcd2(15, seq(5, 25, 5))
scm2(15, seq(5, 25, 5))
scm2(15, 25)
# GCD across a vector
gcd(c(0, 5, 25))
mark(gcd(c(0, 5, 25)))
x <- rnorm(10^5)
gcd(x)
gcd(x, round = FALSE)
mark(gcd(x))