Реализации алгоритмов/Алгоритм Евклида
Реализации алгоритма Евклида для вычисления НОД — наибольшего общего делителя (англ. 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). Следовательно вычисление НОД с применением наименьшего значения знакового типа может вызывать переполнение и давать неверные результаты.
Как правило, языки программирования включают функцию или оператор нахождения остатка от деления двух чисел, поэтому соответствующие реализации используют именно быстрый алгоритм Евклида. Алгоритм, построенный на вычитании, имеет смысл использовать на тех системах, где встроенная операция нахождения остатка отсутствует и её невыгодно эмулировать, например, через деление и взятие целой части.
Реализации
править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
Классический
правитьЦикл, вычитание (операция нахождения остатка 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
Цикл, деление с остатком:
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
В следующих примерах используется тип 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: Тип 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 следует заменить 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);
}
Деление с остатком, рекурсия:
gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, (A rem B)).
Деление с остатком, рекурсия:
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 ;
Тип 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)
}
Деление с остатком, рекурсия:
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)
Деление с остатком, цикл:
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
Тип 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;
Деление с остатком, рекурсия:
sub gcd {
return $_[0] != 0 ? gcd ( ( $_[1] % $_[0] ), $_[0] ) : $_[1];
}
Деление с остатком, цикл:
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);
}
Деление с остатком, рекурсия:
?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)
Деление с остатком, рекурсия:
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).
Деление с остатком, цикл:
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)
Деление с остатком, цикл:
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
Деление с остатком, цикл:
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)
}
}
Вычитание, рекурсия:
(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. С/П