Greatest common divisor: Difference between revisions
Content added Content deleted
(→{{header|Fortran}}: added Fortran language) |
|||
Line 55: | Line 55: | ||
: gcd ( a b -- n ) |
: gcd ( a b -- n ) |
||
begin dup while tuck mod repeat drop ; |
begin dup while tuck mod repeat drop ; |
||
=={{header|Fortran}}== |
|||
===Iterative Euclid algorithm=== |
|||
subroutine gcd_iter(value, u, v) |
|||
Cf2py integer intent(out) :: value |
|||
integer value, u, v, t |
|||
intrinsic abs, mod |
|||
do while( v.NE.0 ) |
|||
t = u |
|||
u = v |
|||
v = mod(t, v) |
|||
enddo |
|||
value = abs(u) |
|||
end subroutine gcd_iter |
|||
===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 |
|||
===Notes on performance=== |
|||
<code>gcd_iter(40902, 24140)</code> takes us about '''2.8''' usec |
|||
<code>gcd_bin(40902, 24140)</code> takes us about '''2.5''' usec |
|||
=={{header|J}}== |
=={{header|J}}== |
Revision as of 01:23, 19 December 2007
Greatest common divisor
You are encouraged to solve this task according to the task description, using any language you may know.
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
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;
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
Forth
: gcd ( a b -- n ) begin dup while tuck mod repeat drop ;
Fortran
Iterative Euclid algorithm
subroutine gcd_iter(value, u, v) Cf2py integer intent(out) :: value integer value, u, v, t intrinsic abs, mod
do while( v.NE.0 ) t = u u = v v = mod(t, v) enddo value = abs(u) end subroutine gcd_iter
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
Notes on performance
gcd_iter(40902, 24140)
takes us about 2.8 usec
gcd_bin(40902, 24140)
takes us about 2.5 usec
J
x+.y
Java
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; }
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); }
Python
Iterative Euclid algorithm
def gcd_iter(u, v): while v: u, v = v, u % v return abs(u)
Recursive Euclid algorithm
Interpreter: Python 2.5
def gcd(u, v): return gcd(v, u % v) if v else abs(u)
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)
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
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