Greatest common divisor
This task requires the finding of the greatest common divisor of two integers.
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
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
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
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) */ }
Recursive Euclid algorithm
int gcd(int u, int v) { if (v) return gcd(v, u % v); else return u < 0 ? -u : u; /* abs(u) */ }
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; }
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
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); }
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
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) = hd(z) asa x*y eq 0; 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 )
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)
Perl
Iterative Euclid algorithm
sub gcd_iter($$) { ($u, $v) = @_; while ($v) { $t = $u; $u = $v; $v = $t % $v; } return abs($u); }
Recursive Euclid algorithm
sub gcd($$) { ($u, $v) = @_; if ($v) { return gcd($v, $u % $v); } else { return abs($u); } }
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; }
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% --
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
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
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
(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)
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