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

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

Описание

Классический алгоритм Евклида применяется к паре неотрицательных целых чисел. Пока ни одно из чисел в паре не равно нулю, из большего числа вычитается меньшее; вычитаемое и полученная разность формируют новую пару. Действие повторяется, пока один из элементов пары не обратится в 0, тогда значение другого будет равно искомому НОД.

Рекурсивная формулировка классического алгоритма:

• НОД(a, 0) = a
• НОД(a, b) = НОД(a, a − b) при a ≥ b
• НОД(a, b) = НОД(b, b − a) при a < b

Несложно заметить, что последовательное вычитание из большего числа меньшего, пока разность не станет меньше вычитаемого, соответствует нахождению остатка от деления большего числа на меньшее. На этом основан так называемый быстрый алгоритм Евклида: в паре чисел одно число делится с остатком на второе; делитель и полученный остаток формируют новую пару. Действие повторяется, пока один из элементов пары не обратится в 0, тогда значение другого будет равно искомому НОД.

Рекурсивная формулировка быстрого алгоритма:

• НОД(a, 0) = a
• НОД(a, b) = НОД(b, ОСТАТОК(a / b))

Оба алгоритма обобщаются на ноль и отрицательные значения. При этом следует иметь ввиду:

• Помимо положительных общих делителей у чисел имеются и отрицательные. Однако наибольший общий делитель по определению не может быть отрицательным (очевидно, что любое положительное число больше любого отрицательного). Таким образом НОД двух чисел равен НОДу их модулей.
• Если одно из чисел в паре равно нулю, а другое — нет, то их НОД равен модулю ненулевого числа.
• НОД пары нулей может рассматриваться, как неопределённое значение или бесконечность, а может приниматься равным нулю. Приведённые реализации в основном придерживаются последнего подхода (технически он реализуется проще).
• Подавляющее большинство языков программирования представляют отрицательные целые числа в так называемом дополнительном коде, при этом у наименьшего отрицательного значения типа отсутствует парное положительное значение (например наименьшее значение 16-битного знакового целого — −32768, а наибольшее — 32767). Следовательно вычисление НОД с применением наименьшего значения знакового типа может вызывать переполнение и давать неверные результаты.

Как правило, языки программирования включают функцию или оператор нахождения остатка от деления двух чисел, поэтому соответствующие реализации используют именно быстрый алгоритм Евклида. Алгоритм, построенный на вычитании, имеет смысл использовать на тех системах, где встроенная операция нахождения остатка отсутствует и её невыгодно эмулировать, например, через деление и взятие целой части.

Реализации

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

Классический

Цикл, вычитание (операция нахождения остатка 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.X, Visual Basic версий ≤ 6.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);
		else 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

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

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)

JavaScript, ECMAScript

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

function gcd(a, b) {
	if (a === 0)
		return Math.abs(b);
	if (b === 0)
		return Math.abs(a);
	for ( ; ; )
		if ((a %= b) === 0)
			return Math.abs(b);
		else if ((b %= a) === 0)
			return Math.abs(a);
}

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

const gcd = (a, b) => b === 0 ? Math.abs(a) : gcd(b, a % b); // ECMAScript версий ≥ 6.0

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);
}

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)

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

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

use num::Zero;
use std::ops::{RemAssign, Sub};

fn gcd <Integer> (a: Integer, b: Integer) -> Integer
where Integer: Zero + PartialOrd + Sub<Output = Integer> + RemAssign + Copy
{
	let result: Integer;
	if a.is_zero() {
		result = b;
	} else if b.is_zero() {
		result = a;
	} else {
		// Вместо неизменяемых параметров a и b дальше используются переменные _a и _b
		let mut _a = a;
		let mut _b = b;

		loop {
			_a %= _b;
			if _a.is_zero() {
				result = _b;
				break;
			};
			_b %= _a;
			if _b.is_zero() {
				result = _a;
				break;
			};
		};
	};
	// `result` берётся по модулю
	if result < Integer::zero() {
		Integer::zero() - result
	} else {
		result
	}
}

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

use num::Zero;
use std::ops::{Rem, Sub};

pub fn gcd <Integer> (a: Integer, b: Integer) -> Integer
where Integer: Zero + PartialOrd + Sub<Output = Integer> + Rem<Output = Integer> + Copy
{
	if b.is_zero() {
		// Возвращаемое значение берётся по модулю
		if a < Integer::zero() {
			Integer::zero() - a
		} else {
			a
		}
	} else {
		gcd(b, a % b)
	}
}

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)
КОН НОД;

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

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

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

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

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

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

МК-61 / 52 / 161 / 163 / 152 / 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. С/П

См. также

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