Реализации алгоритмов/Бинарный алгоритм вычисления НОД: различия между версиями

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Отмена правок до редакции 51022.
Реализации на Pascal, Perl, Scala перенесены из ../Алгоритм Евклида.
Строка 1: Строка 1:
{{wikipedia |Бинарный алгоритм вычисления НОД}}
{{wikipedia|Наибольший общий делитель}}
== Реализации бинарного алгоритма нахождения НОД ==
{{wikipedia|Бинарный алгоритм нахождения НОД}}


=== С ===
== С ==


<source lang="c">
<source lang="c">
Строка 9: Строка 7:
{
{
int shift;
int shift;

/* GCD(0,x) := x */
/* GCD(0,x) := x */
if (u == 0 || v == 0)
if (u == 0 || v == 0)
return u | v;
return u | v;

/* Let shift := lg K, where K is the greatest power of 2
/* Let shift := lg K, where K is the greatest power of 2
dividing both u and v. */
dividing both u and v. */
Строка 20: Строка 18:
v >>= 1;
v >>= 1;
}
}

while ((u & 1) == 0)
while ((u & 1) == 0)
u >>= 1;
u >>= 1;

/* From here on, u is always odd. */
/* From here on, u is always odd. */
do {
do {
while ((v & 1) == 0) /* Loop X */
while ((v & 1) == 0) /* Loop X */
v >>= 1;
v >>= 1;

/* Now u and v are both odd, so diff(u, v) is even.
/* Now u and v are both odd, so diff(u, v) is even.
Let u = min(u, v), v = diff(u, v)/2. */
Let u = min(u, v), v = diff(u, v)/2. */
Строка 40: Строка 38:
v >>= 1;
v >>= 1;
} while (v != 0);
} while (v != 0);

return u << shift;
return u << shift;
}
}
</source>
</source>


=== C# ===
== C# ==


<source lang="csharp">
<source lang="csharp">
Строка 61: Строка 59:
</source>
</source>


=== Pascal/Delphi ===
== Pascal ==


<source lang="pascal">
<source lang="pascal">
function GCD(a, b: integer): integer;
function GCD(a, b: integer): integer;
begin
begin
if (a = 0) then
if a = 0 then
begin
GCD:= b
Result:= b;
else if b = 0 then
Exit;
GCD:= a
end else
else if a = b then
if (b = 0) then
GCD:= a
else if (a = 1) or (b =1) then
begin
Result:= a;
GCD:= 1
else if (a mod 2 = 0) and (b mod 2 = 0) then
Exit;
GCD:= 2*GCD(a div 2, b div 2)
end else
if (a = b) then
else if (a mod 2 = 0) and (b mod 2 <> 0) then
GCD:= GCD(a div 2, b)
begin
else if (a mod 2 <> 0) and (b mod 2 = 0) then
Result:= a;
Exit;
GCD:= GCD(a, b div 2)
end else
else
if (a = 1) or (b =1) then
GCD:= GCD(b, abs(a - b));
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;
end;
</source>
</source>


== Perl ==
[[Категория:Алгоритмы]]

<source lang="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;
}
</source>

== Scala ==
<!-- Добавил Рыжий Лис red-fox0@mail.ru -->
<source lang="scala">
def GCD(a:BigInt, b:BigInt):BigInt = {
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, (a-b).abs);
}
</source>

{{BookCat}}

Версия от 08:02, 6 июля 2014

С

 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

function GCD(a, b: integer): integer;
begin
   if a = 0 then
      GCD:= b
   else if b = 0 then
      GCD:= a
   else if a = b then
      GCD:= a
   else if (a = 1) or (b =1) then
      GCD:= 1
   else if (a mod 2 = 0) and (b mod 2 = 0) then
      GCD:= 2*GCD(a div 2, b div 2)
   else if (a mod 2 = 0) and (b mod 2 <> 0) then
      GCD:= GCD(a div 2, b)
   else if (a mod 2 <> 0) and (b mod 2 = 0) then
      GCD:= GCD(a, b div 2)
   else
      GCD:= 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;
}

Scala

  def GCD(a:BigInt, b:BigInt):BigInt = {
   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, (a-b).abs);
  }