Реализации алгоритмов/Бинарный алгоритм вычисления НОД: различия между версиями
Содержимое удалено Содержимое добавлено
Отмена правок до редакции 51022. |
Реализации на Pascal, Perl, Scala перенесены из ../Алгоритм Евклида. |
||
Строка 1: | Строка 1: | ||
⚫ | |||
{{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# == |
|||
<source lang="csharp"> |
<source lang="csharp"> |
||
Строка 61: | Строка 59: | ||
</source> |
</source> |
||
== Pascal == |
|||
<source lang="pascal"> |
<source lang="pascal"> |
||
function GCD(a, b: integer): integer; |
function GCD(a, b: integer): integer; |
||
begin |
begin |
||
if |
if a = 0 then |
||
GCD:= b |
|||
else if b = 0 then |
|||
GCD:= a |
|||
else if a = b then |
|||
GCD:= a |
|||
⚫ | |||
begin |
|||
GCD:= 1 |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
if (a = b) then |
else if (a mod 2 = 0) and (b mod 2 <> 0) then |
||
⚫ | |||
begin |
|||
⚫ | |||
⚫ | |||
GCD:= GCD(a, b div 2) |
|||
else |
|||
GCD:= GCD(b, abs(a - b)); |
|||
begin |
|||
Result:= 1; |
|||
⚫ | |||
end else |
|||
⚫ | |||
begin |
|||
⚫ | |||
Exit; |
|||
end else |
|||
⚫ | |||
begin |
|||
⚫ | |||
Exit; |
|||
end else |
|||
⚫ | |||
begin |
|||
Result:= GCD(a, Trunc(b/2)); |
|||
Exit; |
|||
end; |
|||
⚫ | |||
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) |
|||
⚫ | |||
$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;} |
|||
⚫ | |||
⚫ | |||
$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); |
|||
⚫ | |||
} |
|||
</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);
}