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 euclidSub(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;
}
(defun euclid-sub (a b)
  (euclid-sub* (abs a) (abs b)))

(defun euclid-sub* (a b)
  (if (eq a b)
    a
    (if (> a b)
      (euclid-sub* (- a b) b)
      (euclid-sub* a (- b 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_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
proc euclid_sub(in1, in2: int): int =
  var
    a = abs(in1)
    b = abs(in2)

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

    return a
euclid_sub:
  mov    rax, rdi           # Get abs of a
  sar    rax, 31
  xor    rdi, rax
  sub    rdi, rax
  mov    rax, rsi           # Get abs of b
  sar    rax, 31
  xor    rsi, rax
  sub    rsi, rax
  jmp    check
loop:
  cmp    rdi, rsi           # Find which is bigger
  jle    if_true
  sub    rdi, rsi           # If a is bigger then a -= b
  jmp    check
if_true:
  sub    rsi, rdi           # Else b -= a
check:
  cmp    rsi, rdi           # Check if a and b are not equal
  jne    loop
  mov    rax, rdi           # Return results
  ret
INTEGER FUNCTION euclid_sub(a, b)
    IMPLICIT NONE
    INTEGER, INTENT(INOUT) :: a, b

    a = ABS(a)
    b = ABS(b)

    DO WHILE (a /= b)

        IF (a > b) THEN
            a = a - b
        ELSE
            b = b - a
        END IF
    END DO

    euclid_sub = a

END FUNCTION euclid_sub
function euclid_sub(int $a, int $b): int
{
    $a = abs($a);
    $b = abs($b);

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

    return $a;
}
: euclid- ( a b -- gcd )
  [ abs ] [email protected]
  [ 2dup = ]
  [
    ! make sure the lower number is deeper
    2dup >= [ swap ] when
    over -
    ! leaves us with stack { <lower> <greater - lower> }
  ]
  until
  ! we have the GCD twice now, drop one
  drop
;
Euclidian algorithm subtraction method.
Enter two positive integers.    
































The                      
end.
def euclid_sub(a: Int, b: Int): Int =
  (Math.abs(a), Math.abs(b)) match {
    case (0, _) | (_, 0) => 0
    case (x, y) if x < y => euclid(x, y - x)
    case (x, y) if x > y => euclid(x - y, y)
    case _ => a
(define (euclid_sub a b)
  (local ((define (euclid_sub* x y)
          (if (= x y)
              x
              (if (> x y)
                  (euclid_sub* (- x y) y)
                  (euclid_sub* x (- y x))
                  )
              )
          )) (euclid_sub* (abs a) (abs b))
    )
  )
def gcd_minus(a, b)
    a = a.abs
    b = b.abs
    until a == b
        if a > b
            a -= b
        else
            b -= a
        end
    end
    a
end
Integer>>euclidSub: secondNumber
    "Euclidean algorithm with subtraction"
    | a b |
    a := self abs.
    b := secondNumber abs.
    [ a == b ] whileFalse: [ 
        a > b ifTrue: [ 
            a := a - b.
        ] ifFalse: [ 
            b := b - a.
        ].
    ].
    ^a.
🐇 ❗️ 🔼 a 🔢 b 🔢 ➡️ 🔢 🍇
  💭 Use 🏧 (returns the absolute value) to support negative numbers.
  🏧a ❗️ ➡️ 🖍🆕var_a
  🏧b ❗️ ➡️ 🖍🆕var_b

  ️🔁 ❎ var_a 🙌 var_b ❗️ 🍇
    ↪️ var_a ▶️ var_b 🍇
      var_a ⬅️ ➖ var_b
    🍉
    🙅 🍇
      var_b ⬅️ ➖ var_a
    🍉
  🍉

  ↩️ var_a
🍉
HOW IZ I UKLIDSUP YR NUM1 AN YR NUM2
    NUM1 R I IZ ABZ YR NUM1 MKAY
    NUM2 R EI IZ ABZ YR NUM2 MKAY

    IM IN YR LOOP 
        BOTH SAEM NUM1 AN NUM2, O RLY?
            YA RLY, FOUND YR NUM1
        OIC        

        DIFFRINT NUM1 AN SMALLR OF NUM1 AN NUM2, O RLY?
            YA RLY, NUM1 R DIFF OF NUM1 AN NUM2
            NO WAI, NUM2 R DIFF OF NUM2 AN NUM1
        OIC
    IM OUTTA YR LOOP

IF U SAY SO
euclid_sub() {
    local a
    local b
    a=$(abs "$1")
    b=$(abs "$2")

    while (( a != b )); do
        if (( a > b )); then
            ((a -= b))
        else
            ((b -= a))
        fi
    done
    printf "%s" "$a"
}

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 euclidMod(a, b) {
  a = Math.abs(a);
  b = Math.abs(b);

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

  return a;
}
(defun euclid-mod (a b)
  (if (zerop b)
    (abs a)
    (euclid-mod b (mod a b))))
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_mod(a::Int64, b::Int64)
    a = abs(a)
    b = abs(b)

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

    return a
end
proc euclid_mod(in1, in2: int): int =
  var
    a = abs(in1)
    b = abs(in2)

  while b != 0:
    let temp: int = b
    b = a mod b
    a = temp;

    return a
# rdi - a
# rsi - b
# RET rax - gcd of a and b
euclid_mod:
  mov    rax, rdi           # Get abs of a
  sar    rax, 31
  xor    rdi, rax
  sub    rdi, rax
  mov    rax, rsi           # Get abs of b
  sar    rax, 31
  xor    rsi, rax
  sub    rsi, rax
  jmp    mod_check
mod_loop:
  xor    rdx, rdx           # Take the mod of a and b
  mov    rax, rdi
  div    rsi
  mov    rdi, rsi           # Set b to the mod of a and b
  mov    rsi, rdx           # Set a to b
mod_check:
  cmp    rsi, 0             # Check if b is non-zero
  jne    mod_loop
  mov    rax, rdi           # Return the result
  ret
INTEGER FUNCTION euclid_mod(a, b)
    IMPLICIT NONE
    INTEGER, INTENT(INOUT) :: a, b
    INTEGER                :: temp

    DO WHILE (b > 0)
        temp = b
        b = MODULO(a,b)
        a = temp
    END DO

    euclid_mod = a

END FUNCTION euclid_mod
function euclid_mod(int $a, int $b): int
{
    $a = abs($a);
    $b = abs($b);

    while ($b !== 0) {
        list($b, $a) = [$a % $b, $b];
    }

    return $a;
}
: euclid% ( a b -- gcd )
  [ abs ] [email protected]   ! take both absolute values
  [ dup zero? ] ! check if `b` (on top) is 0
  [
    ! a b -> a b b -> b a b -> b a%b
    dup -rot mod
  ]
  until
  ! the zero is on top, so get rid of it
  drop
;
Euclidian algorithm modulo method.
Enter two positive integers.    
























The
end.

def euclid_mod(a: Int, b: Int): Int =
  (Math.abs(a), Math.abs(b)) match {
    case (_, 0) => a
    case (a, b) => euclid_mod(b, a % b)
(define (euclid_mod a b)
  (local ((define (euclid_mod* a b)
           (if (= 0 b)
               (abs a)
               (euclid_mod* b (modulo a b))
               )
           )) (euclid_mod* a b)
    )
  )
def gcd_mod(a, b)
    a = a.abs
    b = b.abs
    a, b = b, a%b until b.zero?
    a
end
Integer>>euclidMod: secondNumber
    "Euclidean algorithm with modulus."
    | a b oldB |
    a := self abs.
    b := secondNumber abs.
    [ b == 0 ] whileFalse: [ 
        oldB := b.
        b := a % b.
        a := oldB.
    ].
    ^a.
🐇 ❗️ ⏫ a 🔢 b 🔢 ➡️ 🔢 🍇
  💭 Use 🏧 (returns the absolute value) to support negative numbers.
  🏧a ❗️ ➡️ 🖍🆕var_a
  🏧b ❗️ ➡️ 🖍🆕var_b

  ️🔁 ❎ var_b 🙌 0 ❗️ 🍇
    var_b ➡️ temp
    var_a 🚮 var_b ➡️ 🖍var_b
    temp ➡️ 🖍var_a
  🍉

  ↩️ var_a
🍉
HOW IZ I UKLIDMOD YR NUM1 AN YR NUM2
    NUM1 R I IZ ABZ YR NUM1 MKAY
    NUM2 R I IZ ABZ YR NUM2 MKAY

    IM IN YR LOOP 
        BOTH SAEM NUM2 AN 0, O RLY?
            YA RLY, FOUND YR NUM1
        OIC

        I HAS A TMP ITZ NUM2
        NUM2 R MOD OF NUM1 AN NUM2
        NUM1 R TMP
    IM OUTTA YR LOOP

IF U SAY SO
euclid_mod() {
    local a
    local b
    a=$(abs "$1")
    b=$(abs "$2")

    while (( b != 0 )); do
        ((tmp = b))
        ((b = a % b))
        ((a = tmp))
    done
    printf "%s" "$a"
}

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.

Video Explanation

Here's a video on the Euclidean algorithm:

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)))
#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 euclidMod(a, b) {
  a = Math.abs(a);
  b = Math.abs(b);

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

  return a;
}

function euclidSub(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(euclidMod(64 * 67, 64 * 81));
console.log(euclidSub(128 * 12, 128 * 77));
;;;; Euclid algorithm implementation

(defun euclid-sub (a b)
  (euclid-sub* (abs a) (abs b)))

(defun euclid-sub* (a b)
  (if (eq a b)
    a
    (if (> a b)
      (euclid-sub* (- a b) b)
      (euclid-sub* a (- b a)))))

(defun euclid-mod (a b)
  (if (zerop b)
    (abs a)
    (euclid-mod b (mod a b))))

(print 
  (euclid-sub (* 64 67)
              (* 64 81)))
(print 
  (euclid-mod (* 128 12)
              (* 128 77)))

;; built-in function: (gcd 80 40)
;; quick test
(assert 
  (=  (euclid-sub (* 64 67) (* 64 81))
      (gcd (* 64 67) (* 64 81))))

(assert 
  (=  (euclid-mod (* 64 67) (* 64 81))
      (gcd (* 64 67) (* 64 81))))
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()
proc euclid_mod(in1, in2: int): int =
  var
    a = abs(in1)
    b = abs(in2)

  while b != 0:
    let temp: int = b
    b = a mod b
    a = temp;

    return a

proc euclid_sub(in1, in2: int): int =
  var
    a = abs(in1)
    b = abs(in2)

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

    return a

echo euclid_sub(64 * 67, 64 * 81)
echo euclid_mod(128 * 12, 128 * 77)
.intel_syntax noprefix

.section .rodata
  fmt:  .string "%d\n"

.section .text
  .global main
  .extern printf

# rdi - a
# rsi - b
# RET rax - gcd of a and b
euclid_mod:
  mov    rax, rdi           # Get abs of a
  sar    rax, 31
  xor    rdi, rax
  sub    rdi, rax
  mov    rax, rsi           # Get abs of b
  sar    rax, 31
  xor    rsi, rax
  sub    rsi, rax
  jmp    mod_check
mod_loop:
  xor    rdx, rdx           # Take the mod of a and b
  mov    rax, rdi
  div    rsi
  mov    rdi, rsi           # Set b to the mod of a and b
  mov    rsi, rdx           # Set a to b
mod_check:
  cmp    rsi, 0             # Check if b is non-zero
  jne    mod_loop
  mov    rax, rdi           # Return the result
  ret

euclid_sub:
  mov    rax, rdi           # Get abs of a
  sar    rax, 31
  xor    rdi, rax
  sub    rdi, rax
  mov    rax, rsi           # Get abs of b
  sar    rax, 31
  xor    rsi, rax
  sub    rsi, rax
  jmp    check
loop:
  cmp    rdi, rsi           # Find which is bigger
  jle    if_true
  sub    rdi, rsi           # If a is bigger then a -= b
  jmp    check
if_true:
  sub    rsi, rdi           # Else b -= a
check:
  cmp    rsi, rdi           # Check if a and b are not equal
  jne    loop
  mov    rax, rdi           # Return results
  ret

main:
  mov    rdi, 4288          # Call euclid_mod
  mov    rsi, 5184
  call   euclid_mod
  mov    rdi, OFFSET fmt    # Print output
  mov    rsi, rax
  xor    rax, rax
  call   printf
  mov    rdi, 1536          # Call euclid_sub
  mov    rsi, 9856
  call   euclid_sub
  mov    rdi, OFFSET fmt    # Print output
  mov    rsi, rax
  xor    rax, rax
  call   printf
  xor    rax, rax           # Return 0
  ret
INTEGER FUNCTION euclid_sub(a, b)
    IMPLICIT NONE
    INTEGER, INTENT(INOUT) :: a, b

    a = ABS(a)
    b = ABS(b)

    DO WHILE (a /= b)

        IF (a > b) THEN
            a = a - b
        ELSE
            b = b - a
        END IF
    END DO

    euclid_sub = a

END FUNCTION euclid_sub 

INTEGER FUNCTION euclid_mod(a, b)
    IMPLICIT NONE
    INTEGER, INTENT(INOUT) :: a, b
    INTEGER                :: temp

    DO WHILE (b > 0)
        temp = b
        b = MODULO(a,b)
        a = temp
    END DO

    euclid_mod = a

END FUNCTION euclid_mod

PROGRAM euclidean

    IMPLICIT NONE
    INTEGER :: a, b, euclid_sub, euclid_mod

    a = 24
    b = 27
    WRITE(*,*) 'Subtraction method: GCD is: ', euclid_sub(a, b)

    a = 24
    b = 27
    WRITE(*,*) 'Modulus method:     GCD is: ', euclid_mod(a, b)

END PROGRAM euclidean
<?php
declare(strict_types=1);

function euclid_sub(int $a, int $b): int
{
    $a = abs($a);
    $b = abs($b);

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

    return $a;
}

function euclid_mod(int $a, int $b): int
{
    $a = abs($a);
    $b = abs($b);

    while ($b !== 0) {
        list($b, $a) = [$a % $b, $b];
    }

    return $a;
}

printf('Euclidean mod: %s', euclid_mod(64 * 67, 64 * 81));
echo PHP_EOL;
printf('Euclidean sub: %s', euclid_sub(128 * 12, 128 * 77));
echo PHP_EOL;
: euclid- ( a b -- gcd )
  [ abs ] [email protected]
  [ 2dup = ]
  [
    ! make sure the lower number is deeper
    2dup >= [ swap ] when
    over -
    ! leaves us with stack { <lower> <greater - lower> }
  ]
  until
  ! we have the GCD twice now, drop one
  drop
;

: euclid% ( a b -- gcd )
  [ abs ] [email protected]   ! take both absolute values
  [ dup zero? ] ! check if `b` (on top) is 0
  [
    ! a b -> a b b -> b a b -> b a%b
    dup -rot mod
  ]
  until
  ! the zero is on top, so get rid of it
  drop
;

42 56 euclid% .  ! 14
48 180 euclid% . ! 12

42 56 euclid- .  ! 14
48 180 euclid- . ! 12

Here is a readable version of the algorithms with comments. First, subtraction method:

Reading the input: a, b
[SPACE][SPACE][SPACE][LF]            push 0
[SPACE][SPACE][SPACE][TAB][LF]       push 1
[TAB][LF][TAB][TAB]                  readi
[TAB][LF][TAB][TAB]                  readi

Loop: a, b => a, b-a
[LF][SPACE][SPACE][LF]               label_0:
[SPACE][SPACE][SPACE][LF]              push 0
[TAB][TAB][TAB]                        retrieve
[SPACE][SPACE][SPACE][TAB][LF]         push 1
[TAB][TAB][TAB]                        retrieve
[TAB][SPACE][SPACE][TAB]               sub
[SPACE][LF][SPACE]                     dup
[LF][TAB][SPACE][TAB][LF]              jmp zero label_1
[SPACE][LF][SPACE]                     dup
[LF][TAB][TAB][TAB][SPACE][LF]         jmp neg label_2
[SPACE][SPACE][SPACE][LF]              push 0
[SPACE][LF][TAB]                       swap
[TAB][TAB][SPACE]                      store
[LF][SPACE][LF][LF]                    jmp label_0

Exit when a=b
[LF][SPACE][SPACE][TAB][LF]          label_1:
[SPACE][SPACE][SPACE][LF]              push 0
[TAB][TAB][TAB]                        retrieve
[TAB][LF][SPACE][TAB]                  printi
[LF][LF][LF]                           end

If a>b: a, b => a-b, b
[LF][SPACE][SPACE][TAB][SPACE][LF]   label_2:
[SPACE][SPACE][SPACE][LF]              push 0
[SPACE][LF][TAB]                       swap
[TAB][SPACE][SPACE][TAB]               sub
[SPACE][SPACE][SPACE][TAB][LF]         push 1
[SPACE][LF][TAB]                       swap
[TAB][TAB][SPACE]                      store
[LF][SPACE][LF][LF]                    jmp label_0

and modulo method:

Reading the input: a, b
[SPACE][SPACE][SPACE][LF]       push 0
[SPACE][SPACE][SPACE][TAB][LF]  push 1
[TAB][LF][TAB][TAB]             readi
[TAB][LF][TAB][TAB]             readi

Loop: a, b => b, a%b
[LF][SPACE][SPACE][LF]          label_0:
[SPACE][SPACE][SPACE][LF]         push 0
[TAB][TAB][TAB]                   retrieve
[SPACE][LF][SPACE]                dup
[LF][TAB][SPACE][TAB][LF]         jmp zero label_1
[SPACE][SPACE][SPACE][TAB][LF]    push 1
[TAB][TAB][TAB]                   retrieve
[SPACE][LF][TAB]                  swap
[TAB][SPACE][TAB][TAB]            mod
[SPACE][SPACE][SPACE][LF]         push 0
[TAB][TAB][TAB]                   retrieve
[SPACE][SPACE][SPACE][TAB][LF]    push 1
[SPACE][LF][TAB]                  swap
[TAB][TAB][SPACE]                 store
[SPACE][SPACE][SPACE][LF]         push 0
[SPACE][LF][TAB]                  swap
[TAB][TAB][SPACE]                 store
[LF][SPACE][LF][LF]               jmp label_0

Exit when b=0
[LF][SPACE][SPACE][TAB][LF]     label_1:
[SPACE][SPACE][SPACE][TAB][LF]    push 1
[TAB][TAB][TAB]                   retrieve
[TAB][LF][SPACE][TAB]             printi
[LF][LF][LF][LF]                  end
object Euclid {

  def euclid_sub(a: Int, b: Int): Int =
    (Math.abs(a), Math.abs(b)) match {
      case (0, _) | (_, 0) => 0
      case (x, y) if x < y => euclid(x, y - x)
      case (x, y) if x > y => euclid(x - y, y)
      case _ => a
    }

  def euclid_mod(a: Int, b: Int): Int =
    (Math.abs(a), Math.abs(b)) match {
      case (_, 0) => a
      case (a, b) => euclid_mod(b, a % b)
    }

  def main(args: Array[String]): Unit = {
    println(euclid_sub(151 * 899, 151 * 182))
    println(euclid_mod(151 * 899, 151 * 182))
  }

}
#lang racket

(define (euclid_sub a b)
  (local ((define (euclid_sub* x y)
          (if (= x y)
              x
              (if (> x y)
                  (euclid_sub* (- x y) y)
                  (euclid_sub* x (- y x))
                  )
              )
          )) (euclid_sub* (abs a) (abs b))
    )
  )

(define (euclid_mod a b)
  (local ((define (euclid_mod* a b)
           (if (= 0 b)
               (abs a)
               (euclid_mod* b (modulo a b))
               )
           )) (euclid_mod* a b)
    )
  )

(displayln (euclid_sub (* 64 67) (* 64 81)))
(displayln (euclid_mod (* 128 12) (* 128 77)))
def gcd_mod(a, b)
    a = a.abs
    b = b.abs
    a, b = b, a%b until b.zero?
    a
end

def gcd_minus(a, b)
    a = a.abs
    b = b.abs
    until a == b
        if a > b
            a -= b
        else
            b -= a
        end
    end
    a
end

p gcd_mod(12 * 6, 12 * 4) #=> 12
p gcd_mod(9 * 667, 9 * 104) #=> 9

p gcd_minus(12 * 6, 12 * 4) #=> 12
p gcd_minus(9 * 667, 9 * 104) #=> 9
Integer>>euclidSub: secondNumber
    "Euclidean algorithm with subtraction"
    | a b |
    a := self abs.
    b := secondNumber abs.
    [ a == b ] whileFalse: [ 
        a > b ifTrue: [ 
            a := a - b.
        ] ifFalse: [ 
            b := b - a.
        ].
    ].
    ^a.

Integer>>euclidMod: secondNumber
    "Euclidean algorithm with modulus."
    | a b oldB |
    a := self abs.
    b := secondNumber abs.
    [ b == 0 ] whileFalse: [ 
        oldB := b.
        b := a % b.
        a := oldB.
    ].
    ^a.

Transcript show: ((64 * 67) euclidSub: (64 * 81)).
Transcript cr.
Transcript show: ((128 * 12) euclidMod: (128 * 77)).
🐇 ⬆️ 🍇
  🐇 ❗️ 🔼 a 🔢 b 🔢 ➡️ 🔢 🍇
    💭 Use 🏧 (returns the absolute value) to support negative numbers.
    🏧a ❗️ ➡️ 🖍🆕var_a
    🏧b ❗️ ➡️ 🖍🆕var_b

    ️🔁 ❎ var_a 🙌 var_b ❗️ 🍇
      ↪️ var_a ▶️ var_b 🍇
        var_a ⬅️ ➖ var_b
      🍉
      🙅 🍇
        var_b ⬅️ ➖ var_a
      🍉
    🍉

    ↩️ var_a
  🍉

  🐇 ❗️ ⏫ a 🔢 b 🔢 ➡️ 🔢 🍇
    💭 Use 🏧 (returns the absolute value) to support negative numbers.
    🏧a ❗️ ➡️ 🖍🆕var_a
    🏧b ❗️ ➡️ 🖍🆕var_b

    ️🔁 ❎ var_b 🙌 0 ❗️ 🍇
      var_b ➡️ temp
      var_a 🚮 var_b ➡️ 🖍var_b
      temp ➡️ 🖍var_a
    🍉

    ↩️ var_a
  🍉
🍉

🏁 🍇
  😀 🔡 ️🔼🐇⬆️ 🤜64 ✖️ 67🤛 🤜64 ✖️ 81🤛 ❗️ 10 ❗️❗️
  😀 🔡 ️⏫🐇⬆️ 🤜128 ✖️ 12🤛 🤜128 ✖️ 77🤛 ❗️ 10 ❗️❗️
🍉
HAI 1.2
    HOW IZ I ABZ YR NUM
        DIFFRINT NUM AN BIGGR OF NUM AN 0, O RLY?
            YA RLY, FOUND YR DIFF OF 0 AN NUM
            NO WAI, FOUND YR NUM
        OIC
    IF U SAY SO

    HOW IZ I UKLIDMOD YR NUM1 AN YR NUM2
        NUM1 R I IZ ABZ YR NUM1 MKAY
        NUM2 R I IZ ABZ YR NUM2 MKAY

        IM IN YR LOOP 
            BOTH SAEM NUM2 AN 0, O RLY?
                YA RLY, FOUND YR NUM1
            OIC

            I HAS A TMP ITZ NUM2
            NUM2 R MOD OF NUM1 AN NUM2
            NUM1 R TMP
        IM OUTTA YR LOOP

    IF U SAY SO

    HOW IZ I UKLIDSUP YR NUM1 AN YR NUM2
        NUM1 R I IZ ABZ YR NUM1 MKAY
        NUM2 R EI IZ ABZ YR NUM2 MKAY

        IM IN YR LOOP 
            BOTH SAEM NUM1 AN NUM2, O RLY?
                YA RLY, FOUND YR NUM1
            OIC        

            DIFFRINT NUM1 AN SMALLR OF NUM1 AN NUM2, O RLY?
                YA RLY, NUM1 R DIFF OF NUM1 AN NUM2
                NO WAI, NUM2 R DIFF OF NUM2 AN NUM1
            OIC
        IM OUTTA YR LOOP

    IF U SAY SO

    I HAS A CHECK1 ITZ I IZ UKLIDMOD YR PRODUKT OF 64 AN 67 AN YR PRODUKT OF 64 AN 81 MKAY
    I HAS A CHECK2 ITZ I IZ UKLIDSUP YR PRODUKT OF 128 AN 12  AN YR PRODUKT OF 128 AN 77 MKAY

    VISIBLE CHECK1
    VISIBLE CHECK2
KTHXBYE
#!/usr/bin/env bash
abs() {
    local ret=$1
    if (( ret < 0 )); then
        ((ret *= -1))
    fi
    printf "%s" "$ret"
} 

euclid_mod() {
    local a
    local b
    a=$(abs "$1")
    b=$(abs "$2")

    while (( b != 0 )); do
        ((tmp = b))
        ((b = a % b))
        ((a = tmp))
    done
    printf "%s" "$a"
}

euclid_sub() {
    local a
    local b
    a=$(abs "$1")
    b=$(abs "$2")

    while (( a != b )); do
        if (( a > b )); then
            ((a -= b))
        else
            ((b -= a))
        fi
    done
    printf "%s" "$a"
}

result=$(euclid_mod $((64 * 67)) $((64 * 81)))
echo "$result"
result=$(euclid_sub $((128 * 12)) $((128 * 77)))
echo "$result"

results matching ""

    No results matching ""