Finding the GCD without looping - R

Reanimation picture Reanimation · Feb 1, 2014 · Viewed 11.4k times · Source

So I'm trying to learn R and using a number of resources including a book called "Discovering Statistics using R" and a bunch of other cool eBooks.

I understand a great method in programming is the Euclid's Algorithm.

Implementing it in a loop can be achieved like this:

 gcd(x,y) //assuming x is the largest value
 //do
 r = x%y;
 x = y;
 y = r;
 //while r != 0;
 return x;

After several searches on Google, SO and Youtube refreshing my memory of gcd algorithms, I wasn't able to find one that doesn't use a loop. Even recursive methods seem to use loops.

How can this be achieved in R without the use of loops or if statements?

Thanks in advance.

Answer

Matthew Lundberg picture Matthew Lundberg · Feb 1, 2014

Using the statement "without loops or the if statement" literally, here is a recursive version that uses ifelse:

gcd <- function(x,y) {
  r <- x%%y;
  return(ifelse(r, gcd(y, r), y))
}

One might not expect it, but this is actually vectorized:

gcd(c(1000, 10), c(15, 10))
[1]  5 10

A solution using if would not handle vectors of length greater than 1.