User talk:NevilleDNZ/GeSHi sandbox
You are encouraged to solve this task according to the task description, using any language you may know.
This task requires the finding of the greatest common divisor of two integers.
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:
GCD of 100, 5 is 5 GCD of 5, 100 is 5 GCD of 7, 23 is 1
ALGOL 68
<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)))
)
</algol-68> The output is:
The gcd of +33 and +77 is +11 The gcd of +49865 and +69811 is +9973
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) */
}
</c>
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
<c> 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;
} </c>
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
Forth
<forth>
: gcd ( a b -- n ) begin dup while tuck mod repeat drop ;
</forth>
Fortran
Iterative Euclid algorithm
<fortran>
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
</fortran>
Iterative binary algorithm
<fortran>
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
</fortran>
Notes on performance
gcd_iter(40902, 24140) takes us about 2.8 usec
gcd_bin(40902, 24140) takes us about 2.5 usec
J
<j>
x+.y
</j>
Java
Iterative
<java>
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;
}
</java>
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>
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>
Perl
Iterative Euclid algorithm
<perl>
sub gcd_iter($$) {
($u, $v) = @_;
while ($v) {
$t = $u;
$u = $v;
$v = $t % $v;
}
return abs($u);
}
</perl>
Recursive Euclid algorithm
<perl>
sub gcd($$) {
($u, $v) = @_;
if ($v) {
return gcd($v, $u % $v);
} else {
return abs($u);
}
}
</perl>
Iterative binary algorithm
<perl>
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;
}
</perl>
Notes on performance
<perl>
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); },
});
</perl> 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% --
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
>>> 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
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
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