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.

Spinnaker

No, but I am working through old examples. – Spinnaker

I ask if it's homework not to be snide, but in order to offer hints if it is, and outright answer the question otherwise. – Ducharme

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.

Ducharme

Oh, nice :D So I guess it can be done. I've been curious about this all day. Thanks for taking the time to post. I'm going to have a play with it now. Thanks. – Spinnaker

This is pretty ingenius – Bravura

A minor tweak: the assignment is unnecessary, and it is safer not to recurse on the explicit name of the function. Thus: gcd <- function(x, y) ifelse(y, Recall(y, x %% y), x). – Muro

And Recall() works in anonymous functions too, so for a multi argument gcd we could do gcd <- function(...) Reduce(function(x,y) ifelse(y, Recall(y, x %% y), x), list(...)) – Fisher

Recall is of course preferred for production code. This is academic. – Ducharme

Ingenious and beautiful. Has this function been implemented in some package since 2014? – Flavone

Answer 2

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(...))

Muro

Answer 3

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))
}

Logogriph

This sounds like a repeat of this existing answer. Read this how-to-answer for providing a quality answer. – Graphomotor

Oops - just getting started here. Thanks! – Logogriph

This also uses recursion, but without the clever use of ifelse shown by @Matthew Lundberg. Easier to read, but doesn't have the Wow effect of Matthew's answer. – Enrobe

@Logogriph This answer provides another aspect or way of doing things, therefore I disagree with the comment by thewaywewere. We welcome diverse answers, otherwise StackExchange would not support them, nor would it support voting. – Franfranc

Answer 4

My package timeplyr has a gcd function and the development version now has gcd2 which is a vectorized binary version.

remotes::install_github("NicChr/timeplyr")
library(timeplyr)
x <- seq(0, 25, 5)
y <- 5

gcd2(x, y)
#> [1] 5 5 5 5 5 5

# Works on decimals too
gcd2(2.5, 10.5)
#> [1] 0.5

library(bench)
z <- seq(0L, 10000000L, by = 10L)
gcd(z)
#> [1] 10
mark(gcd(z))
#> # A tibble: 1 × 6
#>   expression      min   median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl>
#> 1 gcd(z)       3.61ms   3.61ms      276.        0B        0

^{Created on 2023-12-18 with reprex v2.0.2}

Lint

Answer 5

If you just want to avoid loops, the best option might be using recursion, as did in @Matthew Lundberg solution.

---

Here is another loop-free implementation, which seems a bit weird and clumsy than usual options (due to the use of seq_len), and it is using some vectorizing feature of base R vectors

gcd <- function(...) {
    max(which(Reduce(`+`, lapply(list(...), `%%`, seq_len(min(...)))) == 0))
}

and for example

> gcd(75, 575, 25, 600)
[1] 25

> gcd(1000, 15)
[1] 5

> gcd(10, 10)
[1] 10

Acne