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

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

Scheme

Алгоритм вычитанием

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

Ruby

Функция в рекурсивном виде:

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

Функция в нерекурсивном виде:

def gcd(a, b)
    while !b.eql? 0
        a, b = b, a % b
    end
    return a
end

Алгоритм вычитанием:

def gcd(a, b)
    while !a.eql? b
        if a > b
            a -= b
        else
           b -= a
        end
    end
    return a
end

Python

Функция в рекурсивном виде:

def gcd(a, b):
  return b and gcd(b, a % b) or a

Функция в нерекурсивном виде:

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

Perl

Функция в рекурсивном виде:

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

Shell

Функция в рекурсивном виде:

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

nod $1 $2
echo "NOD is $?"

Си

 int gcd(int a, int b) {
   int c;
   while (b) {
      c = a % b;
      a = b;
      b = c;        
   }
   return abs(a);
 }

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

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

Та же функция в рекурсивном виде:

 int gcd(int a, int b) {
   if (b == 0) return a;
   return gcd(b, a % b);
 }

Немного короче:

 int gcd(int a, int b) {
   return b? gcd(b, a % b) : a;
 }

Алгоритм вычитанием:

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

Форт (диалект RetroForth)

Рекурсивный алгоритм

: НОД  ( n1 n2 -- n )  tuck mod 0; НОД ;

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 (rem x y)

Глагол

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

Pascal

  function nod( a, b: longint): longint; 
  begin
   while (a <> 0) and (b <> 0) do
     if a >= b then 
       a:= a mod b 
     else 
       b:= b mod a;
   nod:= a + b;
  end;

В рекурсивном виде:

  function nod(var a, b: longint): longint; 
  begin
   if (a = 0) or (b = 0) then
     if a = 0 then
       nod:= b
     else 
       nod:= a
   else 
     if a >= b then 
       nod:= nod( a mod b, b)
     else 
       nod:= nod( a, b mod a)
  end;

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).

Erlang

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

Java

public class GCD {
    public static int gcd(int a,int b) {
        while (b !=0) {
            int tmp = a%b;
            a = b;
            b = tmp;
        }
        return a;
    }
}

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

public class GCD {
    public static int gcd(int a,int b) {
        while(b!=0) b^=a^=b^=a%=b;
        return a;
    }
}

C#

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

Реализации бинарного алгоритма нахождения НОД

С

 unsigned int gcd(unsigned int u, unsigned int v)
 {
     int shift;
 
     /* GCD(0,x) := x */
     if (u == 0 || v == 0)
       return u | v;
 
     /* Let shift := lg K, where K is the greatest power of 2
        dividing both u and v. */
     for (shift = 0; ((u | v) & 1) == 0; ++shift) {
         u >>= 1;
         v >>= 1;
     }
 
     while ((u & 1) == 0)
       u >>= 1;
 
     /* From here on, u is always odd. */
     do {
         while ((v & 1) == 0)  /* Loop X */
           v >>= 1;
 
         /* Now u and v are both odd, so diff(u, v) is even.
            Let u = min(u, v), v = diff(u, v)/2. */
         if (u < v) {
             v -= u;
         } else {
             unsigned int diff = u - v;
             u = v;
             v = diff;
         }
         v >>= 1;
     } while (v != 0);
 
     return u << shift;
 }

C#

long GCD(long a, long b)
{
   if (a == 0) return b;
   if (b == 0) return a;
   if (a == b) return a;
   if (a == 1 || b == 1) return 1;
   if ((a % 2 == 0) && (b % 2 == 0)) return 2 * GCD(a / 2, b / 2);
   if ((a % 2 == 0) && (b % 2 != 0)) return GCD(a / 2, b);
   if ((a % 2 != 0) && (b % 2 == 0)) return GCD(a, b / 2);
   return GCD(b, (long)Math.Abs(a - b));
}

Pascal/Delphi

function GCD(a, b: integer): integer;
begin
   if (a = 0) then
   begin
      Result:= b;
      Exit;
   end else
   if (b = 0) then
   begin
      Result:= a;
      Exit;
   end else
   if (a = b) then
   begin
      Result:= a;
      Exit;
   end else
   if (a = 1) or (b =1) then
   begin
      Result:= 1;
      Exit;
   end else
   if (a mod 2 = 0) and (b mod 2 = 0) then
   begin
      Result:= 2*GCD(Trunc(a/2), Trunc(b/2));
      Exit;
   end else
   if (a mod 2 = 0) and (b mod 2 <> 0) then
   begin
      Result:= GCD(Trunc(a/2), b);
      Exit;
   end else
   if (a mod 2 <> 0) and (b mod 2 = 0) then
   begin
      Result:= GCD(a, Trunc(b/2));
      Exit;
   end;
Result:= GCD(b, Abs(a - b));
end;

Perl

sub nod
{
return $_[0] if $_[1] == 0;
return $_[1] if $_[0] == 0;
($u, $v)=@_; $g=1;$t=100;
while (1)
{
if ($u%2==1 || $v%2==1) {last;};
     $u>>=1;  ##(right shift)
     $v>>=1;
     $g<<=1;  ## (left shift)
}

while ($u > 0)
{
     if ($u%2==0 && $u>0) {$u = $u>>1;}
     elsif ($v%2==0 && $v>0) {$v = $v>>1;}
     else
          {
           $t = abs (($u-$v)/2);
           if ($u < $v) {$v = $t;} else {$u = $t;}
          }
}
 return $v*$g;
}