Greatest common divisor
From Rosetta Code
Programming Task
This is a programming task. It lays out a problem which Rosetta Code users are encouraged to solve, using languages they know.
This task requires the finding of the greatest common divisor of two integers.
Contents |
[edit] 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;
Output:
GCD of 100, 5 is 5 GCD of 5, 100 is 5 GCD of 7, 23 is 1
[edit] ALGOL 68
PROC gcd = (INT a, b) INT: (
IF a = 0 THEN
b
ELIF b = 0 THEN
a
ELIF a > b THEN
gcd(b, a MOD b)
ELSE
gcd(a, b MOD a)
FI
);
main : (
INT a = 33, b = 77;
printf(($x"The gcd of"g" and "g" is "gl$,a,b,gcd(a,b)));
INT c = 49865, d = 69811;
printf(($x"The gcd of"g" and "g" is "gl$,c,d,gcd(c,d)))
)
The output is:
The gcd of +33 and +77 is +11 The gcd of +49865 and +69811 is +9973
[edit] C
[edit] Iterative Euclid algorithm
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) */
}
[edit] Recursive Euclid algorithm
int
gcd(int u, int v) {
if (v)
return gcd(v, u % v);
else
return u < 0 ? -u : u; /* abs(u) */
}
[edit] Iterative binary algorithm
int
gcd_bin(int u, int v) {
int t, k;
u = u < 0 ? -u : u; /* abs(u) */
v = v < 0 ? -v : v;
if (u < v) {
t = u;
u = v;
v = t;
}
if (v == 0)
return u;
k = 1;
while (u & 1 == 0 && v & 1 == 0) { /* u, v - even */
u >>= 1; v >>= 1;
k <<= 1;
}
t = (u & 1) ? -v : u;
while (t) {
while (t & 1 == 0)
t >>= 1;
if (t > 0)
u = t;
else
v = -t;
t = u - v;
}
return u * k;
}
[edit] Notes on performance
gcd_iter(40902, 24140) takes us about 2.87 usec
gcd_bin(40902, 24140) takes us about 2.47 usec
gcd(40902, 24140) takes us about 2.86 usec
[edit] Forth
: gcd ( a b -- n ) begin dup while tuck mod repeat drop ;
[edit] Fortran
[edit] Recursive Euclid algorithm
In ISO Fortran 95 or later, use RECURSIVE function:
recursive function gcd_rec(u, v) result(gcd)
integer :: gcd
integer, intent(in) :: u, v
if (mod(u, v) /= 0) then
gcd = gcd_rec(v, mod(u, v))
else
gcd = v
end if
end function gcd_rec
[edit] Iterative Euclid algorithm
subroutine gcd_iter(value, u, v)
Cf2py integer, intent(out) :: value
integer value, u, v, t
intrinsic abs, mod
C
do while( v.NE.0 )
t = u
u = v
v = mod(t, v)
enddo
value = abs(u)
end subroutine gcd_iter
[edit] Iterative binary algorithm
subroutine gcd_bin(value, u, v)
Cf2py integer, intent(out) :: value
integer value, u, v, k, t, abs, mod
intrinsic abs, mod
u = abs(u)
v = abs(v)
if( u.lt.v ) then
t = u
u = v
v = t
endif
if( v.eq.0 ) then
value = u
return
endif
k = 1
do while( (mod(u, 2).eq.0).and.(mod(v, 2).eq.0) )
u = u / 2
v = v / 2
k = k * 2
enddo
if( (mod(u, 2).eq.0) ) then
t = u
else
t = -v
endif
do while( t.ne.0 )
do while( (mod(t, 2).eq.0) )
t = t / 2
enddo
if( t.gt.0 ) then
u = t
else
v = -t
endif
t = u - v
enddo
value = u * k
end subroutine gcd_bin
[edit] Notes on performance
gcd_iter(40902, 24140) takes us about 2.8 usec
gcd_bin(40902, 24140) takes us about 2.5 usec
[edit] Haskell
That is already available as the function gcd in the Prelude. Here's the implementation:
gcd :: (Integral a) => a -> a -> a gcd 0 0 = error "Prelude.gcd: gcd 0 0 is undefined" gcd x y = gcd' (abs x) (abs y) where gcd' a 0 = a gcd' a b = gcd' b (a `rem` b)
[edit] J
x+.y
[edit] Java
[edit] Iterative
public static long gcd(long a, long b){
long factor= 0;
factor= Math.max(a, b);
for(long loop= factor;loop > 1;loop--){
if(a % loop == 0 && b % loop == 0){
return loop;
}
}
return 1;
}
[edit] Recursive
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);
}
[edit] Logo
to gcd :a :b if :b = 0 [output :a] output gcd :b modulo :a :b end
[edit] Mathematica
GCD[a, b]
[edit] MAXScript
[edit] Iterative Euclid algorithm
fn gcdIter a b =
(
while b > 0 do
(
c = mod a b
a = b
b = c
)
abs a
)
[edit] Recursive Euclid algorithm
fn gcdRec a b =
(
if b > 0 then gcdRec b (mod a b) else abs a
)
[edit] 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)
[edit] Perl
[edit] Iterative Euclid algorithm
sub gcd_iter($$) {
($u, $v) = @_;
while ($v) {
$t = $u;
$u = $v;
$v = $t % $v;
}
return abs($u);
}
[edit] Recursive Euclid algorithm
sub gcd($$) {
($u, $v) = @_;
if ($v) {
return gcd($v, $u % $v);
} else {
return abs($u);
}
}
[edit] Iterative binary algorithm
sub gcd_bin($$) {
($u, $v) = @_;
$u = abs($u);
$v = abs($v);
if ($u < $v) {
$t = $u;
$u = $v;
$v = $t;
}
if ($v == 0) {
return $u;
}
$k = 1;
while ($u & 1 == 0 && $v & 1 == 0) {
$u >>= 1;
$v >>= 1;
$k <<= 1;
}
$t = ($u & 1) ? -$v : $u;
while ($t) {
while ($t & 1 == 0) {
$t >>= 1;
}
if ($t > 0) {
$u = $t;
} else {
$v = -$t;
}
$t = $u - $v;
}
return $u * $k;
}
[edit] Notes on performance
use Benchmark qw(cmpthese);
$u = 40902;
$v = 24140;
(-5, {
'gcd' => sub { gcd($u, $v); },
'gcd_iter' => sub { gcd_iter($u, $v); },
'gcd_bin' => sub { gcd_bin($u, $v); },
});
Output on 'Intel(R) Pentium(R) 4 CPU 1.50GHz' / Linux / Perl 5.8.8:
Rate gcd_bin gcd_iter gcd
gcd_bin 321639/s -- -12% -20%
gcd_iter 366890/s 14% -- -9%
gcd 401149/s 25% 9% --
[edit] Pop11
[edit] Built-in gcd
gcd_n(15, 12, 2) =>
Note: the last argument gives the number of other arguments (in this case 2).
[edit] Iterative Euclid algorithm
define gcd(k, l) -> r;
lvars k , l, r = l;
abs(k) -> k;
abs(l) -> l;
if k < l then (k, l) -> (l, k) endif;
while l /= 0 do
(l, k rem l) -> (k, l)
endwhile;
k -> r;
enddefine;
[edit] Prolog
[edit] Recursive Euclid Algorithm
gcd(X, 0, X). gcd(0, X, X). gcd(X, X, X). gcd(X, Y, D) :- X > Y, Z is X mod Y, gcd(Y, Z, D). gcd(X, Y, D) :- X < Y, Z is Y mod X, gcd(X, Z, D).
[edit] Repeated Subtraction
gcd(X, X, X). gcd(X, Y, D) :- X < Y, Z is Y - X, gcd(X, Z, D). gcd(X, Y, D) :- Y < X, gcd(Y, X, D).
[edit] Python
[edit] Iterative Euclid algorithm
def gcd_iter(u, v):
while v:
u, v = v, u % v
return abs(u)
[edit] Recursive Euclid algorithm
Interpreter: Python 2.5
def gcd(u, v):
return gcd(v, u % v) if v else abs(u)
[edit] Tests
>>> gcd(0,0) 0 >>> gcd(0, 10) == gcd(10, 0) == gcd(-10, 0) == gcd(0, -10) == 10 True >>> gcd(9, 6) == gcd(6, 9) == gcd(-6, 9) == gcd(9, -6) == gcd(6, -9) == gcd(-9, 6) == 3 True >>> gcd(8, 45) == gcd(45, 8) == gcd(-45, 8) == gcd(8, -45) == gcd(-8, 45) == gcd(45, -8) == 1 True >>> gcd(40902, 24140) # check Knuth :) 34
[edit] Iterative binary algorithm
See The Art of Computer Programming by Knuth (Vol.2)
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
[edit] Notes on performance
gcd(40902, 24140) takes us about 17 usec
gcd_iter(40902, 24140) takes us about 11 usec
gcd_bin(40902, 24140) takes us about 41 usec
[edit] SETL
a := 33; b := 77;
print(" the gcd of",a," and ",b," is ",gcd(a,b));
c := 49865; d := 69811;
print(" the gcd of",c," and ",d," is ",gcd(c,d));
procedure gcd(a, b);
return if a = 0 then
b
elseif b = 0 then
a
elseif a > b then
gcd(b, a mod b)
else
gcd(a, b mod a)
end if;
end gcd;
Output:
the gcd of 33 and 77 is 11 the gcd of 49865 and 69811 is 9973
[edit] 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)))))
or using the standard function included with Scheme (takes any number of arguments):
(gcd a b)
[edit] TI-83 BASIC
gcd(A,B)
Categories: Programming Tasks | Arithmetic operations | Recursion | Ada | ALGOL 68 | C | Forth | Fortran | Haskell | J | Java | Logo | Mathematica | MAXScript | OCaml | Perl | Pop11 | Prolog | Python | SETL | Scheme | TI-83 BASIC
