---
title: 'Euclid GCD'
url: 'https://blog.recursiveprocess.com/2014/09/25/euclid-gcd'
markdown: 'https://blog.recursiveprocess.com/2014/09/25/euclid-gcd.md'
date: '2014-09-25'
description: 'Darker pixel = longer Euclidean algorithm to find GCD(x,y). Here x & y range from 1 to 500. So many questions… pic.twitter.com/k8N6jiGxSd — Matt Enlow (@CmonMattTHINK) September 24, 2014 I saw this toot by Matt yesterday morning and I loved the visual of the color based on the nu…'
taxonomy:
  category:
    - blog
---

# Euclid GCD

### [Euclid GCD](https://blog.recursiveprocess.com/2014/09/25/euclid-gcd)

   September 25, 2014, 12:00 am  

> Darker pixel = longer Euclidean algorithm to find GCD(x,y). Here x & y range from 1 to 500. So many questions… [pic.twitter.com/k8N6jiGxSd](http://t.co/k8N6jiGxSd)
> 
> — Matt Enlow (@CmonMattTHINK) [September 24, 2014](https://twitter.com/CmonMattTHINK/status/514747295527886848?ref_src=twsrc%5Etfw)

I saw this toot by Matt yesterday morning and I loved the visual of the color based on the number of steps of Euclid’s GCD algorithm. The algorithm is pretty straightforward and it’s a nice example for either using recursion or using a loop. The coloring is fun to mess with too. The coding went quickly for me because I already had the code for breaking a 1D pixel array (why processing??) into x and y coordinates.
There’s two variations:
Here’s the [link for the GCD steps version](http://www.openprocessing.org/sketch/162986).
[![2014-09-26_07h38_20](https://blog.recursiveprocess.com/wp-content/uploads/2014/09/2014-09-26_07h38_20.png)](https://blog.recursiveprocess.com/wp-content/uploads/2014/09/2014-09-26_07h38_20.png)
And here’s the [link for the GCD version](http://www.openprocessing.org/sketch/162989) where the closer the GCD is to the minimum of x and y, the more white the pixel is.
[![2014-09-26_07h20_35](https://blog.recursiveprocess.com/wp-content/uploads/2014/09/2014-09-26_07h20_35.png)](https://blog.recursiveprocess.com/wp-content/uploads/2014/09/2014-09-26_07h20_35.png)
Here’s the recursive algorithm:

```
int euclidGCD(int x, int y)
{
  if (y == 0)
  {
    return x;
  }
  else if (x >= y && y > 0)
  {
    return euclidGCD(y,(x%y));
  }
  else 
  {
    return euclidGCD(y,x);
  }  
}
```

Here’s the loop algorithm to count the number of steps:

```
int euclidGCDsteps(int x, int y)
{
  int t;
  int steps = 0;
  if (x >= y)
  {
    while (y != 0)
    {
      t = y;
      y = x % y;
      x += t;
      steps++;
    }
  }
  else
  {
    return euclidGCDsteps(y,x);
  }
  return steps; 
}
```

 [ Next Post](https://blog.recursiveprocess.com/2014/09/29/kaprekars-constant) [Previous Post ](https://blog.recursiveprocess.com/2014/07/29/my-favorite-for-the-students)

#### SimpleSearch

Bootstrap Theme for [Grav](http://getgrav.org)

---

## Navigation

- Parent: [A Recursive Process](https://blog.recursiveprocess.com/index.md)
- Previous: [Kaprekar’s constant](https://blog.recursiveprocess.com/2014/09/29/kaprekars-constant.md)
- Next: [My Favorite for the Students](https://blog.recursiveprocess.com/2014/07/29/my-favorite-for-the-students.md)