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.
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 M : Integer := A; N : Integer := B; T : Integer; begin while N /= 0 loop T := M; M := N; N := T mod N; end loop; return M; 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
); test:(
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> Output:
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
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>
BBC BASIC
<lang bbcbasic> DEF FN_GCD_Iterative_Euclid(A%, B%)
LOCAL C% WHILE B% C% = A% A% = B% B% = C% MOD B% ENDWHILE = ABS(A%)</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/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
COBOL
<lang cobol> IDENTIFICATION DIVISION.
PROGRAM-ID. GCD.
DATA DIVISION. WORKING-STORAGE SECTION. 01 A PIC 9(10) VALUE ZEROES. 01 B PIC 9(10) VALUE ZEROES. 01 TEMP PIC 9(10) VALUE ZEROES.
PROCEDURE DIVISION. Begin. DISPLAY "Enter first number, max 10 digits." ACCEPT A DISPLAY "Enter second number, max 10 digits." ACCEPT B IF A < B MOVE B TO TEMP MOVE A TO B MOVE TEMP TO B END-IF
PERFORM UNTIL B = 0 MOVE A TO TEMP MOVE B TO A DIVIDE TEMP BY B GIVING TEMP REMAINDER B END-PERFORM DISPLAY "The gcd is " A STOP RUN.</lang>
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>
CoffeeScript
Using a simple for loop. <lang coffeescript> ggt = (x,y) ->
max_teiler = Math.min(x,y) ggt = 0 for teiler in [1..max_teiler] if x % teiler == 0 and y % teiler == 0 ggt = teiler return ggt
alert ggt(40902,24140) </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>
Dc
<lang dc>[dSa%Lard0<G]dsGx+</lang> This code assumes that there are two integers on the stack.
dc -e'28 24 [dSa%Lard0<G]dsGx+ p'
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 b =
match b with | 0 -> a | _ -> gcd b (a % b)
>gcd 400 600 val it : int = 200</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>
Fantom
<lang fantom> class Main {
static Int gcd (Int a, Int b) { a = a.abs b = b.abs while (b > 0) { t := a a = b b = t % b } return a }
public static Void main() { echo ("GCD of 51, 34 is: " + gcd(51, 34)) }
} </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
Frink
Frink has a builtin gcd[x,y]
function that returns the GCD of two integers (which can be arbitrarily large.)
<lang frink>
println[gcd[12345,98765]]
</lang>
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>
Go
this is just a wrapper for big.GcdInt <lang go>import "big" func gcd(x, y int64) int64 {
result := new(big.Int) big.GcdInt(result, nil, nil, big.NewInt(x), big.NewInt(y)) return result.Int64()
}</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
<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>
J
<lang J>x+.y</lang>
For example:
<lang J> 12 +. 30 6</lang>
Note that +.
is a single, two character token. GCD is a primitive in J (and anyone that has studied the right kind of mathematics should instantly recognize why the same operation is used for both GCD and OR).
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>
Iterative Euclid's Algorithm
<lang java> public static int gcd(int a, int b) //valid for positive integers. { while(b > 0) { int c = a % b; a = b; b = c; } return a; } </lang>
Iterative binary algorithm
<lang java>public static long gcd(long u, long v){
long t, k; if (v == 0) return u; u = Math.abs(u); v = Math.abs(v); if (u < v){ t = u; u = v; v = t; } for(k = 1; (u & 1) == 0 && (v & 1) == 0; k <<= 1){ u >>= 1; v >>= 1; } t = (u & 1) != 0 ? -v : u; while (t != 0){ while ((t & 1) == 0) t >>= 1; if (t > 0) u = t; else v = -t; t = u - v; } return u * k;
}</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>
MIPS Assembly
<lang mips>gcd:
# a0 and a1 are the two integer parameters # return value is in v0 move $t0, $a0 move $t1, $a1
loop:
beq $t1, $0, done div $t0, $t1 move $t0, $t1 mfhi $t1 j loop
done:
move $v0, $t0 jr $ra</lang>
Modula-2
<lang Modula-2>MODULE ggTkgV;
FROM InOut IMPORT ReadCard, WriteCard, WriteLn, WriteString, WriteBf;
VAR x, y, u, v : CARDINAL;
BEGIN
WriteString ("x = "); WriteBf; ReadCard (x); WriteString ("y = "); WriteBf; ReadCard (y); u := x; v := y; WHILE x # y DO (* ggT (x, y) = ggT (x0, y0), x * v + y * u = 2 * x0 * y0 *) IF x > y THEN x := x - y; u := u + v ELSE y := y - x; v := v + u END END; WriteString ("ggT ="); WriteCard (x, 6); WriteLn; WriteString ("kgV ="); WriteCard ((u+v) DIV 2, 6); WriteLn; WriteString ("u ="); WriteCard (u, 6); WriteLn; WriteString ("v ="); WriteCard (v , 6); WriteLn
END ggTkgV.</lang> Producing the output <lang Modula-2>jan@Beryllium:~/modula/Wirth/PIM$ ggtkgv x = 12 y = 20 ggT = 4 kgV = 60 u = 44 v = 76 jan@Beryllium:~/modula/Wirth/PIM$ ggtkgv x = 123 y = 255 ggT = 3 kgV = 10455 u = 13773 v = 7137</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>
Objeck
<lang objeck> bundle Default {
class GDC { function : Main(args : String[]), Nil { for(x := 1; x < 36; x += 1;) { IO.Console->GetInstance()->Print("GCD of ")->Print(36)->Print(" and ")->Print(x)->Print(" is ")->PrintLine(GDC(36, x)); }; } function : native : GDC(a : Int, b : Int), Int { t : Int; if(a > b) { t := b; b := a; a := t; }; while (b <> 0) { t := a % b; a := b; b := t; }; return a; } }
} </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>
PARI/GP
<lang parigp>gcd(a,b)</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>
Concise
<lang perl6>my &gcd = { (abs $^a, abs $^b, * % * ... 0)[*-2] }</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>
PostScript
<lang postscript> /gcd { {
{0 gt} {dup rup mod} {pop exit} ifte
} loop }. </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 -ne 0) { $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>
Purity
<lang Purity> data Iterate = f => FoldNat <const id, g => $g . $f>
data Sub = Iterate Pred data IsZero = <const True, const False> . UnNat
data Eq = FoldNat
< const IsZero, eq => n => IfThenElse (IsZero $n) False ($eq (Pred $n)) >
data step = gcd => n => m =>
IfThenElse (Eq $m $n) (Pair $m $n) (IfThenElse (Compare Leq $n $m) ($gcd (Sub $m $n) $m) ($gcd (Sub $n $m) $n))
data gcd = Iterate (gcd => uncurry (step (curry $gcd))) </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 divisor of m and n.} m [integer!] n [integer!] /local k
] [
; Euclid's algorithm while [n > 0] [ k: m m: n n: k // m ] m
]</lang>
Retro
This is from the math extensions library.
<lang Retro>: gcd ( ab-n ) [ tuck mod dup ] while drop ;</lang>
REXX
<lang rexx> /*REXX program to find GCD (greatest common divisor) of two integers*/
say 'the GCD of 7 and 21 is' gcd( 7,21) say 'the GCD of 4 and 7 is' gcd( 4, 7) say 'the GCD of 15 and 10 is' gcd(15,10) say 'the GCD of 51 and 99 is' gcd(51,99)
exit
gcd: procedure; parse arg x,y /*find greatest common divisor.*/
if x=0 | y=0 then return 0
x=abs(x) /*insure X number is positive.*/
y=abs(y) /*insure Y number is positive.*/
do until _==0 _=x//y x=y y=_ end
return x </lang> Output:
the GCD of 7 and 21 is 7 the GCD of 4 and 7 is 1 the GCD of 15 and 10 is 5 the GCD of 51 and 99 is 3
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>
Sed
<lang sed>#! /bin/sed -nf
- gcd.sed Copyright (c) 2010 by Paweł Zuzelski <pawelz@pld-linux.org>
- dc.sed Copyright (c) 1995 - 1997 by Greg Ubben <gsu@romulus.ncsc.mil>
- usage:
- echo N M | ./gcd.sed
- Computes the greatest common divisor of N and M integers using euclidean
- algorithm.
s/^/|P|K0|I10|O10|?~/
s/$/ [lalb%sclbsalcsblb0<F]sF sasblFxlap/
- next
s/|?./|?/ s/|?#[ -}]*/|?/ /|?!*[lLsS;:<>=]\{0,1\}$/N /|?!*[-+*/%^<>=]/b binop /^|.*|?[dpPfQXZvxkiosStT;:]/b binop /|?[_0-9A-F.]/b number /|?\[/b string /|?l/b load /|?L/b Load /|?[sS]/b save /|?c/ s/[^|]*// /|?d/ s/[^~]*~/&&/ /|?f/ s//&[pSbz0<aLb]dSaxsaLa/ /|?x/ s/\([^~]*~\)\(.*|?x\)~*/\2\1/ /|?[KIO]/ s/.*|\([KIO]\)\([^|]*\).*|?\1/\2~&/ /|?T/ s/\.*0*~/~/
- a slow, non-stackable array implementation in dc, just for completeness
- A fast, stackable, associative array implementation could be done in sed
- (format: {key}value{key}value...), but would be longer, like load & save.
/|?;/ s/|?;\([^{}]\)/|?~[s}s{L{s}q]S}[S}l\1L}1-d0>}s\1L\1l{xS\1]dS{xL}/ /|?:/ s/|?:\([^{}]\)/|?~[s}L{s}L{s}L}s\1q]S}S}S{[L}1-d0>}S}l\1s\1L\1l{xS\1]dS{x/ /|?[ ~ cdfxKIOT]/b next /|?\n/b next /|?[pP]/b print /|?k/ s/^\([0-9]\{1,3\}\)\([.~].*|K\)[^|]*/\2\1/ /|?i/ s/^\(-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}\)\(~.*|I\)[^|]*/\2\1/ /|?o/ s/^\(-\{0,1\}[1-9][0-9]*\.\{0,1\}[0-9]*\)\(~.*|O\)[^|]*/\2\1/ /|?[kio]/b pop /|?t/b trunc /|??/b input /|?Q/b break /|?q/b quit h /|?[XZz]/b count /|?v/b sqrt s/.*|?\([^Y]\).*/\1 is unimplemented/ s/\n/\\n/g l g b next
/^-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}~.*|?p/!b Print /|O10|/b Print
- Print a number in a non-decimal output base. Uses registers a,b,c,d.
- Handles fractional output bases (O<-1 or O>=1), unlike other dc's.
- Converts the fraction correctly on negative output bases, unlike
- UNIX dc. Also scales the fraction more accurately than UNIX dc.
s,|?p,&KSa0kd[[-]Psa0la-]Sad0>a[0P]sad0=a[A*2+]saOtd0>a1-ZSd[[[[ ]P]sclb1\ !=cSbLdlbtZ[[[-]P0lb-sb]sclb0>c1+]sclb0!<c[0P1+dld>c]scdld>cscSdLbP]q]Sb\ [t[1P1-d0<c]scd0<c]ScO_1>bO1!<cO[16]<bOX0<b[[q]sc[dSbdA>c[A]sbdA=c[B]sbd\ B=c[C]sbdC=c[D]sbdD=c[E]sbdE=c[F]sb]xscLbP]~Sd[dtdZOZ+k1O/Tdsb[.5]*[.1]O\ X^*dZkdXK-1+ktsc0kdSb-[Lbdlb*lc+tdSbO*-lb0!=aldx]dsaxLbsb]sad1!>a[[.]POX\ +sb1[SbO*dtdldx-LbO*dZlb!<a]dsax]sadXd0<asbsasaLasbLbscLcsdLdsdLdLak[]pP, b next
/|?p/s/[^~]*/&\ ~&/ s/\(.*|P\)\([^|]*\)/\ \2\1/ s/\([^~]*\)\n\([^~]*\)\(.*|P\)/\1\3\2/ h s/~.*// /./{ s/.//; p; }
- Just s/.//p would work if we knew we were running under the -n option.
- Using l vs p would kind of do \ continuations, but would break strings.
g
- pop
s/[^~]*~// b next
- load
s/\(.*|?.\)\(.\)/\20~\1/ s/^\(.\)0\(.*|r\1\([^~|]*\)~\)/\1\3\2/ s/.// b next
- Load
s/\(.*|?.\)\(.\)/\2\1/ s/^\(.\)\(.*|r\1\)\([^~|]*~\)/|\3\2/ /^|/!i\ register empty s/.// b next
- save
s/\(.*|?.\)\(.\)/\2\1/ /^\(.\).*|r\1/ !s/\(.\).*|/&r\1|/ /|?S/ s/\(.\).*|r\1/&~/ s/\(.\)\([^~]*~\)\(.*|r\1\)[^~|]*~\{0,1\}/\3\2/ b next
- quit
t quit s/|?[^~]*~[^~]*~/|?q/ t next
- Really should be using the -n option to avoid printing a final newline.
s/.*|P\([^|]*\).*/\1/ q
- break
s/[0-9]*/&;987654321009;/
- break1
s/^\([^;]*\)\([1-9]\)\(0*\)\([^1]*\2\(.\)[^;]*\3\(9*\).*|?.\)[^~]*~/\1\5\6\4/ t break1 b pop
- input
N s/|??\(.*\)\(\n.*\)/|?\2~\1/ b next
- count
/|?Z/ s/~.*// /^-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}$/ s/[-.0]*\([^.]*\)\.*/\1/ /|?X/ s/-*[0-9A-F]*\.*\([0-9A-F]*\).*/\1/ s/|.*// /~/ s/[^~]//g
s/./a/g
- count1
s/a\{10\}/b/g s/b*a*/&a9876543210;/ s/a.\{9\}\(.\).*;/\1/ y/b/a/ /a/b count1 G /|?z/ s/\n/&~/ s/\n[^~]*// b next
- trunc
- for efficiency, doesn't pad with 0s, so 10k 2 5/ returns just .40
- The X* here and in a couple other places works around a SunOS 4.x sed bug.
s/\([^.~]*\.*\)\(.*|K\([^|]*\)\)/\3;9876543210009909:\1,\2/
- trunc1
s/^\([^;]*\)\([1-9]\)\(0*\)\([^1]*\2\(.\)[^:]*X*\3\(9*\)[^,]*\),\([0-9]\)/\1\5\6\4\7,/ t trunc1 s/[^:]*:\([^,]*\)[^~]*/\1/ b normal
- number
s/\(.*|?\)\(_\{0,1\}[0-9A-F]*\.\{0,1\}[0-9A-F]*\)/\2~\1~/ s/^_/-/ /^[^A-F~]*~.*|I10|/b normal /^[-0.]*~/b normal s:\([^.~]*\)\.*\([^~]*\):[Ilb^lbk/,\1\2~0A1B2C3D4E5F1=11223344556677889900;.\2:
- digit
s/^\([^,]*\),\(-*\)\([0-F]\)\([^;]*\(.\)\3[^1;]*\(1*\)\)/I*+\1\2\6\5~,\2\4/
t digit s:...\([^/]*.\)\([^,]*\)[^.]*\(.*|?.\):\2\3KSb[99]k\1]SaSaXSbLalb0<aLakLbktLbk: b next
- string
/|?[^]]*$/N s/\(|?[^]]*\)\[\([^]]*\)]/\1|{\2|}/ /|?\[/b string s/\(.*|?\)|{\(.*\)|}/\2~\1[/ s/|{/[/g s/|}/]/g b next
- binop
/^[^~|]*~[^|]/ !i\ stack empty //!b next /^-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}~/ !s/[^~]*\(.*|?!*[^!=<>]\)/0\1/ /^[^~]*~-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}~/ !s/~[^~]*\(.*|?!*[^!=<>]\)/~0\1/ h /|?\*/b mul /|?\//b div /|?%/b rem /|?^/b exp
/|?[+-]/ s/^\(-*\)\([^~]*~\)\(-*\)\([^~]*~\).*|?\(-\{0,1\}\).*/\2\4s\3o\1\3\5/ s/\([^.~]*\)\([^~]*~[^.~]*\)\(.*\)/<\1,\2,\3|=-~.0,123456789<></ /^<\([^,]*,[^~]*\)\.*0*~\1\.*0*~/ s/</=/
- cmp1
s/^\(<[^,]*\)\([0-9]\),\([^,]*\)\([0-9]\),/\1,\2\3,\4/ t cmp1 /^<\([^~]*\)\([^~]\)[^~]*~\1\(.\).*|=.*\3.*\2/ s/</>/ /|?/{ s/^\([<>]\)\(-[^~]*~-.*\1\)\(.\)/\3\2/ s/^\(.\)\(.*|?!*\)\1/\2!\1/ s/|?![^!]\(.\)/&l\1x/ s/[^~]*~[^~]*~\(.*|?\)!*.\(.*\)|=.*/\1\2/ b next } s/\(-*\)\1|=.*/;9876543210;9876543210/ /o-/ s/;9876543210/;0123456789/ s/^>\([^~]*~\)\([^~]*~\)s\(-*\)\(-*o\3\(-*\)\)/>\2\1s\5\4/
s/,\([0-9]*\)\.*\([^,]*\),\([0-9]*\)\.*\([0-9]*\)/\1,\2\3.,\4;0/
- right1
s/,\([0-9]\)\([^,]*\),;*\([0-9]\)\([0-9]*\);*0*/\1,\2\3,\4;0/ t right1 s/.\([^,]*\),~\(.*\);0~s\(-*\)o-*/\1~\30\2~/
- addsub1
s/\(.\{0,1\}\)\(~[^,]*\)\([0-9]\)\(\.*\),\([^;]*\)\(;\([^;]*\(\3[^;]*\)\).*X*\1\(.*\)\)/\2,\4\5\9\8\7\6/ s/,\([^~]*~\).\{10\}\(.\)[^;]\{0,9\}\([^;]\{0,1\}\)[^;]*/,\2\1\3/
- could be done in one s/// if we could have >9 back-refs...
/^~.*~;/!b addsub1
- endbin
s/.\([^,]*\),\([0-9.]*\).*/\1\2/ G s/\n[^~]*~[^~]*//
- normal
s/^\(-*\)0*\([0-9.]*[0-9]\)[^~]*/\1\2/ s/^[^1-9~]*~/0~/ b next
- mul
s/\(-*\)\([0-9]*\)\.*\([0-9]*\)~\(-*\)\([0-9]*\)\.*\([0-9]*\).*|K\([^|]*\).*/\1\4\2\5.!\3\6,|\2<\3~\5>\6:\7;9876543210009909/
- mul1
s/![0-9]\([^<]*\)<\([0-9]\{0,1\}\)\([^>]*\)>\([0-9]\{0,1\}\)/0!\1\2<\3\4>/ /![0-9]/ s/\(:[^;]*\)\([1-9]\)\(0*\)\([^0]*\2\(.\).*X*\3\(9*\)\)/\1\5\6\4/
/<~[^>]*>:0*;/!t mul1
s/\(-*\)\1\([^>]*\).*/;\2^>:9876543210aaaaaaaaa/
- mul2
s/\([0-9]~*\)^/^\1/ s/<\([0-9]*\)\(.*[~^]\)\([0-9]*\)>/\1<\2>\3/
:mul3
s/>\([0-9]\)\(.*\1.\{9\}\(a*\)\)/\1>\2;9\38\37\36\35\34\33\32\31\30/ s/\(;[^<]*\)\([0-9]\)<\([^;]*\).*\2[0-9]*\(.*\)/\4\1<\2\3/ s/a[0-9]/a/g s/a\{10\}/b/g s/b\{10\}/c/g
/|0*[1-9][^>]*>0*[1-9]/b mul3
s/;/a9876543210;/ s/a.\{9\}\(.\)[^;]*\([^,]*\)[0-9]\([.!]*\),/\2,\1\3/ y/cb/ba/
/|<^/!b mul2 b endbin
- div
- CDDET
/^[-.0]*[1-9]/ !i\ divide by 0 //!b pop s/\(-*\)\([0-9]*\)\.*\([^~]*~-*\)\([0-9]*\)\.*\([^~]*\)/\2.\3\1;0\4.\5;0/
- div1
s/^\.0\([^.]*\)\.;*\([0-9]\)\([0-9]*\);*0*/.\1\2.\3;0/ s/^\([^.]*\)\([0-9]\)\.\([^;]*;\)0*\([0-9]*\)\([0-9]\)\./\1.\2\30\4.\5/ t div1 s/~\(-*\)\1\(-*\);0*\([^;]*[0-9]\)[^~]*/~123456789743222111~\2\3/ s/\(.\(.\)[^~]*\)[^9]*\2.\{8\}\(.\)[^~]*/\3~\1/ s,|?.,&SaSadSaKdlaZ+LaX-1+[sb1]Sbd1>bkLatsbLa[dSa2lbla*-*dLa!=a]dSaxsakLasbLb*t, b next
- rem
s,|?%,&Sadla/LaKSa[999]k*Lak-, b next
- exp
- This decimal method is just a little faster than the binary method done
- totally in dc: 1LaKLb [kdSb*LbK]Sb [[.5]*d0ktdSa<bkd*KLad1<a]Sa d1<a kk*
/^[^~]*\./i\ fraction in exponent ignored s,[^-0-9].*,;9d**dd*8*d*d7dd**d*6d**d5d*d*4*d3d*2lbd**1lb*0,
- exp1
s/\([0-9]\);\(.*\1\([d*]*\)[^l]*\([^*]*\)\(\**\)\)/;dd*d**d*\4\3\5\2/ t exp1 G s,-*.\{9\}\([^9]*\)[^0]*0.\(.*|?.\),\2~saSaKdsaLb0kLbkK*+k1\1LaktsbkLax, s,|?.,&SadSbdXSaZla-SbKLaLadSb[0Lb-d1lb-*d+K+0kkSb[1Lb/]q]Sa0>a[dk]sadK<a[Lb], b next
- sqrt
- first square root using sed: 8k2v at 1:30am Dec 17, 1996
/^-/i\ square root of negative number /^[-0]/b next s/~.*// /^\./ s/0\([0-9]\)/\1/g /^\./ !s/[0-9][0-9]/7/g G s/\n/~/ s,|?.,&K1+k KSbSb[dk]SadXdK<asadlb/lb+[.5]*[sbdlb/lb+[.5]*dlb>a]dsaxsasaLbsaLatLbk K1-kt, b next
- END OF GSU dc.sed</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
x86 Assembly
Using AT & T syntax under linux. <lang 8086 Assembly>.text .global pgcd
pgcd:
push %ebp mov %esp, %ebp
mov 8(%ebp), %eax mov 12(%ebp), %ecx push %edx
.loop:
cmp $0, %ecx je .end xor %edx, %edx div %ecx mov %ecx, %eax mov %edx, %ecx jmp .loop
.end:
pop %edx leave ret</lang>