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

Реализации алгоритма Евклида для вычисления НОД — наибольшего общего делителя (англ. GCD — greatest common divisor) двух целых чисел на различных языках программирования.

Реализации

Assembler

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

BASIC

Оригинальный (Dartmouth BASIC)

Цикл, вычитание (операция нахождения остатка MOD отсутствовала в этой версии языка):

10 PRINT "Two integer numbers";
20 INPUT A, B
30 PRINT "GCD("; A; ", "; B,") = ";
40 LET A = ABS(A)
50 IF B = 0 THEN GOTO 120
60 LET B = ABS(B)
70 IF A < B THEN GOTO 90
80 LET A = A - B: GOTO 70
90 IF A = 0 THEN LET A = B: GOTO 120
100 LET B = B - A: IF B >= A THEN GOTO 100
110 IF B > 0 THEN GOTO 80
120 PRINT A
130 END

GW-BASIC и совместимые диалекты

Цикл, деление с остатком:

10 INPUT "Two integer numbers", A%, B%
20 PRINT "GCD("; A%; ", "; B%; ") = ";
30 WHILE B% <> 0
40 A% = A% MOD B%
50 IF A% = 0 THEN A% = B%: B% = 0: ELSE B% = B% MOD A%
60 WEND
70 PRINT ABS(A%)

QuickBasic версий < 4.0, Turbo Basic

Цикл, деление с остатком:

DEF FNGCD%(A%, B%)
	DO UNTIL B% = 0
		A% = A% MOD B%
		IF A% = 0 THEN
			FNGCD% = ABS(B%)
			EXIT DEF
		END IF
		B% = B% MOD A%
	LOOP
	FNGCD% = ABS(A%)
END DEF

PowerBASIC, QBASIC, QuickBasic версий ≥ 4.0, Visual Basic

В следующих примерах используется тип Long (длинное целое); вместо него можно применять также тип Integer (стандартное целое).

Цикл, деление с остатком:

Function GCD(a As Long, b As Long) As Long
	Do Until b = 0
		a = a Mod b
		If a = 0 Then
			GCD = b
			Exit Function
		End If
		b = b Mod a
	Loop
	GCD = a
End Function

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

Function GCD(a As Long, b As Long) As Long
	If b = 0 Then
		GCD = Abs(a)
	Else
		GCD = GCD(b, a Mod b)
	End If
End Function

Visual Basic .NET

В следующих примерах используется тип Long (длинное целое); вместо него можно применять любые другие целочисленные типы платформы .NET.

Цикл, деление с остатком:

Function GCD(ByVal a As Long, ByVal b As Long) As Long
	Do Until b = 0
		a = a Mod b
		If a = 0 Then Return Math.Abs(b)
		b = b Mod a
	Loop
	Return Math.Abs(a)
End Function

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

Function GCD(ByVal a As Long, ByVal b As Long) As Long
	Return If(b = 0, Math.Abs(a), GCD(b, a Mod b)) ' VB.NET 2008 или более поздняя версия
End Function

C/C++

C: Тип Integer должен быть задан как:

typedef int Integer; /* Вместо int можно подставить любой другой целочисленный тип */

C++: Любую из нижеприведённых функций (включая abs) следует предварить строкой:

template <typename Integer>

Для корректной обработки отрицательных чисел все последующие примеры на C/C++ используют функцию вычисления модуля числа:

Integer abs (Integer value) {
	return (value < 0) ? -value : value;
}

Деление с остатком, цикл:

Integer gcd (Integer a, Integer b) {
	for (Integer c; b; ) {
		c = a % b;
		a = b;
		b = c;
	}
	return abs(a);
}

Без использования дополнительной переменной:

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

Без использования дополнительной переменной и с наименьшим числом сравнений и присваиваний:

Integer gcd (Integer a, Integer b) {
	if (!a)
		return abs(b);
	if (!b)
		return abs(a);
	for ( ; ; )
		if (!(a %= b))
			return abs(b);
		else if (!(b %= a))
			return abs(a);
}

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

Integer gcd (Integer a, Integer b) {
	return !b ? abs(a) : gcd(b, a % b);
}

Вычитание, цикл:

Integer gcd (Integer a, Integer b) {
	a = abs(a);
	b = abs(b);
	while (b) {
		while (a >= b)
			a -= b;
		if (!a)
			return b;
		do {
			b -= a;
		} while (b >= a);
    }
    return a;
}

C#, Java

Приведён код для C#. Для Java следует заменить Abs на abs и, для соответствия правилам оформления кода, переименовать функции в gcd и перенести { в конец предыдущей строки.

Вместо long можно использовать и другие целочисленные типы — byte, int и т. д.

Деление с остатком, цикл:

static long GCD(long a, long b)
{
    while (b != 0)
        b = a % (a = b);
    return Math.Abs(a);
}

static long GCD(long a, long b)
{
	if (a == 0)
		return Math.Abs(b);
	if (b == 0)
		return Math.Abs(a);
	for ( ; ; ) {
		if ((a %= b) == 0)
			return Math.Abs(b);
		if ((b %= a) == 0)
			return Math.Abs(a);
	}
}

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

static long GCD (long a, long b)
{
    return b == 0 ? Math.Abs(a) : GCD(b, a % b);
}

Erlang

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

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

F#

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

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

Forth (диалект RetroForth)

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

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

Go

Тип IntType определён как:

type Integer = int // Вместо int можно подставить любой другой целочисленный тип

Для корректной обработки отрицательных чисел все последующие примеры на Go используют функцию вычисления модуля числа:

func IntAbs(value Integer) Integer {
	if value < 0 {
		return -value
	}
	return value
}

Деление с остатком, цикл:

func GCD(a, b Integer) Integer {
	for b != 0 {
		a %= b
		if a == 0 {
			return IntAbs(b)
		}
		b %= a
	}
	return IntAbs(a)
}

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

func GCD(a, b Integer) Integer {
	if b == 0 {
		return IntAbs(a)
	}
	return GCD(b, a % b)
}

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)

Pascal

Тип TInteger определён как:

type TInteger = Integer; { Вместо Integer можно подставить любой другой целочисленный тип }

Деление с остатком, цикл:

function GCD(a, b: TInteger): TInteger;
begin
	while b <> 0 do
	begin
		a := a mod b;
		if a = 0 then
		begin
			a := b;
			b := 0
		end
		else
			b := b mod a
	end;
	GCD := Abs(a)
end;

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

function GCD(a, b: TInteger): TInteger;
begin
	if b = 0 then
		GCD := Abs(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) {
	if ($a === 0)
		return abs($b);
	if ($b === 0)
		return abs($a)
	for ( ; ; )
		if (($a %= $b) === 0)
			return abs($b);
		else if (($b %= $a) === 0)
			return abs($a);
}
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)

w:SWI-Prolog

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

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: int, b: int) -> int:
	while b:
		a, b = b, a % b
	return abs(a)

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

def gcd(a: int, b: int) -> int:
	return abs(a) if b == 0 else gcd(b, a % b)

Ruby

Деление с остатком, цикл:

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

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

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

Rust

Деление с остатком, цикл:

extern crate num;

use self::num::FromPrimitive;
use std::ops::Rem;


pub fn gcd <IntType> (mut a: IntType, mut b: IntType) -> IntType
where IntType: Copy + FromPrimitive + PartialEq + Rem<Output = IntType> {
	let zero = FromPrimitive::from_u32(0u32).unwrap(); // Обобщённая константа 0
	let mut c: IntType;
	while b != zero {
		c = a % b;
		a = b;
		b = c;
	}
	a
}

Вычитание, цикл:

use std::ops::SubAssign;


pub fn gcd <T: Copy + PartialOrd + SubAssign> (mut a: T, mut b: T) -> T {
	while a != b {
		if a > b {
			a -= b;
		} else {
			b -= a;
		}
	}
	a
}

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: ЦЕЛ): ЦЕЛ;
УКАЗ
	ПОКА b # 0 ВЫП
		a := a ОСТАТОК b;
		ЕСЛИ a = 0 ТО
        	a := b;
			b := 0
		ИНАЧЕ
			b := b ОСТАТОК a
        КОН
    КОН;
    ВОЗВРАТ МОДУЛЬ(a)
КОН НОД;

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

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

МК-61 / 52 / 152 / 161 / 163 / 1152

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

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. С/П

Б3-34, МК-54 / 56 / 61 / 52 / 152 / 161 / 163 / 1152

Вычитание, цикл. Корректно обрабатываются любые целые неотрицательные числа. В вычислениях участвуют только регистры стека X и Y.

00. −      01. Fx≠0   02. 12     03. Fx<0   04. 09     05. FВx    06. ↔      07. /−/    08. −      09. FВx
10. БП     11. 00     12. FВx    13. С/П

Б3-21, МК-46 / 64, МС-1103

Вычитание, цикл. Корректно обрабатываются любые целые неотрицательные числа. В вычислениях участвуют только регистры стека X и Y.

00. Px≠0   01. ↔      02. −      03. Px≥0   04. F1     05. ↔
10. −      11. /−/    12. ↔      13. Px=0   14. Peⁱˣ   15. ↔
20. С/П

См. также

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