# Programmatically Calculating GCD and LCM

I recently came across a really interesting technique for calculating GCD (greatest common divisor) and then found out you can use that to calculate LCM (least common multiple).

## Greatest Common Divisor

The greatest common divisor of two numbers is the largest number that divides evenly into those numbers.

For instance the GCD of 12 and 15 is 3, the GCD of 30 and 20 is 10, and the GCD of 7 and 11 is 1.

You could calculate this with brute force – starting with 1 and counting up to the smaller number, keeping track of the largest number that divides evenly into both numbers – but for larger numbers, this technique could take a long time.

Luckily Euclid came up a better way in 300 BC!

Euclid’s algorithm to find the GCD of numbers A and B:

1. If A and B are the same number, that number is the GCD
2. Otherwise, subtract the smaller number from the larger number
3. Goto 1

Pretty simple right? It’s not immediately intuitive why that works, but as an example let’s say that there’s a number that goes into A fives times, and goes into B three times. That same number must go into (A-B) two times.

Try it out on paper, think about it a bit, and check out the links at the end of this section (:

A refinement on that algorithm is to use remainder (modulus) instead of possibly having to do repeated subtraction to get the same result. For instance if you had the numbers 1015 and 2, you are going to have to subtract 2 from 1015 quite a few times before the 2 becomes the larger number.

Here’s the refined algorithm:

1. If A and B are the same number, that number is the GCD
2. Otherwise, set the larger number to be the remainder of the larger number divided by the smaller number
3. Goto 1

And here’s the C++ code:

```#include <stdio.h>
#include <algorithm>

unsigned int CalculateGCD (unsigned int smaller, unsigned int larger)
{
// make sure A <= B before starting
if (larger < smaller)
std::swap(smaller, larger);

// loop
while (1)
{
// if the remainder of larger / smaller is 0, they are the same
// so return smaller as the GCD
unsigned int remainder = larger % smaller;
if (remainder == 0)
return smaller;

// otherwise, the new larger number is the old smaller number, and
// the new smaller number is the remainder
larger = smaller;
smaller = remainder;
}
}

void WaitForEnter ()
{
printf("nPress Enter to quit");
fflush(stdin);
getchar();
}

void main (void)
{
// Get A
printf("Greatest Common Devisor Calculator, using Euclid's algorithm!n");
printf("nFirst number? ");
unsigned int A = 0;
if (scanf("%u",&A) == 0 || A == 0) {
printf("nMust input a positive integer greater than 0!");
WaitForEnter();
return;
}

// Get B
printf("Second number? ");
unsigned int B = 0;
if (scanf("%u",&B) == 0 || B == 0) {
printf("nMust input a positive integer greater than 0!");
WaitForEnter();
return;
}

// show the result
printf("nGCD(%u,%u) = %un", A, B, CalculateGCD(A,B));

// wait for user to press enter
WaitForEnter();
}
```

That book is filled with amazing treasures of knowledge and interesting stories to boot. I highly suggest flipping to a couple random chapters and reading it a bit. Very cool stuff in there (:

You might also find these links interesting or useful!
Wikipedia: Greatest Common Divisor
Wikipedia: Euclidean Algorithm

I’m sure there’s a way to extend this algorithm to work for N numbers at a time instead of only 2 numbers. I’ll leave that as a fun exercise for you if you want to play with that 😛

## Least Common Multiple

The least common multiple of two numbers is the smallest number that is evenly divisible by those numbers.

Kind of an ear full so some examples: The LCM of 3 and 4 is 12, the LCM of 1 and 7 is 7, the LCM of 20 and 35 is 140. Note that in the first two examples, the LCM is just the two numbers multiplied together, but in the 3rd example it isn’t (also an interesting thing of note is that the first 2 examples have a GCD of 1, while the 3rd example has a GCD of 5).

Well interestingly, calculating the LCM is super easy if you already know how to calculate the GCD. You just multiply the numbers together and divide by the GCD.

LCM(A,B) = (A*B) / GCD(A,B)

Interestingly though, GCD(A,B) divides evenly into both A and B and will result in an integer result. This means we can multiply by A or B after the division happens and get the exact same answer. More importantly though, it helps protect you against integer overflow in the A*B calculation. Using that knowledge the equation becomes this:

LCM(A,B) = (A / GCD(A,B))*B

Pretty neat! Here’s some C++ code that calculates LCM.

```#include <stdio.h>
#include <algorithm>

unsigned int CalculateGCD (unsigned int smaller, unsigned int larger)
{
// make sure A <= B before starting
if (larger < smaller)
std::swap(smaller, larger);

// loop
while (1)
{
// if the remainder of larger / smaller is 0, they are the same
// so return smaller as the GCD
unsigned int remainder = larger % smaller;
if (remainder == 0)
return smaller;

// otherwise, the new larger number is the old smaller number, and
// the new smaller number is the remainder
larger = smaller;
smaller = remainder;
}
}

unsigned int CalculateLCM (unsigned int A, unsigned int B)
{
// LCM(A,B) = (A/GCD(A,B))*B
return (A/CalculateGCD(A,B))*B;
}

void WaitForEnter ()
{
printf("nPress Enter to quit");
fflush(stdin);
getchar();
}

void main (void)
{
// Get A
printf("Least Common Multiple Calculator, using Euclid's algorithm for GCD!n");
printf("nFirst number? ");
unsigned int A = 0;
if (scanf("%u",&A) == 0 || A == 0) {
printf("nMust input a positive integer greater than 0!");
WaitForEnter();
return;
}

// Get B
printf("Second number? ");
unsigned int B = 0;
if (scanf("%u",&B) == 0 || B == 0) {
printf("nMust input a positive integer greater than 0!");
WaitForEnter();
return;
}

// show the result
printf("nLCM(%u,%u) = %un", A, B, CalculateLCM(A,B));

// wait for user to press enter
WaitForEnter();
}
```

Extending this to N numbers could be an interesting thing to try too (:

## Compile Time GCD and LCM

I’ve just heard that a compile time GCD and LCM implementation has been recomended for the STL. Check out the link below, kinda neat!

Greatest Common Divisor and Least Common Multiple

TTFN.

# DAPSE Preview

Here’s a preview of something I’m working on. Details aren’t ready yet, but I’m going to try and write up a little research paper about it and try to get it published if I can. I’m going to try Journal of Computer Graphics Techniques first, and if that doesn’t work out, I’m going to try plosone.com.

After going through the process I think I’ll be writing up some other papers about some other things, including some real time raytracing techniques 😛

I’ll probably also gather some notes and post them for other first time research paper writers looking to get their techniques out there.

Any guesses as to what DAPSE is all about? (:

As a very vague hint, this comic helped to inspire the name Saturday Morning Breakfast Cereal: Why We do Science # Bresenham’s Drawing Algorithms

If you were asked to name a line drawing algorithm, chances are you would say Bresenham. I recently needed to write my own software line drawing algorithm (CPU and regular ram, not GPU and VRAM) and Bresenham was the first to come to mind for me as well.

Believe it or not, Jack Bresenham actually came up with 2 famous line drawing algorithms. One is a run length algorithm, and the other is a run slice algorithm. People are most often familiar with the run length algorithm, which I mainly talk about in this post, but there’s some information about the run slice algorithm and links to other Bresenham primitive rendering algorithms below as well!

An interesting thing about both line algorithms is that they involve only integer mathematics, so there is no round off error, epsilons, numerical instability or anything like that. You use only integers and simple math (no divisions even!), and get the exact right answer out. I think that is pretty cool.

## Bresenham’s Run Length Line Algorithm Summarized

To help understand the code, I want to give a brief summarization of how the algorithm works at a high level.

The first step of the Bresenham line algorithm is to see if the line is longer on the X axis or Y axis. Whichever one it is longer on is the major axis, and the shorter one is the minor axis.

Then, starting at the starting point of the line, you loop across all pixels of the major axis, doing some math to decide for each pixel whether you need to move the pixel on the minor axis yet or not. Basically you keep track of the error – or the distance the pixel is away from the true position of the line on the minor axis – and if the error is greater than or equal to 1 pixel, you move the pixel on the minor axis and subtract one pixel from the error. If the error is smaller than 1 pixel, you keep it at the same value it was for the last pixel, and keep the error value the same, so that it can accumulate some more error for the next pixel and test again. The left line is longer on the X axis, so the major axis is the X axis. The right line is longer on the Y axis, so the major axis is the Y axis. Notice that there is one pixel for each value along the major axis of each line, but repeated pixel values along the minor axis of each line.

If you want the deeper details about the algorithm or the math behind it, check out this link:
Wikipedia: Bresenham’s line algorithm

## One Octant Code

Wikipedia says that many implementations implement the algorithm for a single octant (half of a quadrant) and then use coordinate conversions (flipping the x and y’s and/or negating them) to make the same logic work for any quadrant.

In that vein, here is a simple implementation for the first octant – where the major axis is X, and both X and Y are increasing from the starting point to the ending point.

```	void DrawLine (int x1, int y1, int x2, int y2, unsigned int color)
{
const int dx = x2 - x1;
const int dy = y2 - y1;

int Error = 2 * dy - dx;
int y = y1;

DrawPixel(x1, y1, color);
for (int x = x1+1; x < x2; ++x)
{
if (Error > 0)
{
y++;
Error += 2 * dy - 2 * dx;
}
else
{
Error += 2 * dy;
}
DrawPixel(x,y,color);
}
}
```

With the point of Bresenham being that it is efficient, let’s sacrifice readability a bit and get rid of those DrawPixel calls and perhaps over-micro-optimize a bit and make some consts for frequently used values.

```	void DrawLine (unsigned int* pixels, int width, int x1, int y1, int x2, int y2, unsigned int color)
{
const int dx = x2 - x1;
const int dy = y2 - y1;
const int dx2 = dx * 2;
const int dy2 = dy * 2;
const int dy2Mindx2 = dy2 - dx2;

int Error = dy2 - dx;

unsigned int* pixel = &amp;pixels[y1*width+x1];
*pixel = color;
for (int x = x2 - x1 - 1; x > 0; --x)
{
if (Error > 0)
{
pixel += width + 1;
Error += dy2Mindx2;
}
else
{
pixel++;
Error += dy2;
}
*pixel = color;
}
}
```

Cool, now let’s make it work for any line.

## Final Code

```	// Generic Line Drawing
// X and Y are flipped for Y maxor axis lines, but the pixel writes are handled correctly due to
// minor and major axis pixel movement
void DrawLineMajorAxis(
unsigned int* pixel,
int majorAxisPixelMovement,
int minorAxisPixelMovement,
int dx,
int dy,
unsigned int color
)
{
// calculate some constants
const int dx2 = dx * 2;
const int dy2 = dy * 2;
const int dy2Mindx2 = dy2 - dx2;

// calculate the starting error value
int Error = dy2 - dx;

// draw the first pixel
*pixel = color;

// loop across the major axis
while (dx--)
{
// move on major axis and minor axis
if (Error > 0)
{
pixel += majorAxisPixelMovement + minorAxisPixelMovement;
Error += dy2Mindx2;
}
// move on major axis only
else
{
pixel += majorAxisPixelMovement;
Error += dy2;
}

// draw the next pixel
*pixel = color;
}
}

// Specialized Line Drawing optimized for horizontal or vertical lines
// X and Y are flipped for Y maxor axis lines, but the pixel writes are handled correctly due to
// minor and major axis pixel movement
void DrawLineSingleAxis(unsigned int* pixel, int majorAxisPixelMovement, int dx, unsigned int color)
{
// draw the first pixel
*pixel = color;

// loop across the major axis and draw the rest of the pixels
while (dx--)
{
pixel += majorAxisPixelMovement;
*pixel = color;
};
}

// Draw an arbitrary line.  Assumes start and end point are within valid range
// pixels is a pointer to where the pixels you want to draw to start aka (0,0)
// pixelStride is the number of unsigned ints to get from one row of pixels to the next.
// Usually, that is the same as the width of the image you are drawing to, but sometimes is not.
void DrawLine(unsigned int* pixels, int pixelStride, int x1, int y1, int x2, int y2, unsigned int color)
{
// calculate our deltas
int dx = x2 - x1;
int dy = y2 - y1;

// if the X axis is the major axis
if (abs(dx) >= abs(dy))
{
// if x2 < x1, flip the points to have fewer special cases
if (dx < 0)
{
dx *= -1;
dy *= -1;
swap(x1, x2);
swap(y1, y2);
}

// get the address of the pixel at (x1,y1)
unsigned int* startPixel = &amp;pixels[y1 * pixelStride + x1];

// determine special cases
if (dy > 0)
DrawLineMajorAxis(startPixel, 1, pixelStride, dx, dy, color);
else if (dy < 0)
DrawLineMajorAxis(startPixel, 1, -pixelStride, dx, -dy, color);
else
DrawLineSingleAxis(startPixel, 1, dx, color);
}
// else the Y axis is the major axis
else
{
// if y2 < y1, flip the points to have fewer special cases
if (dy < 0)
{
dx *= -1;
dy *= -1;
swap(x1, x2);
swap(y1, y2);
}

// get the address of the pixel at (x1,y1)
unsigned int* startPixel = &amp;pixels[y1 * pixelStride + x1];

// determine special cases
if (dx > 0)
DrawLineMajorAxis(startPixel, pixelStride, 1, dy, dx, color);
else if (dx < 0)
DrawLineMajorAxis(startPixel, pixelStride, -1, dy, -dx, color);
else
DrawLineSingleAxis(startPixel, pixelStride, dy, color);
}
}
```

Using the above functions, I wrote a little test to draw lines from the center of an image towards the edges at 100 different angles, and also a horizontal and vertical line. Here’s the results: ## Run Slice Algorithm

So, like I said above, there is another Bresenham line algorithm that is a run slice algorithm.

What that means is that instead of looping across the major axis figuring out if each pixel needs to move on the minor axis as well, instead it loops across the minor axis, figuring out how many pixels it needs to write for that row or column of pixels.

One benefit of that algorithm is that it is less loop iterations since it’s looping across the minor axis pixels instead of the major axis.

Here’s an interesting read about Michael Abrash and his encounters with and the run slice algorithm:

Michael Abrash’s Graphics Programming Black Book Special Edition: The Good, the Bad, and the Run-Sliced

## Other Bresenham Algorithms

This was origionally just going to be about the line algorithms, and I was going to make up another post about the circle algorithm, but I changed my mind.

While doing some research to see if there was a Bresenham bezier curve algorithm I stumbled on the page below, which shows that yes, there is! There are quite a few other algorithms as well:

Many Bresenham algorithms with very short c++ implementations