Greatest common divisor
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.
ActionScript
<lang ActionScript>//Euclidean algorithm function gcd(a:int,b:int):int { var tmp:int; //Swap the numbers so a >= b if(a < b) { tmp = a; a = b; b = tmp; } //Find the gcd while(b != 0) { tmp = a % b; a = b; b = tmp; } return a; }</lang>
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
<lang algol68>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)))
)</lang> The output is: <lang algol68>The gcd of +33 and +77 is +11 The gcd of +49865 and +69811 is +9973</lang>
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
AWK
The following scriptlet defines the gcd() function, then reads pairs of numbers from stdin, and reports their gcd on stdout. <lang awk>$ awk 'func gcd(p,q){return(q?gcd(q,(p%q)):p)}{print gcd($1,$2)}' 12 16 4 22 33 11 45 67 1</lang>
AutoHotkey
contributed by Laszlo on the ahk forum <lang AutoHotkey>GCD(a,b) {
Return b=0 ? Abs(a) : Gcd(b,mod(a,b))
}</lang>
Batch File
Recursive method <lang dos>:: gcd.cmd @echo off
- gcd
if "%2" equ "" goto :instructions if "%1" equ "" goto :instructions
if %2 equ 0 ( set final=%1 goto :done ) set /a res = %1 %% %2 call :gcd %2 %res% goto :eof
- done
echo gcd=%final% goto :eof
- instructions
echo Syntax: echo GCD {a} {b} echo.</lang>
BASIC
Iterative
<lang qbasic>function gcd(a%, b%)
if a > b then factor = a else factor = b end if for l = factor to 1 step -1 if a mod l = 0 and b mod l = 0 then gcd = l end if next l gcd = 1
end function</lang>
Recursive
<lang qbasic>function gcd(a%, b%)
if a = 0 gcd = b if b = 0 gcd = a if a > b gcd = gcd(b, a mod b) gcd = gcd(a, b mod a)
end function</lang>
Bc
Utility functions: <lang bc>define even(a) {
if ( a % 2 == 0 ) { return(1); } else { return(0); }
}
define abs(a) {
if (a<0) { return(-a); } else { return(a); }
}</lang>
Iterative (Euclid) <lang bc>define gcd_iter(u, v) {
while(v) { t = u; u = v; v = t % v; } return(abs(u));
}</lang>
Recursive
<lang bc>define gcd(u, v) {
if (v) { return ( gcd(v, u%v) ); } else { return (abs(u)); }
}</lang>
Iterative (Binary)
<lang bc>define 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 (even(u) && even(v)) { u = u / 2; v = v / 2; k = k * 2; } if ( even(u) ) { t = -v; } else { t = u; } while (t) { while (even(t)) { t = t / 2; } if (t > 0) { u = t; } else { v = -t; } t = u - v; } return (u * k);
}</lang>
Befunge
<lang befunge>#v&< @.$<
- <\g05%p05:_^#</lang>
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 µsec
gcd_bin(40902, 24140) takes us about 2.47 µsec
gcd(40902, 24140) takes us about 2.86 µsec
Clojure
<lang lisp>(defn gcd
"(gcd a b) computes the greatest common divisor of a and b." [a b] (if (zero? b) a (recur b (mod a b)))) ; This is (gcd b (mod a b)), but with explicit tail call optimization.</lang>
C#
This is an Euclidean algorithm, translated from ActionScript. <lang csharp> static void Main(string[] args) { Console.WriteLine("GCD of {0} and {1} is {2}", 1, 1, gcd(1, 1)); Console.WriteLine("GCD of {0} and {1} is {2}", 1, 10, gcd(1, 10)); Console.WriteLine("GCD of {0} and {1} is {2}", 10, 100, gcd(10, 100)); Console.WriteLine("GCD of {0} and {1} is {2}", 5, 50, gcd(5, 50)); Console.WriteLine("GCD of {0} and {1} is {2}", 8, 24, gcd(8, 24)); Console.WriteLine("GCD of {0} and {1} is {2}", 36, 17, gcd(36, 17)); Console.WriteLine("GCD of {0} and {1} is {2}", 36, 18, gcd(36, 18)); Console.WriteLine("GCD of {0} and {1} is {2}", 36, 19, gcd(36, 19)); for (int x = 1; x < 36; x++) { Console.WriteLine("GCD of {0} and {1} is {2}", 36, x, gcd(36, x)); } Console.Read(); }
private static int gcd(int a, int b) { int t;
// Ensure B > A if (a > b) { t = b; b = a; a = t; }
// Find while (b != 0) { t = a % b; a = b; b = t; }
return a; } </lang>
Example output:
GCD of 1 and 1 is 1 GCD of 1 and 10 is 1 GCD of 10 and 100 is 10 GCD of 5 and 50 is 5 GCD of 8 and 24 is 8 GCD of 36 and 1 is 1 GCD of 36 and 2 is 2 .. GCD of 36 and 16 is 4 GCD of 36 and 17 is 1 GCD of 36 and 18 is 18 .. .. GCD of 36 and 33 is 3 GCD of 36 and 34 is 2 GCD of 36 and 35 is 1
Common Lisp
We call the function gcd2
so as not to conflict with common-lisp:gcd
.
<lang lisp>(defun gcd2 (a b)
(do ((n a)) ((zerop b) (abs a)) (shiftf n a b (mod n b))))</lang>
D
<lang d>bool isEven(int number) {
return number%2 == 0;
}
int gcd(int a, int b) {
if(a == 0) return b; else if(b == 0) return a; else if(isEven(a) && isEven(b)) return gcd(a>>1, b>>1) << 1; else if(isEven(a) && !isEven(b)) return gcd(a>>1, b); else if(!isEven(a) && isEven(b)) return gcd(a, b>>1); else if(a >= b) return gcd(a-b, b); return gcd(a, b-a);
}</lang>
E
<lang e>def gcd(var u :int, var v :int) {
while (v != 0) { def r := u %% v u := v v := r } return u.abs()
}</lang>
Emacs Lisp
<lang lisp> (defun pgdc (a b)
(cond ((< a b) (pgdc a (- b a))) ((> a b) (pgdc (- a b) b)) (t a)))
</lang>
Erlang
<lang erlang>gcd(0,B) -> abs(B); gcd(A,0) -> abs(A); gcd(A,B) when A > B -> gcd(B, A rem B); gcd(A,B) -> gcd(A, B rem A).</lang>
F#
<lang fsharp>Open System
let rec GCD (a:int) (b:int) =
match b with | 0 -> Math.Abs(a) | _ -> GCD b (a % b)</lang>
Factor
<lang factor>: gcd ( a b -- c )
[ abs ] [ [ nip ] [ mod ] 2bi gcd ] if-zero ;</lang>
FALSE
<lang false>[[$][$@$@$@\/*-]#%]g: 10 15 g;!. { 5 }</lang>
Forth
<lang forth>: gcd ( a b -- n )
begin dup while tuck mod repeat drop ;</lang>
Fortran
Recursive Euclid algorithm
<lang fortran>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</lang>
Iterative Euclid algorithm
<lang fortran>subroutine gcd_iter(value, u, v)
integer, intent(out) :: value integer, intent(inout) :: u, v integer :: t
do while( v /= 0 ) t = u u = v v = mod(t, v) enddo value = abs(u)
end subroutine gcd_iter</lang>
A different version, and implemented as function
<lang fortran>function gcd(v, t)
integer :: gcd integer, intent(in) :: v, t integer :: c, b, a
b = t a = v do c = mod(a, b) if ( c == 0) exit a = b b = c end do gcd = b ! abs(b)
end function gcd</lang>
Iterative binary algorithm
<lang fortran>subroutine gcd_bin(value, u, v)
integer, intent(out) :: value integer, intent(inout) :: u, v integer :: k, t
u = abs(u) v = abs(v) if( u < v ) then t = u u = v v = t endif if( v == 0 ) then value = u return endif k = 1 do while( (mod(u, 2) == 0).and.(mod(v, 2) == 0) ) u = u / 2 v = v / 2 k = k * 2 enddo if( (mod(u, 2) == 0) ) then t = u else t = -v endif do while( t /= 0 ) do while( (mod(t, 2) == 0) ) t = t / 2 enddo if( t > 0 ) then u = t else v = -t endif t = u - v enddo value = u * k
end subroutine gcd_bin</lang>
Notes on performance
gcd_iter(40902, 24140) takes us about 2.8 µsec
gcd_bin(40902, 24140) takes us about 2.5 µsec
Genyris
Recursive
<lang genyris>def gcd (u v)
u = (abs u) v = (abs v) cond (equal? v 0) u else (gcd v (% u v))</lang>
Iterative
<lang genyris>def gcd (u v)
u = (abs u) v = (abs v) while (not (equal? v 0)) var tmp (% u v) u = v v = tmp u</lang>
gnuplot
<lang gnuplot>gcd (a, b) = b == 0 ? a : gcd (b, a % b)</lang> Example: <lang gnuplot>print gcd (111111, 1111)</lang> Output: <lang>11</lang>
Groovy
Recursive
<lang groovy>def gcdR gcdR = { m, n -> m = m.abs(); n = n.abs(); n == 0 ? m : m%n == 0 ? n : gcdR(n, m%n) }</lang>
Iterative
<lang groovy>def gcdI = { m, n -> m = m.abs(); n = n.abs(); n == 0 ? m : { while(m%n != 0) { t=n; n=m%n; m=t }; n }() }</lang>
Test program: <lang groovy>println " R I" println "gcd(28, 0) = ${gcdR(28, 0)} == ${gcdI(28, 0)}" println "gcd(0, 28) = ${gcdR(0, 28)} == ${gcdI(0, 28)}" println "gcd(0, -28) = ${gcdR(0, -28)} == ${gcdI(0, -28)}" println "gcd(70, -28) = ${gcdR(70, -28)} == ${gcdI(70, -28)}" println "gcd(70, 28) = ${gcdR(70, 28)} == ${gcdI(70, 28)}" println "gcd(28, 70) = ${gcdR(28, 70)} == ${gcdI(28, 70)}" println "gcd(800, 70) = ${gcdR(800, 70)} == ${gcdI(800, 70)}" println "gcd(27, -70) = ${gcdR(27, -70)} == ${gcdI(27, -70)}"</lang>
Output:
R I gcd(28, 0) = 28 == 28 gcd(0, 28) = 28 == 28 gcd(0, -28) = 28 == 28 gcd(70, -28) = 14 == 14 gcd(70, 28) = 14 == 14 gcd(28, 70) = 14 == 14 gcd(800, 70) = 10 == 10 gcd(27, -70) = 1 == 1
Haskell
That is already available as the function gcd in the Prelude. Here's the implementation:
<lang haskell>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)</lang>
HicEst
<lang hicest>FUNCTION gcd(a, b)
IF(b == 0) THEN gcd = ABS(a) ELSE aa = a gcd = b DO i = 1, 1E100 r = ABS(MOD(aa, gcd)) IF( r == 0 ) RETURN aa = gcd gcd = r ENDDO ENDIF END</lang>
Icon and Unicon
Icon
<lang Icon>link numbers # gcd is part of the Icon Programming Library procedure main(args)
write(gcd(arg[1], arg[2])) | "Usage: gcd n m")
end</lang>
numbers implements this as:
<lang Icon>procedure gcd(i,j) #: greatest common divisor
local r
if (i | j) < 1 then runerr(501)
repeat { r := i % j if r = 0 then return j i := j j := r }
end</lang>
Unicon
This Icon solution works in Unicon.
J
<lang J>x+.y</lang>
For example:
<lang J> 12 +. 30 6</lang>
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>
JavaScript
Iterative. <lang javascript>function gcd(a,b) {
if (a < 0) a = -a; if (b < 0) b = -b; if (b > a) {var temp = a; a = b; b = temp;} while (true) { a %= b; if (a == 0) return b; b %= a; if (b == 0) return a; }
}</lang>
Recursive. <lang javascript>function gcd_rec(a, b) {
if (b) { return gcd_rec(b, a % b); } else { return Math.abs(a); }
}</lang>
Joy
<lang joy>DEFINE gcd == [0 >] [dup rollup rem] while pop.</lang>
Logo
<lang logo>to gcd :a :b
if :b = 0 [output :a] output gcd :b modulo :a :b
end</lang>
Lua
<lang lua>function gcd(a,b) if b ~= 0 then return gcd(b, a % b) else return math.abs(a) end end
function demo(a,b) print("GCD of " .. a .. " and " .. b .. " is " .. gcd(a, b)) end
demo(100, 5) demo(5, 100) demo(7, 23)</lang>
Output:
GCD of 100 and 5 is 5 GCD of 5 and 100 is 5 GCD of 7 and 23 is 1
Lucid
dataflow algorithm
<lang 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) = (x asa x*y eq 0) fby eod;
end</lang>
Mathematica
<lang mathematica>GCD[a, b]</lang>
MATLAB
<lang Matlab>function [gcdValue] = greatestcommondivisor(integer1, integer2)
gcdValue = gcd(integer1, integer2);</lang>
MAXScript
Iterative Euclid algorithm
<lang maxscript>fn gcdIter a b = (
while b > 0 do ( c = mod a b a = b b = c ) abs a
)</lang>
Recursive Euclid algorithm
<lang maxscript>fn gcdRec a b = (
if b > 0 then gcdRec b (mod a b) else abs a
)</lang>
Modula-3
<lang modula3>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.</lang>
Output:
GCD of 100, 5 is 5 GCD of 5, 100 is 5 GCD of 7, 23 is 1
MUMPS
<lang MUMPS> GCD(A,B)
QUIT:((A/1)'=(A\1))!((B/1)'=(B\1)) 0 SET:A<0 A=-A SET:B<0 B=-B IF B'=0 FOR SET T=A#B,A=B,B=T QUIT:B=0 ;ARGUEMENTLESS FOR NEEDS TWO SPACES QUIT A</lang>
Ouput:
CACHE>S X=$$GCD^ROSETTA(12,24) W X 12 CACHE>S X=$$GCD^ROSETTA(24,-112) W X 8 CACHE>S X=$$GCD^ROSETTA(24,-112.2) W X 0
Nial
Nial provides gcd in the standard lib. <lang nial>|loaddefs 'niallib/gcd.ndf' |gcd 6 4 =2</lang>
defining it for arrays <lang nial># 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 <=</lang>
Using it <lang nial>|gcd 9 6 3 =3</lang>
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>
Octave
<lang octave>r = gcd(a, b)</lang>
Oz
<lang oz>declare
fun {UnsafeGCD A B} if B == 0 then A else {UnsafeGCD B A mod B} end end
fun {GCD A B} if A == 0 andthen B == 0 then raise undefined(gcd 0 0) end else {UnsafeGCD {Abs A} {Abs B}} end end
in
{Show {GCD 456 ~632}}</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% --
Perl 6
Iterative
<lang perl6>sub gcd (Int $a is copy, Int $b is copy) {
$a & $b == 0 and fail; ($a, $b) = ($b, $a % $b) while $b; return abs $a;
}</lang>
Recursive
<lang perl6>multi gcd (0, 0) { fail } multi gcd (Int $a, 0) { abs $a } multi gcd (Int $a, Int $b) { gcd $b, $a % $b }</lang>
PicoLisp
<lang PicoLisp>(de gcd (A B)
(until (=0 B) (let M (% A B) (setq A B B M) ) ) (abs A) )</lang>
PHP
Iterative
<lang php> function gcdIter($n, $m) {
while(true) { if($n == $m) { return $m; } if($n > $m) { $n -= $m; } else { $m -= $n; } }
} </lang>
Recursive
<lang php> function gcdRec($n, $m) {
if($m > 0) { return gcdRec($m, $n % $m); } else { return abs($n); }
} </lang>
PL/I
<lang PL/I> GCD: procedure (a, b) returns (fixed binary (31)) recursive;
declare (a, b) fixed binary (31);
if b = 0 then return (a);
return (GCD (b, mod(a, b)) );
end GCD; </lang>
Pop11
Built-in gcd
<lang pop11>gcd_n(15, 12, 2) =></lang>
Note: the last argument gives the number of other arguments (in this case 2).
Iterative Euclid algorithm
<lang pop11>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;</lang>
PowerShell
Recursive Euclid Algorithm
<lang powershell>function get-gcd ($x, $y) {
if($x-eq$y){ return $y } if($x-gt$y){ $a=$x $b=$y } else { $a=$y $b=$x } while (($a%$b)-ne0){ $tmp=$a%$b $a=$b $b=$tmp } return $b
}</lang>
Prolog
Recursive Euclid Algorithm
<lang prolog>gcd(X, 0, X):- !. gcd(0, X, X):- !. gcd(X, Y, D):- X > Y, !, Z is X mod Y, gcd(Y, Z, D). gcd(X, Y, D):- Z is Y mod X, gcd(X, Z, D).</lang>
Repeated Subtraction
<lang prolog>gcd(X, 0, X):- !. gcd(0, X, X):- !. gcd(X, Y, D):- X =< Y, !, Z is Y - X, gcd(X, Z, D). gcd(X, Y, D):- gcd(Y, X, D).</lang>
PureBasic
Iterative <lang PureBasic>Procedure GCD(x, y)
Protected r While y <> 0 r = x % y x = y y = r Wend ProcedureReturn y
EndProcedure</lang>
Recursive <lang PureBasic>Procedure GCD(x, y)
Protected r r = x % y If (r > 0) y = GCD(y, r) EndIf ProcedureReturn y
EndProcedure</lang>
Python
Built-in
<lang python>from fractions import gcd</lang>
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 µsec (Euclid, not built-in)
gcd_iter(40902, 24140) takes us about 11 µsec
gcd_bin(40902, 24140) takes us about 41 µsec
R
<lang R>"%gcd%" <- function(u, v) {
ifelse(u %% v != 0, v %gcd% (u%%v), v)
}</lang>
<lang R>"%gcd%" <- function(v, t) {
while ( (c <- v%%t) != 0 ) { v <- t t <- c }
}</lang>
<lang R>print(50 %gcd% 75)</lang>
REBOL
<lang rebol> gcd: func [
{Returns the greatest common denominator of m and n.} m [integer!] n [integer!]
][
;Euclid's algorithm abs either zero? n [0] [either zero? (m // n) [n] [gcd n (m // n)]]
] </lang>
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>
Sather
<lang sather>class MATH is
gcd_iter(u, v:INT):INT is loop while!( v.bool ); t ::= u; u := v; v := t % v; end; return u.abs; end;
gcd(u, v:INT):INT is if v.bool then return gcd(v, u%v); end; return u.abs; end;
private swap(inout a, inout b:INT) is t ::= a; a := b; b := t; end;
gcd_bin(u, v:INT):INT is t:INT;
u := u.abs; v := v.abs; if u < v then swap(inout u, inout v); end; if v = 0 then return u; end; k ::= 1; loop while!( u.is_even and v.is_even ); u := u / 2; v := v / 2; k := k * 2; end; if u.is_even then t := -v; else t := u; end; loop while!( t.bool ); loop while!( t.is_even ); t := t / 2; end; if t > 0 then u := t; else v := -t; end; t := u - v; end; return u * k; end;
end;</lang>
<lang sather>class MAIN is
main is a ::= 40902; b ::= 24140; #OUT + MATH::gcd_iter(a, b) + "\n"; #OUT + MATH::gcd(a, b) + "\n"; #OUT + MATH::gcd_bin(a, b) + "\n"; -- built in #OUT + a.gcd(b) + "\n"; end;
end;</lang>
Scala
<lang scala>def gcd(a: Int, b: Int): Int = if (b == 0) a.abs else gcd(b, a % b)</lang>
Scheme
<lang scheme>(define (gcd a b)
(if (= b 0) a (gcd b (modulo a b))))</lang>
or using the standard function included with Scheme (takes any number of arguments): <lang scheme>(gcd a b)</lang>
Seed7
<lang seed7>const func integer: gcd (in var integer: a, in var integer: b) is func
result var integer: result is 0; local var integer: help is 0; begin while a <> 0 do help := b rem a; b := a; a := help; end while; result := b; end func;</lang>
Original source: [1]
SETL
<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));
proc gcd (u, v);
return if v = 0 then abs u else gcd (v, u mod v) end;
end;</lang>
Output: <lang setl>the gcd of 33 and 77 is 11 the gcd of 49865 and 69811 is 9973</lang>
Slate
Slate's Integer type has gcd defined:
<lang slate>40902 gcd: 24140</lang>
Iterative Euclid algorithm
<lang slate>x@(Integer traits) gcd: y@(Integer traits) "Euclid's algorithm for finding the greatest common divisor." [| n m temp |
n: x. m: y. [n isZero] whileFalse: [temp: n. n: m \\ temp. m: temp]. m abs
].</lang>
Recursive Euclid algorithm
<lang slate>x@(Integer traits) gcd: y@(Integer traits) [
y isZero ifTrue: [x] ifFalse: [y gcd: x \\ y]
].</lang>
Smalltalk
The Integer class has its gcd method.
<lang smalltalk>(40902 gcd: 24140) displayNl</lang>
An implementation of the Iterative Euclid's algorithm
<lang smalltalk>|gcd_iter|
gcd_iter := [ :a :b | |u v| u := a. v := b.
[ v > 0 ] whileTrue: [ |t| t := u copy. u := v copy. v := t rem: v ]. u abs
].
(gcd_iter value: 40902 value: 24140)
printNl.</lang>
SNOBOL4
<lang snobol> define('gcd(i,j)') :(gcd_end) gcd ?eq(i,0) :s(freturn) ?eq(j,0) :s(freturn)
loop gcd = remdr(i,j) gcd = ?eq(gcd,0) j :s(return) i = j j = gcd :(loop) gcd_end
output = gcd(1071,1029) end</lang>
Standard ML
<lang sml>fun gcd a 0 = a
| gcd a b = gcd b (a mod b)</lang>
Tcl
Iterative Euclid algorithm
<lang tcl>package require Tcl 8.5 namespace path {::tcl::mathop ::tcl::mathfunc} proc gcd_iter {p q} {
while {$q != 0} { lassign [list $q [% $p $q]] p q } abs $p
}</lang>
Recursive Euclid algorithm
<lang tcl>proc gcd {p q} {
if {$q == 0} { return $p } gcd $q [expr {$p % $q}]
}</lang> With Tcl 8.6, this can be optimized slightly to: <lang tcl>proc gcd {p q} {
if {$q == 0} { return $p } tailcall gcd $q [expr {$p % $q}]
}</lang> (Tcl does not perform automatic tail-call optimization introduction because that makes any potential error traces less informative.)
Iterative binary algorithm
<lang tcl>package require Tcl 8.5 namespace path {::tcl::mathop ::tcl::mathfunc} proc gcd_bin {p q} {
if {$p == $q} {return [abs $p]} set p [abs $p] if {$q == 0} {return $p} set q [abs $q] if {$p < $q} {lassign [list $q $p] p q} set k 1 while {($p & 1) == 0 && ($q & 1) == 0} { set p [>> $p 1] set q [>> $q 1] set k [<< $k 1] } set t [expr {$p & 1 ? -$q : $p}] while {$t} { while {$t & 1 == 0} {set t [>> $t 1]} if {$t > 0} {set p $t} {set q [- $t]} set t [- $p $q] } return [* $p $k]
}</lang>
Notes on performance
<lang tcl>foreach proc {gcd_iter gcd gcd_bin} {
puts [format "%-8s - %s" $proc [time {$proc $u $v} 100000]]
}</lang> Outputs:
gcd_iter - 4.46712 microseconds per iteration gcd - 5.73969 microseconds per iteration gcd_bin - 9.25613 microseconds per iteration
TI-83 BASIC, TI-89 BASIC
gcd(A,B)
Ursala
This doesn't need to be defined because it's a library function, but it can be defined like this based on a recursive implementation of Euclid's algorithm. This isn't the simplest possible solution because it includes a bit shifting optimization that happens when both operands are even. <lang Ursala>#import nat
gcd = ~&B?\~&Y ~&alh^?\~&arh2faltPrXPRNfabt2RCQ @a ~&ar^?\~&al ^|R/~& ^/~&r remainder</lang> test program: <lang Ursala>#cast %nWnAL
test = ^(~&,gcd)* <(25,15),(36,16),(120,45),(30,100)></lang> output:
< (25,15): 5, (36,16): 4, (120,45): 15, (30,100): 10>
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
- Programming Tasks
- Arithmetic operations
- Recursion
- ActionScript
- Ada
- ALGOL 68
- APL
- AWK
- AutoHotkey
- Batch File
- BASIC
- Bc
- Befunge
- C
- Clojure
- C sharp
- Common Lisp
- D
- E
- Emacs Lisp
- Erlang
- F Sharp
- Factor
- FALSE
- Forth
- Fortran
- Genyris
- Gnuplot
- Groovy
- Haskell
- HicEst
- Icon
- Icon Programming Library
- Unicon
- J
- Java
- JavaScript
- Joy
- Logo
- Lua
- Lucid
- Mathematica
- MATLAB
- MAXScript
- Modula-3
- MUMPS
- Nial
- OCaml
- Octave
- Oz
- Pascal
- Perl
- Perl 6
- PicoLisp
- PHP
- PL/I
- Pop11
- PowerShell
- Prolog
- PureBasic
- Python
- R
- REBOL
- Ruby
- Sather
- Scala
- Scheme
- Seed7
- SETL
- Slate
- Smalltalk
- SNOBOL4
- Standard ML
- Tcl
- TI-83 BASIC
- TI-89 BASIC
- Ursala
- V