Реализации алгоритмов/Алгоритм Евклида: различия между версиями
Добавлено описание алгоритма, добавлены реализации на JavaScript, переработаны реализации для Rust и ПМК, мелкие исправления |
|||
| Строка 571: | Строка 571: | ||
==Программируемые микрокалькуляторы «Электроника»== |
==Программируемые микрокалькуляторы «Электроника»== |
||
Использование: <первое число> → регистр Y, <второе число> → регистр X, В/О, С/П (НОД на индикаторе). |
'''Использование:''' <первое число> → регистр Y, <второе число> → регистр X, В/О, С/П (НОД на индикаторе). |
||
===Б3-21, МК-46 / 64, МС-1103=== |
===Б3-21, МК-46 / 64, МС-1103=== |
||
| Строка 581: | Строка 581: | ||
</source> |
</source> |
||
===Б3-34, МК-54 / 56 / 61 / 52 |
===Б3-34, МК-54 / 56 / 61 / 52 / 161 / 163 / 152 / 1152=== |
||
Вычитание, цикл. Корректно обрабатываются любые целые неотрицательные числа. В вычислениях участвуют только регистры стека X и |
Вычитание, цикл. Корректно обрабатываются любые целые неотрицательные числа. В вычислениях участвуют только регистры стека X, Y и X1. |
||
<source> |
<source> |
||
00. Fx≠0 01. 13 02. − 03. Fx<0 04. 09 05. /−/ 06. FВx 07. ↔ 08. − 09. FВx |
00. Fx≠0 01. 13 02. − 03. Fx<0 04. 09 05. /−/ 06. FВx 07. ↔ 08. − 09. FВx |
||
| Строка 588: | Строка 588: | ||
</source> |
</source> |
||
===МК-61 / 52 |
===МК-61 / 52 / 161 / 163 / 152 / 1152=== |
||
Деление с остатком, цикл. Корректно обрабатываются любые целые числа (включая 0 и отрицательные). В вычислениях участвуют |
Деление с остатком, цикл. Корректно обрабатываются любые целые числа (включая 0 и отрицательные). В вычислениях участвуют все регистры стека. |
||
<source> |
<source> |
||
00. Fx≠0 01. 13 02. ↔ 03. В↑ 04. FВx 05. ÷ 06. FВx 07. ↔ 08. K[x] 09. × |
00. Fx≠0 01. 13 02. ↔ 03. В↑ 04. FВx 05. ÷ 06. FВx 07. ↔ 08. K[x] 09. × |
||
Версия от 19:33, 4 августа 2019
Реализации алгоритма Евклида для вычисления НОД — наибольшего общего делителя (англ. 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, ОСТАТОК(b / a))
Оба алгоритма обобщаются на ноль и отрицательные значения. При этом следует иметь ввиду:
- Помимо положительных общих делителей у чисел имеются и отрицательные. Однако наибольший общий делитель по определению не может быть отрицательным (очевидно, что любое положительное число больше любого отрицательного). Таким образом НОД двух чисел равен НОДу их модулей.
- Если одно из чисел в паре равно нулю, а другое — нет, то их НОД равен модулю ненулевого числа.
- НОД пары нулей может рассматриваться, как неопределённое значение или бесконечность, а может приниматься равным нулю. Приведённые реализации в основном придерживаются последнего подхода (технически он реализуется проще).
- Подавляющее большинство языков программирования представляют отрицательные целые числа в так называемом дополнительном коде, при этом у наименьшего отрицательного значения типа отсутствует парное положительное значение (например наименьшее значение 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)
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
Деление с остатком, цикл:
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. С/П