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

And here’s the link for the GCD version where the closer the GCD is to the minimum of x and y, the more white the pixel is.

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