Greatest common divisor: Difference between revisions
No edit summary |
|||
Line 3: | Line 3: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
<ada>with Ada.Text_Io; use Ada.Text_Io; |
<lang ada>with Ada.Text_Io; use Ada.Text_Io; |
||
procedure Gcd_Test is |
procedure Gcd_Test is |
||
Line 25: | Line 25: | ||
Put_Line("GCD of 5, 100 is" & Integer'Image(Gcd(5, 100))); |
Put_Line("GCD of 5, 100 is" & Integer'Image(Gcd(5, 100))); |
||
Put_Line("GCD of 7, 23 is" & Integer'Image(Gcd(7, 23))); |
Put_Line("GCD of 7, 23 is" & Integer'Image(Gcd(7, 23))); |
||
end Gcd_Test;</ |
end Gcd_Test;</lang> |
||
Output: |
Output: |
||
Line 70: | Line 70: | ||
=={{header|C}}== |
=={{header|C}}== |
||
===Iterative Euclid algorithm=== |
===Iterative Euclid algorithm=== |
||
<c>int |
<lang c>int |
||
gcd_iter(int u, int v) { |
gcd_iter(int u, int v) { |
||
int t; |
int t; |
||
Line 79: | Line 79: | ||
} |
} |
||
return u < 0 ? -u : u; /* abs(u) */ |
return u < 0 ? -u : u; /* abs(u) */ |
||
}</ |
}</lang> |
||
===Recursive Euclid algorithm=== |
===Recursive Euclid algorithm=== |
||
<c>int |
<lang c>int |
||
gcd(int u, int v) { |
gcd(int u, int v) { |
||
if (v) |
if (v) |
||
Line 88: | Line 88: | ||
else |
else |
||
return u < 0 ? -u : u; /* abs(u) */ |
return u < 0 ? -u : u; /* abs(u) */ |
||
}</ |
}</lang> |
||
===Iterative binary algorithm=== |
===Iterative binary algorithm=== |
||
<c>int |
<lang c>int |
||
gcd_bin(int u, int v) { |
gcd_bin(int u, int v) { |
||
int t, k; |
int t, k; |
||
Line 124: | Line 124: | ||
} |
} |
||
return u * k; |
return u * k; |
||
}</ |
}</lang> |
||
===Notes on performance=== |
===Notes on performance=== |
||
< |
<tt>gcd_iter(40902, 24140)</tt> takes us about '''2.87''' usec |
||
< |
<tt>gcd_bin(40902, 24140)</tt> takes us about '''2.47''' usec |
||
< |
<tt>gcd(40902, 24140)</tt> takes us about '''2.86''' usec |
||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
Line 207: | Line 207: | ||
===Notes on performance=== |
===Notes on performance=== |
||
< |
<tt>gcd_iter(40902, 24140)</tt> takes us about '''2.8''' usec |
||
< |
<tt>gcd_bin(40902, 24140)</tt> takes us about '''2.5''' usec |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Line 226: | Line 226: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
===Iterative=== |
===Iterative=== |
||
<java>public static long gcd(long a, long b){ |
<lang java>public static long gcd(long a, long b){ |
||
long factor= Math.max(a, b); |
long factor= Math.max(a, b); |
||
for(long loop= factor;loop > 1;loop--){ |
for(long loop= factor;loop > 1;loop--){ |
||
Line 234: | Line 234: | ||
} |
} |
||
return 1; |
return 1; |
||
}</ |
}</lang> |
||
===Recursive=== |
===Recursive=== |
||
<java>public static long gcd(long a, long b){ |
<lang java>public static long gcd(long a, long b){ |
||
if(a == 0) return b; |
if(a == 0) return b; |
||
if(b == 0) return a; |
if(b == 0) return a; |
||
if(a > b) return gcd(b, a % b); |
if(a > b) return gcd(b, a % b); |
||
return gcd(a, b % a); |
return gcd(a, b % a); |
||
}</ |
}</lang> |
||
=={{header|Joy}}== |
=={{header|Joy}}== |
||
Line 340: | Line 340: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
<ocaml>let rec gcd a b = |
<lang ocaml>let rec gcd a b = |
||
if a = 0 then b |
if a = 0 then b |
||
else if b = 0 then a |
else if b = 0 then a |
||
else if a > b then gcd b (a mod b) |
else if a > b then gcd b (a mod b) |
||
else gcd a (b mod a)</ |
else gcd a (b mod a)</lang> |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
<pascal>function gcd(a, b: integer): integer; |
<lang pascal>function gcd(a, b: integer): integer; |
||
var |
var |
||
tmp: integer; |
tmp: integer; |
||
Line 358: | Line 358: | ||
end; |
end; |
||
gcd := a |
gcd := a |
||
end;</ |
end;</lang> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
===Iterative Euclid algorithm=== |
===Iterative Euclid algorithm=== |
||
<perl>sub gcd_iter($$) { |
<lang perl>sub gcd_iter($$) { |
||
my ($u, $v) = @_; |
my ($u, $v) = @_; |
||
while ($v) { |
while ($v) { |
||
Line 368: | Line 368: | ||
} |
} |
||
return abs($u); |
return abs($u); |
||
}</ |
}</lang> |
||
===Recursive Euclid algorithm=== |
===Recursive Euclid algorithm=== |
||
<perl>sub gcd($$) { |
<lang perl>sub gcd($$) { |
||
my ($u, $v) = @_; |
my ($u, $v) = @_; |
||
if ($v) { |
if ($v) { |
||
Line 378: | Line 378: | ||
return abs($u); |
return abs($u); |
||
} |
} |
||
}</ |
}</lang> |
||
===Iterative binary algorithm=== |
===Iterative binary algorithm=== |
||
<perl>sub gcd_bin($$) { |
<lang perl>sub gcd_bin($$) { |
||
my ($u, $v) = @_; |
my ($u, $v) = @_; |
||
$u = abs($u); |
$u = abs($u); |
||
Line 410: | Line 410: | ||
} |
} |
||
return $u * $k; |
return $u * $k; |
||
}</ |
}</lang> |
||
===Notes on performance=== |
===Notes on performance=== |
||
<perl>use Benchmark qw(cmpthese); |
<lang perl>use Benchmark qw(cmpthese); |
||
my $u = 40902; |
my $u = 40902; |
||
Line 421: | Line 421: | ||
'gcd_iter' => sub { gcd_iter($u, $v); }, |
'gcd_iter' => sub { gcd_iter($u, $v); }, |
||
'gcd_bin' => sub { gcd_bin($u, $v); }, |
'gcd_bin' => sub { gcd_bin($u, $v); }, |
||
});</ |
});</lang> |
||
Output on 'Intel(R) Pentium(R) 4 CPU 1.50GHz' / Linux / Perl 5.8.8: |
Output on 'Intel(R) Pentium(R) 4 CPU 1.50GHz' / Linux / Perl 5.8.8: |
||
Line 468: | Line 468: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Iterative Euclid algorithm=== |
===Iterative Euclid algorithm=== |
||
<python>def gcd_iter(u, v): |
<lang python>def gcd_iter(u, v): |
||
while v: |
while v: |
||
u, v = v, u % v |
u, v = v, u % v |
||
return abs(u)</ |
return abs(u)</lang> |
||
===Recursive Euclid algorithm=== |
===Recursive Euclid algorithm=== |
||
'''Interpreter:''' [[Python]] 2.5 |
'''Interpreter:''' [[Python]] 2.5 |
||
<python>def gcd(u, v): |
<lang python>def gcd(u, v): |
||
return gcd(v, u % v) if v else abs(u)</ |
return gcd(v, u % v) if v else abs(u)</lang> |
||
===Tests=== |
===Tests=== |
||
Line 492: | Line 492: | ||
===Iterative binary algorithm=== |
===Iterative binary algorithm=== |
||
See [[The Art of Computer Programming]] by Knuth (Vol.2) |
See [[The Art of Computer Programming]] by Knuth (Vol.2) |
||
<python>def gcd_bin(u, v): |
<lang python>def gcd_bin(u, v): |
||
u, v = abs(u), abs(v) # u >= 0, v >= 0 |
u, v = abs(u), abs(v) # u >= 0, v >= 0 |
||
if u < v: |
if u < v: |
||
Line 514: | Line 514: | ||
v = -t |
v = -t |
||
t = u - v |
t = u - v |
||
return u * k</ |
return u * k</lang> |
||
===Notes on performance=== |
===Notes on performance=== |
||
< |
<tt>gcd(40902, 24140)</tt> takes us about '''17''' usec |
||
< |
<tt>gcd_iter(40902, 24140)</tt> takes us about '''11''' usec |
||
< |
<tt>gcd_bin(40902, 24140)</tt> takes us about '''41''' usec |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
Line 532: | Line 532: | ||
Here's an implementation: |
Here's an implementation: |
||
<ruby>def gcd(u, v) |
<lang ruby>def gcd(u, v) |
||
u, v = u.abs, v.abs |
u, v = u.abs, v.abs |
||
while v > 0 |
while v > 0 |
||
Line 538: | Line 538: | ||
end |
end |
||
u |
u |
||
end</ |
end</lang> |
||
=={{header|SETL}}== |
=={{header|SETL}}== |
||
Line 562: | Line 562: | ||
the gcd of 49865 and 69811 is 9973 |
the gcd of 49865 and 69811 is 9973 |
||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
<scheme>(define (gcd a b) |
<lang scheme>(define (gcd a b) |
||
(cond ((= a 0) b) |
(cond ((= a 0) b) |
||
((= b 0) a) |
((= b 0) a) |
||
((> a b) (gcd b (modulo a b))) |
((> a b) (gcd b (modulo a b))) |
||
(else (gcd a (modulo b a)))))</ |
(else (gcd a (modulo b a)))))</lang> |
||
or using the standard function included with Scheme (takes any number of arguments): |
or using the standard function included with Scheme (takes any number of arguments): |
||
<scheme>(gcd a b)</ |
<lang scheme>(gcd a b)</lang> |
||
=={{header|TI-83 BASIC}}== |
=={{header|TI-83 BASIC}}== |
Revision as of 15:35, 3 February 2009
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
<lang 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;</lang>
Output:
GCD of 100, 5 is 5 GCD of 5, 100 is 5 GCD of 7, 23 is 1
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
APL
33 49865 ∨ 77 69811 11 9973
If you're interested in how you'd write GCD in Dyalog, if Dyalog didn't have a primitive for it, (i.e. using other algorithms mentioned on this page: iterative, recursive, binary recursive), see different ways to write GCD in Dyalog.
⌈/(^/0=A∘.|X)/A←⍳⌊/X←49865 69811 9973
C
Iterative Euclid algorithm
<lang 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) */
}</lang>
Recursive Euclid algorithm
<lang c>int gcd(int u, int v) {
if (v) return gcd(v, u % v); else return u < 0 ? -u : u; /* abs(u) */
}</lang>
Iterative binary algorithm
<lang 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;
}</lang>
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
: gcd ( a b -- n ) begin dup while tuck mod repeat drop ;
Fortran
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
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
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
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)
J
x+.y
Java
Iterative
<lang java>public static long gcd(long a, long b){
long factor= Math.max(a, b); for(long loop= factor;loop > 1;loop--){ if(a % loop == 0 && b % loop == 0){ return loop; } } return 1;
}</lang>
Recursive
<lang 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);
}</lang>
Joy
gcd == [0 >] [dup rollup rem] while pop;
Logo
to gcd :a :b if :b = 0 [output :a] output gcd :b modulo :a :b end
Lucid
dataflow algorithm
gcd(n,m) where z = [% n, m %] fby if x > y then [% x - y, y %] else [% x, y - x%] fi; x = hd(z); y = hd(tl(z)); gcd(n, m) = (x asa x*y eq 0) fby eod; end
Mathematica
GCD[a, b]
MAXScript
Iterative Euclid algorithm
fn gcdIter a b = ( while b > 0 do ( c = mod a b a = b b = c ) abs a )
Recursive Euclid algorithm
fn gcdRec a b = ( if b > 0 then gcdRec b (mod a b) else abs a )
Modula-3
MODULE GCD EXPORTS Main; IMPORT IO, Fmt; PROCEDURE GCD(a, b: CARDINAL): CARDINAL = BEGIN IF a = 0 THEN RETURN b; ELSIF b = 0 THEN RETURN a; ELSIF a > b THEN RETURN GCD(b, a MOD b); ELSE RETURN GCD(a, b MOD a); END; END GCD; BEGIN IO.Put("GCD of 100, 5 is " & Fmt.Int(GCD(100, 5)) & "\n"); IO.Put("GCD of 5, 100 is " & Fmt.Int(GCD(5, 100)) & "\n"); IO.Put("GCD of 7, 23 is " & Fmt.Int(GCD(7, 23)) & "\n"); END GCD.
Output:
GCD of 100, 5 is 5 GCD of 5, 100 is 5 GCD of 7, 23 is 1
Nial
Nial provides gcd in the standard lib.
|loaddefs 'niallib/gcd.ndf' |gcd 6 4 =2
defining it for arrays
# red is the reduction operator for a sorted list # one is termination condition red is cull filter (0 unequal) link [mod [rest, first] , first] one is or [= [1 first, tally], > [2 first, first]] gcd is fork [one, first, gcd red] sort <=
Using it
|gcd 9 6 3 =3
OCaml
<lang 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)</lang>
Pascal
<lang pascal>function gcd(a, b: integer): integer;
var tmp: integer; begin while b <> 0 do begin tmp := a mod b; a := b; b := tmp end; gcd := a end;</lang>
Perl
Iterative Euclid algorithm
<lang perl>sub gcd_iter($$) {
my ($u, $v) = @_; while ($v) { ($u, $v) = ($v, $u % $v); } return abs($u);
}</lang>
Recursive Euclid algorithm
<lang perl>sub gcd($$) {
my ($u, $v) = @_; if ($v) { return gcd($v, $u % $v); } else { return abs($u); }
}</lang>
Iterative binary algorithm
<lang perl>sub gcd_bin($$) {
my ($u, $v) = @_; $u = abs($u); $v = abs($v); if ($u < $v) { ($u, $v) = ($v, $u); } if ($v == 0) { return $u; } my $k = 1; while ($u & 1 == 0 && $v & 1 == 0) { $u >>= 1; $v >>= 1; $k <<= 1; } my $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;
}</lang>
Notes on performance
<lang 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); },
});</lang>
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% --
Pop11
Built-in gcd
gcd_n(15, 12, 2) =>
Note: the last argument gives the number of other arguments (in this case 2).
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;
Prolog
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).
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).
Python
Iterative Euclid algorithm
<lang python>def gcd_iter(u, v):
while v: u, v = v, u % v return abs(u)</lang>
Recursive Euclid algorithm
Interpreter: Python 2.5 <lang python>def gcd(u, v):
return gcd(v, u % v) if v else abs(u)</lang>
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) <lang 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</lang>
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
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: <lang ruby>def gcd(u, v)
u, v = u.abs, v.abs while v > 0 u, v = v, u % v end u
end</lang>
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
Scheme
<lang 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)))))</lang>
or using the standard function included with Scheme (takes any number of arguments): <lang scheme>(gcd a b)</lang>
TI-83 BASIC
gcd(A,B)
V
like joy
iterative
[gcd [0 >] [dup rollup %] while pop ].
recursive
like python
[gcd [zero?] [pop] [swap [dup] dip swap %] tailrec].
same with view: (swap [dup] dip swap % is replaced with a destructuring view)
[gcd [zero?] [pop] [[a b : [b a b %]] view i] tailrec].
running it
|1071 1029 gcd =21