Реализации алгоритмов/Алгоритм Евклида

Далее приводятся реализации алгоритма Евклида для вычисления НОД на различных языках программирования.

BASIC

QBASIC, QuickBasic, VisualBasic (до версий с поддержкой .NET)

Деление с остатком, без рекурсии:

Function GCD (a As Integer, b As Integer) As Integer
	Dim d As Integer
	Do While a <> 0 and b <> 0
		If a >=b Then
			a = a mod b
		Else
			b = b mod a
		End If
	Loop
	GCD = a + b
End Function

C

Тип T определён как typedef … T;, вместо … следует подставить любой целочисленный тип (int, unsigned, short и т. д.)

Деление с остатком, без рекурсии:

T gcd (T a, T b) {
    T c;
    while (b) {
        c = a % b;
        a = b;
        b = c;
    }
    return (a < 0) ? -a : a;
}

Более короткое решение:

T gcd (T a, T b) {
    while (b)
        b ^= a ^= b ^= a %= b;
    return a;
}

Деление с остатком, рекурсия:

T gcd (T a, T b) {
   return (b == 0) ? a : gcd(b, a % b);
}

Вычитание, без рекурсии:

T gcd (T a, T b) {
    while (a != b) {
        if (a > b)
            a -= b;
        else
            b -= a;
    }
    return a;
}

C#

Деление с остатком, без рекурсии:

int GCD (int a, int b)
{
    while (b != 0)
        b = a % (a = b);
    return a;
}

Erlang

Деление с остатком, рекурсия:

gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, (A rem B)).

F#

Деление с остатком, рекурсия:

let rec nod a b =
    match b with
    |0 -> a
    |b -> nod b (a % b)

Forth (диалект RetroForth)

Деление с остатком, рекурсия:

: GCD ( n1 n2 -- n ) tuck mod 0; GCD ;

Haskell

Деление с остатком, рекурсия:

gcd :: Integral a => a -> a -> a
gcd 0 0 = error "НОД от 0 и 0 не определён."
gcd x y = gcd' (abs x) (abs y)
    where gcd' x 0 = x
          gcd' x y = gcd' y (x `rem` y)

Java

Деление с остатком, без рекурсии:

public static <T> T gcd (T a, T b) {
    while (b != 0) {
        T c = a % b;
        a = b;
        b = c;
    }
    return a;
}

Также допустимы функции, аналогичные написанным выше на C, например так:

public static <T> gcd (T a, T b) {
    while (b != 0)
        b ^= a ^= b ^= a %= b;
    return a;
}

*короткая запись работает не корректно. Например при начальных значениях 34 и 9 уже на следующем шаге значения получаются 43 и 0...

Деление с остатком, рекурсия:

public static <T> T gcd (T a, T b) {
    return b == 0 ? a : gcd(b, a % b);
}

Pascal

Тип T определён как type T = …;, вместо … следует подставить любой целочисленный тип (Integer, Byte, LongInt и т. д.)

Деление с остатком, без рекурсии:

function GCD (a, b: T): T;
begin
    while a * b <> 0 do
       if a > b then
           a := a mod b
       else
           b := b mod a;
    gcd := a + b
end;

Более быстрый алгоритм:

function GCD (a, b: T): T;
var c: T;
begin
    while b > 0 do
    begin
        c := a mod b;
        a := b;
        b := c
    end;
    gcd := a
end;

Деление с остатком, рекурсия:

function gcd (a, b: T): T;
begin
   if b = 0 then
       gcd := a
   else
       gcd := gcd(b, a mod b)
end;

Perl

Деление с остатком, рекурсия:

sub gcd {
    return  $_[0] != 0  ?  gcd ( ( $_[1] % $_[0] ), $_[0] )  :  $_[1];
}

PHP

Деление с остатком, без рекурсии:

function gcd ($a, $b) {
    while ($a <> 0 && $b <> 0) {
        if ($a > $b)
            $a = $a % $b;
        else
            $b = $b % $a;
        $gcd = $a + $b;
    }
    return $gcd;
}
echo gcd(5, 3);

Prolog

Деление с остатком, рекурсия:

?GCD(a,b,x)

GCD(0,b,b) <-
GCD(a,0,a) <-
GCD(a,b,x) <- a >= b, m is a mod b, GCD(m, b, x)
GCD(a,b,x) <- a < b, m is b mod a, GCD(a, m, x)
</code>

===[[w:SWI-Prolog]]===
Деление с остатком, рекурсия:
<source>
gcd(0,B,B).
gcd(A,0,A).

gcd(A,B,X) :-  A >= B, M is A mod B, gcd(M, B, X).
gcd(A,B,X) :-  A < B, M is B mod A, gcd(A, M, X).

Python

Деление с остатком, без рекурсии:

def gcd (a, b):
    while b:
        a, b = b, a % b
    return a

Деление с остатком, рекурсия:

def gcd (a, b):
    return a if b == 0 else gcd(b, a % b)

Ruby

Деление с остатком, без рекурсии:

def gcd (a, b)
    a, b = b, a % b until b.zero?
    a
end

Деление с остатком, рекурсия:

def gcd (a, b)
    return a if b.zero?
    gcd(b, a % b)
end

Вычитание, без рекурсии:

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

Scheme

Вычитание, рекурсия:

(define gcd (lambda (a b)
  (if (> a b) (gcd (- a b) b)
     (if (< a b) (gcd a (- b a))
        a))))

Shell

Деление с остатком, рекурсия:

gcd () {
   n=1 a=$1 b=$2
   if [[ $a -ne 0 ]]
   then
      gcd $(( $b % $a )) $a
      let "n = $?"
   else
      let "n = $b"
   fi
   return $n
}

gcd $1 $2
echo "Greatest common divisor is $?"

Глагол

Деление с остатком, без рекурсии:

ЗАДАЧА НОД (a, b: ЦЕЛ): ЦЕЛ;
УКАЗ
    ПОКА (a # 0) И (b # 0) ВЫП
        ЕСЛИ a >= b ТО
            a := a ОСТАТОК b
        ИНАЧЕ
            b := b ОСТАТОК a
        КОН
    КОН;
    ВОЗВРАТ a + b
КОН НОД;

Ассемблер

ARM

Вычитание, без рекурсии:

loop	CMP Ri, Rj		; проверка условий NE (i != j), GT (i > j) и LT (i < j);
	SUBGT Ri, Ri, Rj	; если GT, выполняется i = i-j;
	SUBLT Rj, Rj, Ri	; если LT, выполняется j = j-i;
	BNE loop		; если NE - переход на метку loop.

Z80

Вычитание, без рекурсии:

GCD_DEHL:        ;CALL Inputs: HL,DE; Output: DE
        AND     A       ;сброс CF
LOOP:
        SBC     HL,DE   ;совмещение трёх в одном - одного сравнения и поочередно двух вычитаний.
        RET     Z       ;минимизация общего размера, поэтому в цикле.
        JR      NC,LOOP
        ADD     HL,DE   ;откат лишнего вычитания
        EX      DE,HL
        JR      GCD_DEHL

Программируемые микрокалькуляторы «Электроника»

Деление с остатком, без рекурсии. Корректно обрабатываются любые целые числа (включая 0 и отрицательные). В вычислениях участвуют только регистры стека.

Использование: <первое число> В↑ <второе число> В/О С/П (НОД на индикаторе).

МК-52 / 61 / 152 / 161

00. Fx≠0   01. 13     02. ↔      03. В↑     04. FВx    05. ÷      06. FВx    07. ↔      08. K[x]   09. ×
10. −      11. Fx=0   12. 02     13. +      14. K|x|   15. С/П

См. также

• Бинарный алгоритм вычисления НОД