Euclidean Algorithm

Computer science is (almost by definition) a science about computers -- a device first conceptualized in the 1800's. Computers have become so revolutionary, that it is difficult to think of our lives today without them. That said, algorithms are much older and have existed in the world for millennia. Incredibly, a few of the algorithms created before the Common Era (AD) are still in use today. One such algorithm was first described in Euclid's Elements (~ 300 BC) and has come to be known as the Euclidean Algorithm.

The algorithm is a simple way to find the greatest common divisor (GCD) of two numbers, which is useful for a number of different applications (like reducing fractions). The first method (envisioned by Euclid) uses simple subtraction:

int euclid_sub(int a, int b) {
    a = abs(a);
    b = abs(b);

    while (a != b) {
        if (a > b) {
            a -= b;
        } else {
            b -= a;
        }
    }

    return a;
}
public int EuclidSub(int a, int b)
{
    // Math.Abs for negative number support
    a = Math.Abs(a);
    b = Math.Abs(b);

    while (a != b)
    {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }

    return a;
}
(defn euclid-sub [a b]
  (loop [i (Math/abs a) j (Math/abs b)]
    (if (= i j)
      i
      (if (> i j)
        (recur (- i j) j)
        (recur i (- j i))))))
int euclid_sub(int a, int b) {
  a = std::abs(a);
  b = std::abs(b);

  while (a != b) {
    if (a > b) {
      a -= b;
    } else {
      b -= a;
    }
  }

  return a;
}
public static int euclidSub(int a, int b) {
    a = Math.abs(a);
    b = Math.abs(b);

    while (a != b) {
        if (a > b) {
            a -= b;
        } else {
            b -= a;
        }
    }

    return a;
}
function euclid_sub(a, b){
    a = Math.abs(a);
    b = Math.abs(b);

    while (a != b){
        if (a > b){
            a = a - b;
        }
        else{
            b = b - a;
        }
    }

    return a;
}
def euclid_sub(a, b):

    a = abs(a)
    b = abs(b)

    while a != b:
        if a > b:
            a -= b
        else:
            b -= a

    return a
euclidSub :: Integer -> Integer -> Integer
euclidSub a b = inner (abs a) (abs b)
  where
    inner x y
      | x == y = x
      | x < y = euclidSub x (y - x)
      | otherwise = euclidSub (x - y) y
fn euclid_sub(mut a: i64, mut b: i64) -> i64 {
    a = a.abs();
    b = b.abs();
    while a != b {
        if a < b {
            b -= a;
        } else {
            a -= b;
        }
    }

    a
}
let euclid_sub a b =
  let rec inner a b =
    if a = b then
      a
    else if a < b then
      inner a (b - a)
    else
      inner (a - b) b
  in (inner (abs a) (abs b))
func euclidSub(a, b int) int {
    a = abs(a)
    b = abs(b)

    for a != b {
        if a > b {
            a -= b
        } else {
            b -= a
        }
    }

    return a
}
func euclidSub(a: Int, b: Int) -> Int {
    var a = abs(a)
    var b = abs(b)

    while (a != b) {
        if (a > b) {
            a -= b
        } else {
            b -= a
        }
    }

    return a
}
function gcd = euclidSub(a,b)

    a = abs(a);
    b = abs(b);

    while a ~= b
        if a > b
            a = a - b;
        else
            b = b - a;
        end
    end

    gcd = a;
end
function euclidSub (a, b)
  local a = math.abs(a)
  local b = math.abs(b)

  while a ~= b do
    if a > b then
      a = a-b
    else
      b = b-a
    end
  end

  return a
end
function euclid_mod(a::Int64, b::Int64)
    a = abs(a)
    b = abs(b)

    while(b != 0)
        b,a = a%b,b
    end

    return a
end

Here, we simply line the two numbers up every step and subtract the lower value from the higher one every timestep. Once the two values are equal, we call that value the greatest common divisor. A graph of a and b as they change every step would look something like this:

Modern implementations, though, often use the modulus operator (%) like so

int euclid_mod(int a, int b) {
    a = abs(a);
    b = abs(b);

    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}
public int EuclidMod(int a, int b)
{
    // Math.Abs for negative number support
    a = Math.Abs(a);
    b = Math.Abs(b);

    while (b != 0)
    {
        var temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}
(defn euclid-mod [a b]
  (loop [i (Math/abs a) j (Math/abs b)]
    (if (zero? j)
      i
      (recur j (% i j)))))
// Euclidean algorithm using modulus
int euclid_mod(int a, int b) {
  a = std::abs(a);
  b = std::abs(b);

  while (b != 0) {
    a = std::exchange(b, a % b);
  }

  return a;
}
public static int euclidMod(int a, int b) {
    while (b != 0) {
        int tmp = b;
        b = a % b;
        a = tmp;
    }

    return a;
}
function euclid_mod(a, b){
    a = Math.abs(a);
    b = Math.abs(b);

    var temp;
    while (b != 0){
        temp = b;
        b = a%b;
        a = temp;
    }

    return a;
}
def euclid_mod(a, b):

    a = abs(a)
    b = abs(b)

    while b > 0:
        a, b = b, a % b

    return a
euclidMod :: Integer -> Integer -> Integer
euclidMod a b = inner (abs a) (abs b)
  where
    inner x 0 = x
    inner x y = inner y (x `mod` y)
fn euclid_rem(mut a: i64, mut b: i64) -> i64 {
    a = a.abs();
    b = b.abs();
    while b != 0 {
        let tmp = b;
        b = a % b;
        a = tmp;
    }

    a
}
let euclid_mod a b =
  let rec inner a = function
  | 0 -> a
  | b -> inner b (a mod b)
  in (inner (abs a) (abs b))
func euclidMod(a, b int) int {
    a = abs(a)
    b = abs(b)

    for b != 0 {
        a, b = b, a%b
    }

    return a
}
func euclidMod(a: Int, b: Int) -> Int {
    var a = abs(a);
    var b = abs(b);

    while (b != 0) {
        let temp = b
        b = a % b
        a = temp
    }

    return a
}
function gcd = euclidMod(a,b)

    a=abs(a);
    b=abs(b);

    while b > 0
        temp = b;
        b = mod(a,b);
        a = temp;
    end

    gcd = a;
end
function euclidMod (a, b)
  local a = math.abs(a)
  local b = math.abs(b)

  while b ~= 0 do
    a, b = b, a%b
  end

  return a
end
function euclid_sub(a::Int64, b::Int64)
    a = abs(a)
    b = abs(b)

    while (a != b)
        if (a > b)
            a -= b
        else
            b -= a
        end
    end

    return a
end

Here, we set b to be the remainder of a%b and a to be whatever b was last timestep. Because of how the modulus operator works, this will provide the same information as the subtraction-based implementation, but when we show a and b as they change with time, we can see that it might take many fewer steps:

The Euclidean Algorithm is truly fundamental to many other algorithms throughout the history of computer science and will definitely be used again later. At least to me, it's amazing how such an ancient algorithm can still have modern use and appeal. That said, there are still other algorithms out there that can find the greatest common divisor of two numbers that are arguably better in certain cases than the Euclidean algorithm, but the fact that we are discussing Euclid two millennia after his death shows how timeless and universal mathematics truly is. I think that's pretty cool.

Example Code

#include <stdio.h>
#include <math.h>

int euclid_mod(int a, int b) {
    a = abs(a);
    b = abs(b);

    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

int euclid_sub(int a, int b) {
    a = abs(a);
    b = abs(b);

    while (a != b) {
        if (a > b) {
            a -= b;
        } else {
            b -= a;
        }
    }

    return a;
}

int main() {
    int check1 = euclid_mod(64 * 67, 64 * 81);
    int check2 = euclid_sub(128 * 12, 128 * 77);

    printf("%d\n", check1);
    printf("%d\n", check2);

    return 0;
}

EuclideanAlgorithm.cs

// submitted by Julian Schacher (jspp)
using System;

namespace EuclideanAlgorithm
{
    public class EuclideanAlgorithm
    {
        public int EuclidSub(int a, int b)
        {
            // Math.Abs for negative number support
            a = Math.Abs(a);
            b = Math.Abs(b);

            while (a != b)
            {
                if (a > b)
                    a = a - b;
                else
                    b = b - a;
            }

            return a;
        }

        public int EuclidMod(int a, int b)
        {
            // Math.Abs for negative number support
            a = Math.Abs(a);
            b = Math.Abs(b);

            while (b != 0)
            {
                var temp = b;
                b = a % b;
                a = temp;
            }

            return a;
        }
    }
}

Program.cs

// submitted by Julian Schacher (jspp)
using System;

namespace EuclideanAlgorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("EuclideanAlgorithm");
            var euclideanAlgorithm = new EuclideanAlgorithm();
            int check = euclideanAlgorithm.EuclidMod(64 * 67, 64 * 81);
            int check2 = euclideanAlgorithm.EuclidSub(128 * 12, 128 * 77);

            Console.WriteLine(check);
            Console.WriteLine(check2);
        }
    }
}
;; earthfail
(defn euclid-sub [a b]
  (loop [i (Math/abs a) j (Math/abs b)]
    (if (= i j)
      i
      (if (> i j)
        (recur (- i j) j)
        (recur i (- j i))))))
(defn euclid-mod [a b]
  (loop [i (Math/abs a) j (Math/abs b)]
    (if (zero? j)
      i
      (recur j (% i j)))))

(print
 (euclid-sub (* 64 67)
             (* 64 81))
 (euclid-mod (* 128 12)
             (* 128 77)))
// originally contributed by James Schloss (Leios)
// restyled by Nicole Mazzuca (ubsan)
#include <cmath>
#include <iostream>
#include <utility>

// Euclidean algorithm using modulus
int euclid_mod(int a, int b) {
  a = std::abs(a);
  b = std::abs(b);

  while (b != 0) {
    a = std::exchange(b, a % b);
  }

  return a;
}

// Euclidean algorithm with subtraction
int euclid_sub(int a, int b) {
  a = std::abs(a);
  b = std::abs(b);

  while (a != b) {
    if (a > b) {
      a -= b;
    } else {
      b -= a;
    }
  }

  return a;
}

int main() {
  auto check1 = euclid_mod(64 * 67, 64 * 81);
  auto check2 = euclid_sub(128 * 12, 128 * 77);

  std::cout << check1 << '\n';
  std::cout << check2 << '\n';
}
// submitted by lolatomroflsinnlos, modified by xam4lor
public class EuclideanAlgo {
    public static int euclidSub(int a, int b) {
        a = Math.abs(a);
        b = Math.abs(b);

        while (a != b) {
            if (a > b) {
                a -= b;
            } else {
                b -= a;
            }
        }

        return a;
    }

    public static int euclidMod(int a, int b) {
        while (b != 0) {
            int tmp = b;
            b = a % b;
            a = tmp;
        }

        return a;
    }

    public static void main(String[] args) {
        System.out.println(euclidMod(64 * 67, 64 * 81));
        System.out.println(euclidSub(128 * 12, 128 * 77));
    }
}
function euclid_mod(a, b){
    a = Math.abs(a);
    b = Math.abs(b);

    var temp;
    while (b != 0){
        temp = b;
        b = a%b;
        a = temp;
    }

    return a;
}

function euclid_sub(a, b){
    a = Math.abs(a);
    b = Math.abs(b);

    while (a != b){
        if (a > b){
            a = a - b;
        }
        else{
            b = b - a;
        }
    }

    return a;
}

console.log(euclid_mod(64*67, 64*81));
console.log(euclid_sub(128*12, 128*77));
def euclid_mod(a, b):

    a = abs(a)
    b = abs(b)

    while b > 0:
        a, b = b, a % b

    return a

def euclid_sub(a, b):

    a = abs(a)
    b = abs(b)

    while a != b:
        if a > b:
            a -= b
        else:
            b -= a

    return a

if __name__=="__main__":
    print('Euclidean mod: ', euclid_mod(64 * 67, 64 * 81))
    print('Euclidean sub: ', euclid_sub(128 * 12, 128 * 77))
-- contributed by Nicole Mazzuca (ubsan)
euclidSub :: Integer -> Integer -> Integer
euclidSub a b = inner (abs a) (abs b)
  where
    inner x y
      | x == y = x
      | x < y = euclidSub x (y - x)
      | otherwise = euclidSub (x - y) y

euclidMod :: Integer -> Integer -> Integer
euclidMod a b = inner (abs a) (abs b)
  where
    inner x 0 = x
    inner x y = inner y (x `mod` y)

main :: IO ()
main = do
  let chk1 = euclidMod (64 * 67) (64 * 81)
      chk2 = euclidSub (128 * 12) (128 * 77)
  print chk1
  print chk2
// contributed by Nicole Mazzuca (ubsan)

fn euclid_sub(mut a: i64, mut b: i64) -> i64 {
    a = a.abs();
    b = b.abs();
    while a != b {
        if a < b {
            b -= a;
        } else {
            a -= b;
        }
    }

    a
}

fn euclid_rem(mut a: i64, mut b: i64) -> i64 {
    a = a.abs();
    b = b.abs();
    while b != 0 {
        let tmp = b;
        b = a % b;
        a = tmp;
    }

    a
}

fn main() {
    let chk1 = euclid_rem(64 * 67, 64 * 81);
    let chk2 = euclid_sub(128 * 12, 128 * 77);
    println!("{}", chk1);
    println!("{}", chk2);
}
(* contributed by Nicole Mazzuca (ubsan) *)

let euclid_mod a b =
  let rec inner a = function
  | 0 -> a
  | b -> inner b (a mod b)
  in (inner (abs a) (abs b))

let euclid_sub a b =
  let rec inner a b =
    if a = b then
      a
    else if a < b then
      inner a (b - a)
    else
      inner (a - b) b
  in (inner (abs a) (abs b))

let chk1 = euclid_mod (64 * 67) (64 * 81)
let chk2 = euclid_sub (128 * 12) (128 * 77)
let () =
  chk1 |> print_int |> print_newline;
  chk2 |> print_int |> print_newline
// Submitted by Chinmaya Mahesh (chin123)

package main

import "fmt"

func abs(a int) int {
    if a < 0 {
        a = -a
    }
    return a
}

func euclidMod(a, b int) int {
    a = abs(a)
    b = abs(b)

    for b != 0 {
        a, b = b, a%b
    }

    return a
}

func euclidSub(a, b int) int {
    a = abs(a)
    b = abs(b)

    for a != b {
        if a > b {
            a -= b
        } else {
            b -= a
        }
    }

    return a
}

func main() {
    check1 := euclidMod(64*67, 64*81)
    check2 := euclidSub(128*12, 128*77)

    fmt.Println(check1)
    fmt.Println(check2)
}
func euclidSub(a: Int, b: Int) -> Int {
    var a = abs(a)
    var b = abs(b)

    while (a != b) {
        if (a > b) {
            a -= b
        } else {
            b -= a
        }
    }

    return a
}

func euclidMod(a: Int, b: Int) -> Int {
    var a = abs(a);
    var b = abs(b);

    while (b != 0) {
        let temp = b
        b = a % b
        a = temp
    }

    return a
}

func main() {
    print(euclidMod(a: 64 * 67, b: 64 * 81))
    print(euclidSub(a: 128 * 12, b: 128 * 77))
}

main()
// Submitted by Max Weinstein

function gcd = euclidSub(a,b)

    a = abs(a);
    b = abs(b);

    while a ~= b
        if a > b
            a = a - b;
        else
            b = b - a;
        end
    end

    gcd = a;
end

function gcd = euclidMod(a,b)

    a=abs(a);
    b=abs(b);

    while b > 0
        temp = b;
        b = mod(a,b);
        a = temp;
    end

    gcd = a;
end

function euclid()
    ['gcd(520,420) via euclidSub: ',num2str(euclidSub(520,420))]
    ['gcd(183,244) via euclidMod: ',num2str(euclidMod(183,244))]
end
function euclidSub (a, b)
  local a = math.abs(a)
  local b = math.abs(b)

  while a ~= b do
    if a > b then
      a = a-b
    else
      b = b-a
    end
  end

  return a
end

function euclidMod (a, b)
  local a = math.abs(a)
  local b = math.abs(b)

  while b ~= 0 do
    a, b = b, a%b
  end

  return a
end

function main ()
  print(euclidSub(128 * 12, 128 * 77))
  print(euclidMod(64 * 67, 64 * 81))
end

main()
function euclid_mod(a::Int64, b::Int64)
    a = abs(a)
    b = abs(b)

    while(b != 0)
        b,a = a%b,b
    end

    return a
end

function euclid_sub(a::Int64, b::Int64)
    a = abs(a)
    b = abs(b)

    while (a != b)
        if (a > b)
            a -= b
        else
            b -= a
        end
    end

    return a
end

function main()
    check1 = euclid_mod(64 * 67, 64 * 81);
    check2 = euclid_sub(128 * 12, 128 * 77);

    println("Modulus-based euclidean algorithm result: $(check1)")
    println("subtraction-based euclidean algorithm result: $(check2)")

end

main()

results matching ""

    No results matching ""