Finding the GCD without looping - R

Question

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 1

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.

Answer 2

You can solve it recursively.

euclids <- function(x,y){
        theMax = max(x,y)
        theMin = min(x,y)

        if (theMax == theMin) return (theMax)
        else return (euclids(theMin, theMax-theMin))
}

Answer 3

Reducing GCD for two integers enables you to compute GCD for any sequence of integers (sorted or not):

gcd2 <- function(a, b) {
  if (b == 0) a else Recall(b, a %% b)
}

gcd <- function(...) Reduce(gcd2, c(...))

Answer 4

It's easy to do with a couple modulo operations. Sadly, I left my personal gcd code on a different machine (in a galaxy far away) - but you can find the source in either the numbers or pracma packages.

BTW, here's a good way to find existing code: library(sos); ???gcd