Rosetta Code

Greatest common divisor: Difference between revisions

Page Discussion

Greatest common divisor (view source)

Revision as of 01:05, 22 December 2008

323 bytes added ,  15 years ago
added ruby
(+ Pascal)
(added ruby)
Line 3:
 
=={{header|Ada}}==
<ada>with Ada.Text_Io; use Ada.Text_Io;
 
procedure Gcd_Test is
function Gcd (A, B : Integer) return Integer is
begin
if A = 0 then
return B;
end if;
if B = 0 then
return A;
end if;
if A > B then
return Gcd(B, A mod B);
else
return Gcd(A, B mod A);
end if;
end Gcd;
begin
Put_Line("GCD of 100, 5 is" & Integer'Image(Gcd(100, 5)));
Put_Line("GCD of 5, 100 is" & Integer'Image(Gcd(5, 100)));
Put_Line("GCD of 7, 23 is" & Integer'Image(Gcd(7, 23)));
end Gcd_Test;</ada>
 
Output:
Line 70:
=={{header|C}}==
===Iterative Euclid algorithm===
<c>int
gcd_iter(int u, int v) {
int t;
while (v) {
t = u;
u = v;
v = t % v;
}
return u < 0 ? -u : u; /* abs(u) */
}</prec>▼
}
 
===Recursive Euclid algorithm===
<c>int
gcd(int u, int v) {
if (v)
return gcd(v, u % v);
else
return u < 0 ? -u : u; /* abs(u) */
}</c>
}
 
===Iterative binary algorithm===
<prec>int
int
gcd_bin(int u, int v) {
int t, k;
Line 125 ⟶ 124:
}
return u * k;
}</c>
}
▲</pre>
 
===Notes on performance===
Line 228 ⟶ 226:
=={{header|Java}}==
===Iterative===
<java>public static long gcd(long a, long b){
long factor= 0Math.max(a, b);
for(long loop= factor;loop > 1;loop--){
factor= Math.max(a, b);
for if(longa % loop == factor;loop0 >&& b % 1;loop-- == 0){
if(a % loop == 0 && b %return loop == 0){;
return loop;}
}
return }1;
}</java>
return 1;▼
}
 
===Recursive===
<java>public static long gcd(long a, long b){
if(a == 0) return b;
if(b == 0) return a;
if(a > b) return gcd(b, a % b);
return gcd(a, b % a);
}</java>
}
 
=={{header|Joy}}==
Line 310 ⟶ 307:
 
=={{header|OCaml}}==
<ocaml>let rec gcd a b =
if a = 0 then b
else if b = 0 then a
else if a > b then gcd b (a mod b)
else gcd a (b mod a)</ocaml>
 
=={{header|Pascal}}==
<pascal>function gcd(a, b: integer): integer;▼
<pascal>
▲function gcd(a, b: integer): integer;
var
tmp: integer;
Line 329 ⟶ 325:
end;
gcd := a
end;</pascal>
</pascal>
 
=={{header|Perl}}==
===Iterative Euclid algorithm===
<perl>sub gcd_iter($$) {
my ($u, $v) = @_;
while ($v) {
($u, $tv) = ($v, $u % $v);
}▼
$u = $v;▼
▲ return 1abs($u);
$v = $t % $v;
}</perl>
▲ }
return abs($u);
}
 
===Recursive Euclid algorithm===
<perl>sub gcd($$) {
my ($u, $v) = @_;
if ($v) {
return gcd($v, $u % $v);
} else {
return abs($u);
}
}</perl>
}
 
===Iterative binary algorithm===
<perl>sub gcd_bin($$) {
my ($u, $v) = @_;
$u = abs($u);
$v = abs($v);
if ($u < $v) {
($u, $tv) = ($v, $u);
}▼
$u = $v;
if ($v == $t;0) {
} return $u;
}▼
if ($v == 0) {
my $k = return $u1;
while ($u & while1 == 0 && ($tv & 1 == 0) {▼
▲ }
$ku >>= 1;
while ($u & 1v =>>= 0 && $v & 1 == 0) {;
$uk >><<= 1;
}
$v >>= 1;
my $t = ($ku <<=& 1) ? -$v : $u;
while }($t) {
$t =while ($ut & 1) ?== -$v0) : $u;{
while ( $t) {>>= 1;
}
▲ while ($t & 1 == 0) {
if ($t >>= 1;0) {
} $u = $t;
} if ($t > 0)else {
$uv = -$t;
} else {
$vt = $u - $tv;
}
$t =return $u -* $vk;
}</perl>
▲ }
return $u * $k;
}
 
===Notes on performance===
<perl>use Benchmark qw(cmpthese);
 
my $u = 40902;
my $v = 24140;
cmpthese(-5, {
'gcd' => sub { gcd($u, $v); },
'gcd_iter' => sub { gcd_iter($u, $v); },
'gcd_bin' => sub { gcd_bin($u, $v); },
});</perl>
 
Output on 'Intel(R) Pentium(R) 4 CPU 1.50GHz' / Linux / Perl 5.8.8:
Line 444 ⟶ 435:
=={{header|Python}}==
===Iterative Euclid algorithm===
<python>def gcd_iter(u, v):
while v:
u, v = v, u % v
return abs(u)</python>
 
===Recursive Euclid algorithm===
'''Interpreter:''' [[Python]] 2.5
<python>def gcd(u, v):
return gcd(v, u % v) if v else abs(u)</python>
 
===Tests===
Line 468 ⟶ 459:
===Iterative binary algorithm===
See [[The Art of Computer Programming]] by Knuth (Vol.2)
<python>def gcd_bin(u, v):
u, v = abs(u), abs(v) # u >= 0, v >= 0
if u < v:
u, v = v, u # u >= v >= 0
if v == 0:
return u
# u >= v > 0
k = 1
while u & 1 == 0 and v & 1 == 0: # u, v - even
u >>= 1; v >>= 1
k <<= 1
t = -v if u & 1 else u
while t:
while t & 1 == 0:
t >>= 1
if t > 0:
u = t
else:
v = -t
t = u - v
return u * k</python>
 
===Notes on performance===
Line 498 ⟶ 489:
 
<code>gcd_bin(40902, 24140)</code> takes us about '''41''' usec
 
=={{header|Ruby}}==
 
That is already available as the ''gcd'' method of integers:
irb(main):001:0> require 'rational'
=> true
irb(main):002:0> 40902.gcd(24140)
=> 34
 
Here's an implementation:
<ruby>def gcd(u, v)
u, v = u.abs, v.abs
while v > 0
▲ $u, v = $v;, u % v
end
v
end</ruby>
 
=={{header|SETL}}==
Line 521 ⟶ 529:
the gcd of 49865 and 69811 is 9973
=={{header|Scheme}}==
<scheme>(define (gcd a b)
(cond ((= a 0) b)
((= b 0) a)
((> a b) (gcd b (modulo a b)))
(else (gcd a (modulo b a)))))</scheme>
 
or using the standard function included with Scheme (takes any number of arguments):
<scheme>(gcd a b)</scheme>
 
=={{header|TI-83 BASIC}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/51397"