Greatest common divisor: Difference between revisions
Line 3,410:
=={{header|Joy}}==
<
=={{header|jq}}==
Line 4,109:
return
-- 09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)~~
-- Euclid's algorithm - iterative implementation
method gcdEucidI(a_, b_) public static
Line 4,119:
return a_
-- 09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)~~
-- Euclid's algorithm - recursive implementation
method gcdEucidR(a_, b_) public static
Line 4,125:
return a_
-- 09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)~~
method runSample(arg) private static
-- pairs of numbers, each number in the pair separated by a colon, each pair separated by a comma
Line 4,171:
return
-- 09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)~~
method showResults(stem, title) public static
say
Line 4,182:
return
-- 09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)~~
method verifyResults(stem1, stem2) public static returns boolean
if stem1[0] \= stem2[0] then signal BadArgumentException
|
Revision as of 09:53, 27 August 2022
![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.
- Task
Find the greatest common divisor (GCD) of two integers.
Greatest common divisor is also known as greatest common factor (gcf) and greatest common measure.
- Related task
- See also
-
- MathWorld entry: greatest common divisor.
- Wikipedia entry: greatest common divisor.
11l
<lang 11l>F gcd(=u, =v)
L v != 0 (u, v) = (v, u % v) R abs(u)
print(gcd(0, 0)) print(gcd(0, 10)) print(gcd(0, -10)) print(gcd(9, 6)) print(gcd(6, 9)) print(gcd(-6, 9)) print(gcd(8, 45)) print(gcd(40902, 24140))</lang>
- Output:
0 10 10 3 3 3 1 34
360 Assembly
For maximum compatibility, this program uses only the basic instruction set (S/360) with 2 ASSIST macros (XDECO,XPRNT). <lang 360asm>* Greatest common divisor 04/05/2016 GCD CSECT
USING GCD,R15 use calling register L R6,A u=a L R7,B v=b
LOOPW LTR R7,R7 while v<>0
BZ ELOOPW leave while LR R8,R6 t=u LR R6,R7 u=v LR R4,R8 t SRDA R4,32 shift to next reg DR R4,R7 t/v LR R7,R4 v=mod(t,v) B LOOPW end while
ELOOPW LPR R9,R6 c=abs(u)
L R1,A a XDECO R1,XDEC edit a MVC PG+4(5),XDEC+7 move a to buffer L R1,B b XDECO R1,XDEC edit b MVC PG+10(5),XDEC+7 move b to buffer XDECO R9,XDEC edit c MVC PG+17(5),XDEC+7 move c to buffer XPRNT PG,80 print buffer XR R15,R15 return code =0 BR R14 return to caller
A DC F'1071' a B DC F'1029' b PG DC CL80'gcd(00000,00000)=00000' buffer XDEC DS CL12 temp for edit
YREGS END GCD</lang>
- Output:
gcd( 1071, 1029)= 21
8th
<lang forth>: gcd \ a b -- gcd dup 0 n:= if drop ;; then tuck \ b a b n:mod \ b a-mod-b recurse ;
- demo \ a b --
2dup "GCD of " . . " and " . . " = " . gcd . ;
100 5 demo cr
5 100 demo cr 7 23 demo cr
bye </lang>
- Output:
GCD of 5 and 100 = 5 GCD of 100 and 5 = 5 GCD of 23 and 7 = 1
AArch64 Assembly
<lang AArch64 Assembly> /* ARM assembly AARCH64 Raspberry PI 3B */ /* program calPgcd64.s */
/*******************************************/ /* Constantes file */ /*******************************************/ /* for this file see task include a file in language AArch64 assembly*/ .include "../includeConstantesARM64.inc"
/*********************************/ /* Initialized data */ /*********************************/ .data sMessResult: .asciz "Number 1 : @ number 2 : @ PGCD : @ \n" szCarriageReturn: .asciz "\n" szMessError: .asciz "Error PGCD !!\n"
/*********************************/ /* UnInitialized data */ /*********************************/ .bss sZoneConv: .skip 24 /*********************************/ /* code section */ /*********************************/ .text .global main main: // entry of program
mov x20,36 mov x21,18 mov x0,x20 mov x1,x21 bl calPGCDmod bcs 99f // error ? mov x2,x0 // pgcd mov x0,x20 mov x1,x21 bl displayResult mov x20,37 mov x21,15 mov x0,x20 mov x1,x21 bl calPGCDmod bcs 99f // error ? mov x2,x0 // pgcd mov x0,x20 mov x1,x21 bl displayResult b 100f
99: // display error
ldr x0,qAdrszMessError bl affichageMess
100: // standard end of the program
mov x0, #0 // return code mov x8, #EXIT // request to exit program svc #0 // perform the system call
qAdrszCarriageReturn: .quad szCarriageReturn qAdrszMessError: .quad szMessError
/***************************************************/ /* Compute pgcd modulo use */ /***************************************************/ /* x0 contains first number */ /* x1 contains second number */ /* x0 return PGCD */ /* if error carry set to 1 */ calPGCDmod:
stp x1,lr,[sp,-16]! // save registres stp x2,x3,[sp,-16]! // save registres cbz x0,99f // if = 0 error cbz x1,99f cmp x0,0 bgt 1f neg x0,x0 // if negative inversion number 1
1:
cmp x1,0 bgt 2f neg x1,x1 // if negative inversion number 2
2:
cmp x0,x1 // compare two numbers bgt 3f mov x2,x0 // inversion mov x0,x1 mov x1,x2
3:
udiv x2,x0,x1 // division msub x0,x2,x1,x0 // compute remainder cmp x0,0 bgt 2b // loop mov x0,x1 cmn x0,0 // clear carry b 100f
99: // error
mov x0,0 cmp x0,0 // set carry
100:
ldp x2,x3,[sp],16 // restaur des 2 registres ldp x1,lr,[sp],16 // restaur des 2 registres ret // retour adresse lr x30
/***************************************************/ /* display result */ /***************************************************/ /* x0 contains first number */ /* x1 contains second number */ /* x2 contains PGCD */ displayResult:
stp x1,lr,[sp,-16]! // save registres mov x3,x1 // save x1 ldr x1,qAdrsZoneConv bl conversion10 // décimal conversion ldr x0,qAdrsMessResult ldr x1,qAdrsZoneConv // insert conversion bl strInsertAtCharInc mov x4,x0 // save message address mov x0,x3 // conversion second number ldr x1,qAdrsZoneConv bl conversion10 // décimal conversion mov x0,x4 // move message address ldr x1,qAdrsZoneConv // insert conversion bl strInsertAtCharInc mov x4,x0 // save message address mov x0,x2 // conversion pgcd ldr x1,qAdrsZoneConv bl conversion10 // décimal conversion mov x0,x4 // move message address ldr x1,qAdrsZoneConv // insert conversion bl strInsertAtCharInc bl affichageMess // display message ldp x1,lr,[sp],16 // restaur des 2 registres ret // retour adresse lr x30
qAdrsMessResult: .quad sMessResult qAdrsZoneConv: .quad sZoneConv /********************************************************/ /* File Include fonctions */ /********************************************************/ /* for this file see task include a file in language AArch64 assembly */ .include "../includeARM64.inc" </lang>
ACL2
<lang Lisp>(include-book "arithmetic-3/floor-mod/floor-mod" :dir :system)
(defun gcd$ (x y)
(declare (xargs :guard (and (natp x) (natp y)))) (cond ((or (not (natp x)) (< y 0)) nil) ((zp y) x) (t (gcd$ y (mod x y)))))</lang>
Action!
<lang Action!>CARD FUNC Gcd(CARD a,b)
CARD tmp
IF a<b THEN tmp=a a=b b=tmp FI
WHILE b#0 DO tmp=a MOD b a=b b=tmp OD
RETURN(a)
PROC Test(CARD a,b)
CARD res
res=Gcd(a,b) PrintF("GCD of %I and %I is %I%E",a,b,res)
RETURN
PROC Main()
Test(48,18) Test(9360,12240) Test(17,19) Test(123,1) Test(0,0)
RETURN</lang>
- Output:
Screenshot from Atari 8-bit computer
GCD of 48 and 18 is 6 GCD of 9360 and 12240 is 720 GCD of 17 and 19 is 1 GCD of 123 and 1 is 1 GCD of 0 and 0 is 0
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
Aime
<lang aime>o_integer(gcd(33, 77)); o_byte('\n'); o_integer(gcd(49865, 69811)); o_byte('\n');</lang>
ALGOL 60
<lang algol60>begin
comment Greatest common divisor - algol 60;
integer procedure gcd(m,n); value m,n;
integer m,n;
begin integer a,b; a:=abs(m); b:=abs(n); if a=0 then gcd:=b else begin
integer c,i; for i:=a while b notequal 0 do begin
c:=b; b:=a-(a div b)*b; a:=c end; gcd:=a end end gcd;
outinteger(1,gcd(21,35))
end </lang>
- Output:
7
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
ALGOL-M
<lang algol>BEGIN
% RETURN P MOD Q % INTEGER FUNCTION MOD (P, Q); INTEGER P, Q; BEGIN
MOD := P - Q * (P / Q);
END;
% RETURN GREATEST COMMON DIVISOR OF X AND Y % INTEGER FUNCTION GCD (X, Y); INTEGER X, Y; BEGIN INTEGER R; IF X < Y THEN BEGIN INTEGER TEMP; TEMP := X; X := Y; Y := TEMP; END; WHILE (R := MOD(X, Y)) <> 0 DO BEGIN X := Y; Y := R; END; GCD := Y; END;
COMMENT - EXERCISE THE FUNCTION;
WRITE("THE GDC OF 21 AND 35 IS", GCD(21,35)); WRITE("THE GDC OF 23 AND 35 IS", GCD(23,35)); WRITE("THE GDC OF 1071 AND 1029 IS", GCD(1071,1029)); WRITE("THE GDC OF 3528 AND 3780 IS", GCD(3528,252));
END</lang>
- Output:
THE GDC OF 21 AND 35 IS 7 THE GDC OF 23 AND 35 IS 1 THE GDC OF 1071 AND 1029 IS 21 THE GDC OF 3528 AND 3780 IS 252
ALGOL W
<lang algolw>begin
% iterative Greatest Common Divisor routine % integer procedure gcd ( integer value m, n ) ; begin integer a, b, newA; a := abs( m ); b := abs( n ); if a = 0 then begin b end else begin while b not = 0 do begin newA := b; b := a rem b; a := newA; end; a end end gcd ;
write( gcd( -21, 35 ) );
end.</lang>
Alore
<lang Alore>def gcd(a as Int, b as Int) as Int
while b != 0 a,b = b, a mod b end return Abs(a)
end</lang>
AntLang
AntLang has a built-in gcd function. <lang AntLang>gcd[33; 77]</lang>
It is not recommended, but possible to implement it on your own. <lang AntLang>/Unoptimized version gcd':{a:x;b:y;last[{(0 eq a mod x) min (0 eq b mod x)} hfilter {1 + x} map range[a max b]]}</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
AppleScript
By recursion:
<lang AppleScript>-- gcd :: Int -> Int -> Int on gcd(a, b)
if b ≠ 0 then gcd(b, a mod b) else if a < 0 then -a else a end if end if
end gcd </lang>
And just for the sake of it, the same thing iteratively:
<lang applescript>on hcf(a, b)
repeat until (b = 0) set x to a set a to b set b to x mod b end repeat if (a < 0) then return -a return a
end hcf</lang>
Applesoft BASIC
<lang ApplesoftBasic>0 A = ABS(INT(A)) 1 B = ABS(INT(B)) 2 GCD = A * NOT NOT B 3 FOR B = B + A * NOT B TO 0 STEP 0 4 A = GCD 5 GCD = B 6 B = A - INT (A / GCD) * GCD 7 NEXT B</lang>
Arendelle
< a , b > ( r , @a ) [ @r != 0 , ( r , @a % @b ) { @r != 0 , ( a , @b ) ( b , @r ) } ] ( return , @b )
Arturo
<lang rebol>print gcd [10 15]</lang>
- Output:
5
ATS
Stein’s algorithm, without proofs
Here is an implementation of Stein’s algorithm, without proofs of termination or correctness.
<lang ats>(********************************************************************) (*
GCD of two integers, by Stein’s algorithm: https://en.wikipedia.org/w/index.php?title=Binary_GCD_algorithm&oldid=1072393147
This is an implementation without proofs of anything.
The implementations shown here require the GCC builtin functions for ‘count trailing zeros’. If your C compiler is GCC or another that supports those functions, you are fine. Otherwise, one could easily substitute other C code.
Compile with ‘patscc -o gcd gcd.dats’.
- )
- define ATS_EXTERN_PREFIX "rosettacode_gcd_"
- define ATS_DYNLOADFLAG 0 (* No initialization is needed. *)
- include "share/atspre_define.hats"
- include "share/atspre_staload.hats"
(********************************************************************) (* *) (* Declarations of the functions. *) (* *)
(* g0uint_gcd_stein will be the generic template function for
unsigned integers. *)
extern fun {tk : tkind} g0uint_gcd_stein :
(g0uint tk, g0uint tk) -<> g0uint tk
(* g0int_gcd_stein will be the generic template function for
signed integers, giving an unsigned result. *)
extern fun {tk_signed, tk_unsigned : tkind} g0int_gcd_stein :
(g0int tk_signed, g0int tk_signed) -<> g0uint tk_unsigned
(* Let us call these functions ‘gcd_stein’ or just ‘gcd’. *) overload gcd_stein with g0uint_gcd_stein overload gcd_stein with g0int_gcd_stein overload gcd with gcd_stein
(********************************************************************) (* *) (* The implementations. *) (* *)
%{^
/*
We will need a ‘count trailing zeros of a positive number’ function, but this is not provided in the ATS prelude. Here are implementations using GCC builtin functions. For fast alternatives in standard C, see https://www.chessprogramming.org/index.php?title=BitScan&oldid=22495#Trailing_Zero_Count
- /
ATSinline() atstype_uint rosettacode_gcd_g0uint_ctz_uint (atstype_uint x) {
return __builtin_ctz (x);
}
ATSinline() atstype_ulint rosettacode_gcd_g0uint_ctz_ulint (atstype_ulint x) {
return __builtin_ctzl (x);
}
ATSinline() atstype_ullint rosettacode_gcd_g0uint_ctz_ullint (atstype_ullint x) {
return __builtin_ctzll (x);
}
%}
extern fun g0uint_ctz_uint : uint -<> int = "mac#%" extern fun g0uint_ctz_ulint : ulint -<> int = "mac#%" extern fun g0uint_ctz_ullint : ullint -<> int = "mac#%"
(* A generic template function for ‘count trailing zeros’ of
non-dependent unsigned integers. *)
extern fun {tk : tkind} g0uint_ctz : g0uint tk -<> int
(* Link the implementations to the template function. *) implement g0uint_ctz<uint_kind> (x) = g0uint_ctz_uint x implement g0uint_ctz<ulint_kind> (x) = g0uint_ctz_ulint x implement g0uint_ctz<ullint_kind> (x) = g0uint_ctz_ullint x
(* Let one call the function simply ‘ctz’. *) overload ctz with g0uint_ctz
(* Now the actual implementation of g0uint_gcd_stein, the template
function for the gcd of two unsigned integers. *)
implement {tk} g0uint_gcd_stein (u, v) =
let (* Make ‘t’ a shorthand for the unsigned integer type. *) typedef t = g0uint tk
(* Use this macro to fake proof that an int is non-negative. *) macdef nonneg (n) = $UNSAFE.cast{intGte 0} ,(n)
(* Looping is done by tail recursion. There is no proof the function terminates; this fact is indicated by ‘<!ntm>’. *) fun {tk : tkind} main_loop (x_odd : t, y : t) :<!ntm> t = let (* Remove twos from y, giving an odd number. Note gcd(x_odd,y_odd) = gcd(x_odd,y). *) val y_odd = (y >> nonneg (ctz y)) in if x_odd = y_odd then x_odd else let (* If y_odd < x_odd then swap x_odd and y_odd. This operation does not affect the gcd. *) val x_odd = min (x_odd, y_odd) and y_odd = max (x_odd, y_odd) in main_loop (x_odd, y_odd - x_odd) end end
fn u_and_v_both_positive (u : t, v : t) :<> t = let (* n = the number of common factors of two in u and v. *) val n = ctz (u lor v)
(* Remove the common twos from u and v, giving x and y. *) val x = (u >> nonneg n) val y = (v >> nonneg n)
(* Remove twos from x, giving an odd number. Note gcd(x_odd,y) = gcd(x,y). *) val x_odd = (x >> nonneg (ctz x))
(* Run the main loop, but pretend it is proven to terminate. Otherwise we could not write ‘<>’ above, telling the ATS compiler that we trust the function to terminate. *) val z = $effmask_ntm (main_loop (x_odd, y)) in (* Put the common factors of two back in. *) (z << nonneg n) end
(* If v < u then swap u and v. This operation does not affect the gcd. *) val u = min (u, v) and v = max (u, v) in if iseqz u then v else u_and_v_both_positive (u, v) end
(* The implementation of g0int_gcd_stein, the template function for
the gcd of two signed integers, giving an unsigned result. *)
implement {signed_tk, unsigned_tk} g0int_gcd_stein (u, v) =
let val abs_u = $UNSAFE.cast{g0uint unsigned_tk} (abs u) val abs_v = $UNSAFE.cast{g0uint unsigned_tk} (abs v) in g0uint_gcd_stein<unsigned_tk> (abs_u, abs_v) end
(********************************************************************) (* A demonstration program. *)
implement main0 () =
begin (* Unsigned integers. *) assertloc (gcd (0U, 10U) = 10U); assertloc (gcd (9UL, 6UL) = 3UL); assertloc (gcd (40902ULL, 24140ULL) = 34ULL);
(* Signed integers. *) assertloc (gcd (0, 10) = gcd (0U, 10U)); assertloc (gcd (~10, 0) = gcd (0U, 10U)); assertloc (gcd (~6L, ~9L) = 3UL); assertloc (gcd (40902LL, 24140LL) = 34ULL); assertloc (gcd (40902LL, ~24140LL) = 34ULL); assertloc (gcd (~40902LL, 24140LL) = 34ULL); assertloc (gcd (~40902LL, ~24140LL) = 34ULL); assertloc (gcd (24140LL, 40902LL) = 34ULL); assertloc (gcd (~24140LL, 40902LL) = 34ULL); assertloc (gcd (24140LL, ~40902LL) = 34ULL); assertloc (gcd (~24140LL, ~40902LL) = 34ULL) end
(********************************************************************)</lang>
Stein’s algorithm, with proof of termination
Here is an implementation of Stein’s algorithm, this time with a proof of termination. Notice that the proof is rather ‘informal’; this is practical systems programming, not an exercise in mathematical logic.
<lang ats>(********************************************************************) (*
GCD of two integers, by Stein’s algorithm: https://en.wikipedia.org/w/index.php?title=Binary_GCD_algorithm&oldid=1072393147
This is an implementation with proof of termination.
The implementations shown here require the GCC builtin functions for ‘count trailing zeros’. If your C compiler is GCC or another that supports those functions, you are fine. Otherwise, one could easily substitute other C code.
Compile with ‘patscc -o gcd gcd.dats’.
- )
- define ATS_EXTERN_PREFIX "rosettacode_gcd_"
- define ATS_DYNLOADFLAG 0 (* No initialization is needed. *)
- include "share/atspre_define.hats"
- include "share/atspre_staload.hats"
(********************************************************************) (* *) (* Declarations of the functions. *) (* *)
(* g1uint_gcd_stein will be the generic template function for
unsigned integers. *)
extern fun {tk : tkind} g0uint_gcd_stein :
(g0uint tk, g0uint tk) -<> g0uint tk
(* g0int_gcd_stein will be the generic template function for
signed integers, giving an unsigned result. *)
extern fun {tk_signed, tk_unsigned : tkind} g0int_gcd_stein :
(g0int tk_signed, g0int tk_signed) -<> g0uint tk_unsigned
(* Let us call these functions ‘gcd_stein’ or just ‘gcd’. *) overload gcd_stein with g0uint_gcd_stein overload gcd_stein with g0int_gcd_stein overload gcd with gcd_stein
(********************************************************************) (* *) (* The implementations. *) (* *)
%{^
/*
We will need a ‘count trailing zeros of a positive number’ function, but this is not provided in the ATS prelude. Here are implementations using GCC builtin functions. For fast alternatives in standard C, see https://www.chessprogramming.org/index.php?title=BitScan&oldid=22495#Trailing_Zero_Count
- /
ATSinline() atstype_uint rosettacode_gcd_g0uint_ctz_uint (atstype_uint x) {
return __builtin_ctz (x);
}
ATSinline() atstype_ulint rosettacode_gcd_g0uint_ctz_ulint (atstype_ulint x) {
return __builtin_ctzl (x);
}
ATSinline() atstype_ullint rosettacode_gcd_g0uint_ctz_ullint (atstype_ullint x) {
return __builtin_ctzll (x);
}
%}
extern fun g0uint_ctz_uint : uint -<> int = "mac#%" extern fun g0uint_ctz_ulint : ulint -<> int = "mac#%" extern fun g0uint_ctz_ullint : ullint -<> int = "mac#%"
(* A generic template function for ‘count trailing zeros’ of
non-dependent unsigned integers. *)
extern fun {tk : tkind} g0uint_ctz : g0uint tk -<> int
(* Link the implementations to the template function. *) implement g0uint_ctz<uint_kind> (x) = g0uint_ctz_uint x implement g0uint_ctz<ulint_kind> (x) = g0uint_ctz_ulint x implement g0uint_ctz<ullint_kind> (x) = g0uint_ctz_ullint x
(* Let one call the function simply ‘ctz’. *) overload ctz with g0uint_ctz
(* Now the actual implementation of g0uint_gcd_stein, the template
function for the gcd of two unsigned integers. *)
implement {tk} g0uint_gcd_stein (u, v) =
let (* Make ‘t’ a shorthand for the unsigned integer types. *) typedef t = g0uint tk typedef t (i : int) = g1uint (tk, i)
(* Use this macro to fake proof that an int is non-negative. *) macdef nonneg (n) = $UNSAFE.cast{intGte 0} ,(n)
(* Looping is done by tail recursion. The value of (x_odd + y) must decrease towards zero, to prove termination. *) fun {tk : tkind} main_loop {x_odd, y : pos} .<x_odd + y>. (x_odd : t (x_odd), y : t (y)) :<> [d : pos] t (d) = let
(* Remove twos from y, giving an odd number. Note gcd(x_odd,y_odd) = gcd(x_odd,y). We do not have a dependent-type version of the following operation, so let us do it with non-dependent types. *) val [y_odd : int] y_odd = g1ofg0 ((g0ofg1 y) >> nonneg (ctz (g0ofg1 y)))
(* Assert some things we know without proof. (You could also use assertloc, which inserts a runtime check.) *) prval _ = $UNSAFE.prop_assert {0 < y_odd} () prval _ = $UNSAFE.prop_assert {y_odd <= y} () in if x_odd = y_odd then x_odd else if y_odd < x_odd then main_loop (y_odd, x_odd - y_odd) else main_loop (x_odd, y_odd - x_odd) end
fn u_and_v_both_positive (u : t, v : t) :<> t = let (* n = the number of common factors of two in u and v. *) val n = ctz (u lor v)
(* Remove the common twos from u and v, giving x and y. *) val x = (u >> nonneg n) val y = (v >> nonneg n)
(* Remove twos from x, giving an odd number. Note gcd(x_odd,y) = gcd(x,y). *) val x_odd = (x >> nonneg (ctz x))
(* To prove termination of main_loop, we have to convert x_odd and y to a dependent type. *) val [x_odd : int] x_odd = g1ofg0 x_odd val [y : int] y = g1ofg0 y
(* Assert that they are positive. (One could also use assertloc, which inserts a runtime check.) *) prval _ = $UNSAFE.prop_assert {0 < x_odd} () prval _ = $UNSAFE.prop_assert {0 < y} ()
val z = main_loop (x_odd, y)
(* Convert back to the non-dependent type. *) val z = g0ofg1 z in (* Put the common factors of two back in. *) (z << nonneg n) end
(* If v < u then swap u and v. This operation does not affect the gcd. *) val u = min (u, v) and v = max (u, v) in if iseqz u then v else u_and_v_both_positive (u, v) end
(* The implementation of g0int_gcd_stein, the template function for
the gcd of two signed integers, giving an unsigned result. *)
implement {signed_tk, unsigned_tk} g0int_gcd_stein (u, v) =
let val abs_u = $UNSAFE.cast{g0uint unsigned_tk} (abs u) val abs_v = $UNSAFE.cast{g0uint unsigned_tk} (abs v) in g0uint_gcd_stein<unsigned_tk> (abs_u, abs_v) end
(********************************************************************) (* A demonstration program. *)
implement main0 () =
begin (* Unsigned integers. *) assertloc (gcd (0U, 10U) = 10U); assertloc (gcd (9UL, 6UL) = 3UL); assertloc (gcd (40902ULL, 24140ULL) = 34ULL);
(* Signed integers. *) assertloc (gcd (0, 10) = gcd (0U, 10U)); assertloc (gcd (~10, 0) = gcd (0U, 10U)); assertloc (gcd (~6L, ~9L) = 3UL); assertloc (gcd (40902LL, 24140LL) = 34ULL); assertloc (gcd (40902LL, ~24140LL) = 34ULL); assertloc (gcd (~40902LL, 24140LL) = 34ULL); assertloc (gcd (~40902LL, ~24140LL) = 34ULL); assertloc (gcd (24140LL, 40902LL) = 34ULL); assertloc (gcd (~24140LL, 40902LL) = 34ULL); assertloc (gcd (24140LL, ~40902LL) = 34ULL); assertloc (gcd (~24140LL, ~40902LL) = 34ULL) end
(********************************************************************)</lang>
Euclid’s algorithm, with proof of termination and correctness
Here is an implementation of Euclid’s algorithm, with a proof of correctness.
<lang ats>(********************************************************************) (*
GCD of two integers, by Euclid’s algorithm; verified with proofs.
Compile with ‘patscc -o gcd gcd.dats’.
- )
- define ATS_DYNLOADFLAG 0 (* No initialization is needed. *)
- include "share/atspre_define.hats"
- include "share/atspre_staload.hats"
(********************************************************************) (* *) (* Definition of the gcd by axioms in the static language. *) (* *) (* (‘Props’ are better supported in ATS, but I enjoy using the *) (* the static language in proofs.) *) (* *)
(* Write the gcd as an undefined static function. It will be defined
implicitly by axioms. (Such a function also can be used with an external SMT solver such as CVC4, but using an external solver is not the topic of this program.) *)
stacst gcd (u : int, v : int) : int
(*
I think the reader will accept the following axioms as valid, if gcd(0, 0) is to be defined as equal to zero.
(An exercise for the reader is to prove ‘gcd_of_remainder’ from gcd (u, v) == gcd (u, v - u). This requires definitions of multiplication and Euclidean division, which are encoded in terms of props in ‘prelude/SATS/arith_prf.sats’.)
- )
extern praxi gcd_of_zero :
{u, v : int | u == 0; 0 <= v} (* For all integers u = 0, v non-negative. *) () -<prf> [gcd (u, v) == v] void
extern praxi gcd_of_remainder :
{u, v : int | 0 < u; 0 <= v} (* For all integers u positive, v non-negative. *) () -<prf> [gcd (u, v) == gcd (u, v mod u)] void
extern praxi gcd_is_commutative :
{u, v : int} (* For all integers u, v. *) () -<prf> [gcd (u, v) == gcd (v, u)] void
extern praxi gcd_of_the_absolute_values :
{u, v : int} (* For all integers u, v. *) () -<prf> [gcd (u, v) == gcd (abs u, abs v)] void
extern praxi gcd_is_a_function :
{u1, v1 : int} {u2, v2 : int | u1 == u2; v1 == v2} () -<prf> [gcd (u1, v1) == gcd (u2, v2)] void
(********************************************************************) (* *) (* Function declarations. *) (* *)
(* g1uint_gcd_euclid will be the generic template function for
unsigned integers. *)
extern fun {tk : tkind} g1uint_gcd_euclid :
{u, v : int} (g1uint (tk, u), g1uint (tk, v)) -<> g1uint (tk, gcd (u, v))
(* g1int_gcd_euclid will be the generic template function for
signed integers, giving an unsigned result. *)
extern fun {tk_signed, tk_unsigned : tkind} g1int_gcd_euclid :
{u, v : int} (g1int (tk_signed, u), g1int (tk_signed, v)) -<> g1uint (tk_unsigned, gcd (u, v))
(* Let us call these functions ‘gcd_euclid’ or just ‘gcd’. *) overload gcd_euclid with g1uint_gcd_euclid overload gcd_euclid with g1int_gcd_euclid overload gcd with gcd_euclid
(********************************************************************) (* *) (* Function implementations. *) (* *)
(* The implementation of the remainder function in the ATS2 prelude
is inconvenient for us; it does not say that the result equals ‘u mod v’. Let us reimplement it more to our liking. *)
fn {tk : tkind} g1uint_rem {u, v : int | v != 0}
(u : g1uint (tk, u), v : g1uint (tk, v)) :<> [w : int | 0 <= w; w < v; w == u mod v] g1uint (tk, w) = let prval _ = lemma_g1uint_param u prval _ = lemma_g1uint_param v in $UNSAFE.cast (g1uint_mod (u, v)) end
implement {tk} g1uint_gcd_euclid {u, v} (u, v) =
let (* The static variable v, which is defined within the curly braces, must, with each iteration, approach zero without passing it. Otherwise the loop is not proven to terminate, and the typechecker will reject it. *) fun loop {u, v : int | 0 <= u; 0 <= v} .<v>. (u : g1uint (tk, u), v : g1uint (tk, v)) :<> g1uint (tk, gcd (u, v)) = if v = g1i2u 0 then let (* prop_verify tests whether what we believe we have proven has actually been proven. Using it a lot lengthens the code but is excellent documentation. *) prval _ = prop_verify {0 <= u} () prval _ = prop_verify {v == 0} ()
prval _ = gcd_of_zero {v, u} () prval _ = prop_verify {gcd (v, u) == u} ()
prval _ = gcd_is_commutative {u, v} () prval _ = prop_verify {gcd (u, v) == gcd (v, u)} ()
(* Therefore, by transitivity of equality: *) prval _ = prop_verify {gcd (u, v) == u} () in u end else let prval _ = prop_verify {0 <= u} () prval _ = prop_verify {0 < v} ()
prval _ = gcd_of_remainder {v, u} () prval _ = prop_verify {gcd (v, u) == gcd (v, u mod v)} ()
prval _ = gcd_is_commutative {u, v} () prval _ = prop_verify {gcd (u, v) == gcd (v, u)} ()
(* Therefore, by transitivity of equality: *) prval _ = prop_verify {gcd (u, v) == gcd (v, u mod v)} ()
val [w : int] w = g1uint_rem (u, v) prval _ = prop_verify {0 <= w} () prval _ = prop_verify {w < v} () prval _ = prop_verify {w == u mod v} ()
(* It has been proven that the function will terminate: *) prval _ = prop_verify {0 <= w && w < v} ()
prval _ = gcd_is_a_function {v, u mod v} {v, w} () prval _ = prop_verify {gcd (v, u mod v) == gcd (v, w)} ()
(* Therefore, by transitivity of equality: *) prval _ = prop_verify {gcd (u, v) == gcd (v, w)} () in loop (v, w) end
(* u is unsigned, thus proving 0 <= u. *) prval _ = lemma_g1uint_param (u)
(* v is unsigned, thus proving 0 <= v. *) prval _ = lemma_g1uint_param (v) in loop (u, v) end
implement {tk_signed, tk_unsigned} g1int_gcd_euclid {u, v} (u, v) =
let (* Prove that gcd(abs u, abs v) equals gcd(u, v). *) prval _ = gcd_of_the_absolute_values {u, v} () in (* Compute gcd(abs u, abs v). The ‘g1i2u’ notations cast the values from signed integers to unsigned integers. *) g1uint_gcd_euclid (g1i2u (abs u), g1i2u (abs v)) end
(********************************************************************) (* *) (* A demonstration program. *) (* *) (* Unfortunately, the ATS prelude may not include implementations *) (* of all the functions we need for long and long long integers. *) (* Thus the demonstration will be entirely on regular int and uint. *) (* *) (* (Including implementations here would distract from the purpose. *) (* *)
implement main0 () =
begin (* Unsigned integers. *) assertloc (gcd (0U, 10U) = 10U); assertloc (gcd (9U, 6U) = 3U); assertloc (gcd (40902U, 24140U) = 34U);
(* Signed integers. *) assertloc (gcd (0, 10) = gcd (0U, 10U)); assertloc (gcd (~10, 0) = gcd (0U, 10U)); assertloc (gcd (~6, ~9) = 3U); assertloc (gcd (40902, 24140) = 34U); assertloc (gcd (40902, ~24140) = 34U); assertloc (gcd (~40902, 24140) = 34U); assertloc (gcd (~40902, ~24140) = 34U); assertloc (gcd (24140, 40902) = 34U); assertloc (gcd (~24140, 40902) = 34U); assertloc (gcd (24140, ~40902) = 34U); assertloc (gcd (~24140, ~40902) = 34U) end
(********************************************************************)</lang>
Some proofs about the gcd
For the sake of interest, here is some use of ATS's "props"-based proof system. There is no executable code in the following.
<lang ats>(* Typecheck this file with ‘patscc -tcats gcd-proofs.dats’. *)
(* Definition of the gcd by Euclid’s algorithm, using subtractions;
gcd(0,0) is defined to equal zero. (I do not prove that this definition is equivalent to the common meaning of ‘greatest common divisor’; that’s not a sort of thing ATS is good at.) *)
dataprop GCD (int, int, int) = | GCD_0_0 (0, 0, 0) | {u : pos}
GCD_u_0 (u, 0, u)
| {v : pos}
GCD_0_v (0, v, v)
| {u, v : pos | u <= v}
{d : pos} GCD_u_le_v (u, v, d) of GCD (u, v - u, d)
| {u, v : pos | u > v}
{d : pos} GCD_u_gt_v (u, v, d) of GCD (u - v, v, d)
| {u, v : int | u < 0 || v < 0}
{d : pos} GCD_u_or_v_neg (u, v, d) of GCD (abs u, abs v, d)
(* Here is a proof, by construction, of the proposition
‘The gcd of 12 and 8 is 4’. *)
prfn gcd_12_8 () :<prf>
GCD (12, 8, 4) = let prval pf = GCD_u_0 {4} () prval pf = GCD_u_le_v {4, 4} {4} (pf) prval pf = GCD_u_le_v {4, 8} {4} (pf) prval pf = GCD_u_gt_v {12, 8} {4} (pf) in pf end
(* A lemma: the gcd is total. That is, it is defined for all
integers. *)
extern prfun gcd_istot :
{u, v : int} () -<prf> [d : int] GCD (u, v, d)
(* Another lemma: the gcd is a function: it has a unique value for
any given pair of arguments. *)
extern prfun gcd_isfun :
{u, v : int} {d, e : int} (GCD (u, v, d), GCD (u, v, e)) -<prf> [d == e] void
(* Proof of gcd_istot. This source file will not pass typechecking
unless the proof is valid. *)
primplement gcd_istot {u, v} () =
let prfun gcd_istot__nat_nat__ {u, v : nat | u != 0 || v != 0} .. () :<prf> [d : pos] GCD (u, v, d) = sif v == 0 then GCD_u_0 () else sif u == 0 then GCD_0_v () else sif u <= v then GCD_u_le_v (gcd_istot__nat_nat__ {u, v - u} ()) else GCD_u_gt_v (gcd_istot__nat_nat__ {u - v, v} ())
prfun gcd_istot__int_int__ {u, v : int | u != 0 || v != 0} .<>. () :<prf> [d : pos] GCD (u, v, d) = sif u < 0 || v < 0 then GCD_u_or_v_neg (gcd_istot__nat_nat__ {abs u, abs v} ()) else gcd_istot__nat_nat__ {u, v} () in sif u == 0 && v == 0 then GCD_0_0 () else gcd_istot__int_int__ {u, v} () end
(* Proof of gcd_isfun. This source file will not pass typechecking
unless the proof is valid. *)
primplement gcd_isfun {u, v} {d, e} (pfd, pfe) =
let prfun gcd_isfun__nat_nat__ {u, v : nat} {d, e : int} .. (pfd : GCD (u, v, d), pfe : GCD (u, v, e)) :<prf> [d == e] void = case+ pfd of | GCD_0_0 () => { prval GCD_0_0 () = pfe } | GCD_u_0 () => { prval GCD_u_0 () = pfe } | GCD_0_v () => { prval GCD_0_v () = pfe } | GCD_u_le_v pfd1 => { prval GCD_u_le_v pfe1 = pfe prval _ = gcd_isfun__nat_nat__ (pfd1, pfe1) } | GCD_u_gt_v pfd1 => { prval GCD_u_gt_v pfe1 = pfe prval _ = gcd_isfun__nat_nat__ (pfd1, pfe1) } in sif u < 0 || v < 0 then { prval GCD_u_or_v_neg pfd1 = pfd prval GCD_u_or_v_neg pfe1 = pfe prval _ = gcd_isfun__nat_nat__ (pfd1, pfe1) } else gcd_isfun__nat_nat__ (pfd, pfe) end</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> Significantly faster than recursion: <lang AutoHotkey>GCD(a, b) {
while b b := Mod(a | 0x0, a := b) return a
}</lang>
AutoIt
<lang autoit> _GCD(18, 12) _GCD(1071, 1029) _GCD(3528, 3780)
Func _GCD($ia, $ib) Local $ret = "GCD of " & $ia & " : " & $ib & " = " Local $imod While True $imod = Mod($ia, $ib) If $imod = 0 Then Return ConsoleWrite($ret & $ib & @CRLF) $ia = $ib $ib = $imod WEnd EndFunc ;==>_GCD </lang>
Output:
GCD of 18 : 12 = 6 GCD of 1071 : 1029 = 21 GCD of 3528 : 3780 = 252
AWK
The following scriptlet defines the gcd() function, then reads pairs of numbers from stdin, and reports their gcd on stdout. <lang awk>$ awk 'function gcd(p,q){return(q?gcd(q,(p%q)):p)}{print gcd($1,$2)}' 12 16 4 22 33 11 45 67 1</lang>
Axe
<lang axe>Lbl GCD r₁→A r₂→B !If B
A Return
End GCD(B,A^B)</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>
IS-BASIC
<lang IS-BASIC>100 DEF GCD(A,B) 110 DO WHILE B>0 120 LET T=B 130 LET B=MOD(A,B) 140 LET A=T 150 LOOP 160 LET GCD=A 170 END DEF 180 PRINT GCD(12,16)</lang>
Sinclair ZX81 BASIC
<lang basic> 10 LET M=119
20 LET N=544 30 LET R=M-N*INT (M/N) 40 IF R=0 THEN GOTO 80 50 LET M=N 60 LET N=R 70 GOTO 30 80 PRINT N</lang>
- Output:
17
BASIC256
Solución iterativa
<lang freebasic> function gcdI(x, y) while y t = y y = x mod y x = t end while
return x end function
- ------ test ------
a = 111111111111111 b = 11111
print : print "GCD(";a;", ";b;") = "; gcdI(a, b) print : print "GCD(";a;", 111) = "; gcdI(a, 111) end</lang>
- Output:
Igual que la entrada de FreeBASIC.
Solución recursiva
<lang freebasic> function gcdp(a, b) if b = 0 then return a return gcdp(b, a mod b) end function
function gcdR(a, b) return gcdp(abs(a), abs(b)) end function </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>
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>
BCPL
<lang bcpl>get "libhdr"
let gcd(m,n) = n=0 -> m, gcd(n, m rem n)
let show(m,n) be
writef("gcd(%N, %N) = %N*N", m, n, gcd(m, n))
let start() be $( show(18,12)
show(1071,1029) show(3528,3780)
$)</lang>
- Output:
gcd(18, 12) = 6 gcd(1071, 1029) = 21 gcd(3528, 3780) = 252
Befunge
<lang befunge>#v&< @.$<
- <\g05%p05:_^#</lang>
BQN
<lang bqn>Gcd ← {𝕨(|𝕊⍟(>⟜0)⊣)𝕩}</lang>
Example: <lang bqn>21 Gcd 35</lang>
7
Bracmat
Bracmat uses the Euclidean algorithm to simplify fractions. The den
function extracts the denominator from a fraction.
<lang bracmat>(gcd=a b.!arg:(?a.?b)&!b*den$(!a*!b^-1)^-1);</lang>
Example:
{?} gcd$(49865.69811) {!} 9973
C
Iterative Euclid algorithm
<lang c>int gcd_iter(int u, int v) {
if (u < 0) u = -u; if (v < 0) v = -v; if (v) while ((u %= v) && (v %= u)); return (u + v);
}</lang>
Recursive Euclid algorithm
<lang c>int gcd(int u, int v) { return (v != 0)?gcd(v, u%v):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>
C#
Iterative
<lang csharp> static void Main() { 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(); }
/// <summary> /// Greatest Common Denominator using Euclidian Algorithm /// </summary> static int gcd(int a, int b) {
while (b != 0) b = a % (a = b); 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
Recursive
<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(); }
// Greatest Common Denominator using Euclidian Algorithm // Gist: https://gist.github.com/SecretDeveloper/6c426f8993873f1a05f7 static int gcd(int a, int b) { return b==0 ? a : gcd(b, a % b); } </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
C++
<lang cpp>#include <iostream>
- include <numeric>
int main() {
std::cout << "The greatest common divisor of 12 and 18 is " << std::gcd(12, 18) << " !\n";
}</lang>
<lang cpp>#include <boost/math/common_factor.hpp>
- include <iostream>
int main() {
std::cout << "The greatest common divisor of 12 and 18 is " << boost::math::gcd(12, 18) << "!\n";
}</lang>
- Output:
The greatest common divisor of 12 and 18 is 6!
Clojure
Euclid's Algorithm
<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))))</lang>
That recur
call is the same as (gcd b (mod a b))
, but makes use of Clojure's explicit tail call optimization.
This can be easily extended to work with variadic arguments:
<lang lisp>(defn gcd*
"greatest common divisor of a list of numbers" [& lst] (reduce gcd lst))</lang>
Stein's Algorithm (Binary GCD)
<lang lisp>(defn stein-gcd [a b]
(cond (zero? a) b (zero? b) a (and (even? a) (even? b)) (* 2 (stein-gcd (unsigned-bit-shift-right a 1) (unsigned-bit-shift-right b 1))) (and (even? a) (odd? b)) (recur (unsigned-bit-shift-right a 1) b) (and (odd? a) (even? b)) (recur a (unsigned-bit-shift-right b 1)) (and (odd? a) (odd? b)) (recur (unsigned-bit-shift-right (Math/abs (- a b)) 1) (min a b))))</lang>
CLU
<lang clu>gcd = proc (a, b: int) returns (int)
while b~=0 do a, b := b, a//b end return(a)
end gcd
start_up = proc()
po: stream := stream$primary_input() as: array[int] := array[int]$[18, 1071, 3528] bs: array[int] := array[int]$[12, 1029, 3780] for i: int in array[int]$indexes(as) do stream$putl(po, "gcd(" || int$unparse(as[i]) || ", " || int$unparse(bs[i]) || ") = " || int$unparse(gcd(as[i], bs[i]))) end
end start_up</lang>
- Output:
gcd(18, 12) = 6 gcd(1071, 1029) = 21 gcd(3528, 3780) = 252
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>
Cobra
<lang cobra> class Rosetta def gcd(u as number, v as number) as number u, v = u.abs, v.abs while v > 0 u, v = v, u % v return u
def main print "gcd of [12] and [8] is [.gcd(12, 8)]" print "gcd of [12] and [-8] is [.gcd(12, -8)]" print "gcd of [96] and [27] is [.gcd(27, 96)]" print "gcd of [51] and [34] is [.gcd(34, 51)]" </lang>
Output:
gcd of 12 and 8 is 4 gcd of 12 and -8 is 4 gcd of 96 and 27 is 3 gcd of 51 and 34 is 17
CoffeeScript
Simple recursion <lang coffeescript> gcd = (x, y) ->
if y == 0 then x else gcd y, x % y
</lang>
Since JS has no TCO, here's a version with no recursion <lang coffeescript> gcd = (x, y) ->
[1..(Math.min x, y)].reduce (acc, v) -> if x % v == 0 and y % v == 0 then v else acc
</lang>
Common Lisp
Common Lisp provides a gcd function.
<lang lisp>CL-USER> (gcd 2345 5432) 7</lang>
Here is an implementation using the do macro. We call the function gcd*
so as not to conflict with common-lisp:gcd
.
<lang lisp>(defun gcd* (a b)
(do () ((zerop b) (abs a)) (shiftf a b (mod a b))))</lang>
Here is a tail-recursive implementation.
<lang lisp>(defun gcd* (a b)
(if (zerop b) a (gcd2 b (mod a b))))</lang>
The last implementation is based on the loop macro.
<lang lisp>(defun gcd* (a b)
(loop for x = a then y and y = b then (mod x y) until (zerop y) finally (return x)))</lang>
Component Pascal
BlackBox Component Builder <lang oberon2> MODULE Operations; IMPORT StdLog,Args,Strings;
PROCEDURE Gcd(a,b: LONGINT):LONGINT; VAR r: LONGINT; BEGIN LOOP r := a MOD b; IF r = 0 THEN RETURN b END; a := b;b := r END END Gcd;
PROCEDURE DoGcd*; VAR x,y,done: INTEGER; p: Args.Params; BEGIN Args.Get(p); IF p.argc >= 2 THEN Strings.StringToInt(p.args[0],x,done); Strings.StringToInt(p.args[1],y,done); StdLog.String("gcd("+p.args[0]+","+p.args[1]+")=");StdLog.Int(Gcd(x,y));StdLog.Ln END END DoGcd;
END Operations.
</lang>
Execute:
^Q Operations.DoGcd 12 8 ~
^Q Operations.DoGcd 100 5 ~
^Q Operations.DoGcd 7 23 ~
^Q Operations.DoGcd 24 -112 ~
Output:
gcd(12 ,8 )= 4 gcd(100 ,5 )= 5 gcd(7 ,23 )= 1 gcd(24 ,-112 )= -8
D
<lang d>import std.stdio, std.numeric;
long myGCD(in long x, in long y) pure nothrow @nogc {
if (y == 0) return x; return myGCD(y, x % y);
}
void main() {
gcd(15, 10).writeln; // From Phobos. myGCD(15, 10).writeln;
}</lang>
- Output:
5 5
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'
Delphi
See #Pascal / Delphi / Free Pascal.
Draco
<lang draco>proc nonrec gcd(word m, n) word:
word t; while n ~= 0 do t := m; m := n; n := t % n od; m
corp
proc nonrec show(word m, n) void:
writeln("gcd(", m, ", ", n, ") = ", gcd(m, n))
corp
proc nonrec main() void:
show(18, 12); show(1071, 1029); show(3528, 3780)
corp</lang>
- Output:
gcd(18, 12) = 6 gcd(1071, 1029) = 21 gcd(3528, 3780) = 252
DWScript
<lang delphi>PrintLn(Gcd(231, 210));</lang> Output:
21
Dyalect
<lang dyalect>func gcd(a, b) {
func bgcd(a, b, res) { if a == b { return res * a } else if a % 2 == 0 && b % 2 == 0 { return bgcd(a/2, b/2, 2*res) } else if a % 2 == 0 { return bgcd(a/2, b, res) } else if b % 2 == 0 { return bgcd(a, b/2, res) } else if a > b { return bgcd(a-b, b, res) } else { return bgcd(a, b-a, res) } } return bgcd(a, b, 1)
}
var testdata = [
(a: 33, b: 77), (a: 49865, b: 69811)
]
for v in testdata {
print("gcd(\(v.a), \(v.b)) = \(gcd(v.a, v.b))")
}</lang>
- Output:
gcd(33, 77) = 11 gcd(49865, 69811) = 9973
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>
EasyLang
<lang>func gcd a b . res .
while b <> 0 h = b b = a mod b a = h . res = a
. call gcd 120 35 r print r</lang>
EDSAC order code
The EDSAC had no division instruction, so the GCD routine below has to include its own code for division. <lang edsac>
[Greatest common divisor for Rosetta Code. Program for EDSAC, Initial Orders 2.]
[Library subroutine R2. Reads positive integers during input of orders, and is then overwritten (so doesn't take up any memory). Negative numbers can be input by adding 2^35. Each integer is followed by 'F', except the last is followed by '#TZ'.] T 45 K [store address in location 45 values are then accessed by code letter H] P 220 F [<------ address here] GKT20FVDL8FA40DUDTFI40FA40FS39FG@S2FG23FA5@T5@E4@E13Z T #H [Tell R2 the storage location defined above]
[Integers to be read by R2. First item is count, then pairs for GCD algo.] 4F 1066F 2019F 1815F 1914F 103785682F 167928761F 109876463F 177777648#TZ
[---------------------------------------------------------------------- Library subroutine P7. Prints long strictly positive integer at 0D. 10 characters, right justified, padded left with spaces. Closed, even; 35 storage locations; working position 4D.] T 56 K GKA3FT26@H28#@NDYFLDT4DS27@TFH8@S8@T1FV4DAFG31@SFLDUFOFFFSFL4F T4DA1FA27@G11@XFT28#ZPFT27ZP1024FP610D@524D!FO30@SFL8FE22@
[--------------------------------------------------------------- Subroutine to return GCD of two non-negative 35-bit integers. Input: Integers at 4D, 6D. Output: GCD at 4D; changes 6D. 41 locations; working location 0D.] T 100 K G K A 3 F [plant link] T 39 @ S 4 D [test for 4D = 0] E 37 @ [if so, quick exit, GCD = 6D] T 40 @ [clear acc] [5] A 4 D [load divisor] [6] T D [initialize shifted divisor] A 6 D [load dividend] R D [shift 1 right] S D [shifted divisor > dividend/2 yet?] G 15 @ [yes, start subtraction] T 40 @ [no, clear acc] A D [shift divisor 1 more] L D E 6 @ [loop back (always, since acc = 0)] [15] T 40 @ [clear acc] [16] A 6 D [load remainder (initially = dividend)] S D [trial subtraction] G 20 @ [skip if can't subtract] T 6 D [update remainder] [20] T 40 @ [clear acc] A 4 D [load original divisor] S D [is shifted divisor back to original?] E 29 @ [yes, jump out with acc = 0] T 40 @ [no, clear acc] A D [shift divisor 1 right] R D T D E 16 @ [loop back (always, since acc = 0)] [Here when finished dividing 6D by 4D. Remainder is at 6D; acc = 0.] [29] S 6 D [test for 6D = 0] E 39 @ [if so, exit with GCD in 4D] T D [else swap 4D and 6D] A 4 D T 6 D S D T 4 D E 5 @ [loop back] [37] A 6 D [here if 4D = 0 at start; GCD is 6D] T 4 D [return in 4D as GCD] [39] E F [40] P F [junk word, to clear accumulator] [---------------------------------------------------------------------- Main routine] T 150 K G K [Variable] [0] P F [Constants] [1] P D [single-word 1] [2] A 2#H [order to load first number of first pair] [3] P 2 F [to inc addresses by 2] [4] # F [figure shift] [5] K 2048 F [letter shift] [6] G F [letters to print 'GCD'] [7] C F [8] D F [9] V F [equals sign (in figures mode)] [10] ! F [space] [11] @ F [carriage return] [12] & F [line feed] [13] K 4096 F [null char] [Enter here with acc = 0] [14] O 4 @ [set teleprinter to figures] S H [negative of number of pairs] T @ [initialize counter] A 2 @ [initial load order] [18] U 23 @ [plant order to load 1st integer] U 32 @ A 3 @ [inc address by 2] U 28 @ [plant order to load 2nd integer] T 34 @ [23] A #H [load 1st integer (order set up at runtime)] T D [to 0D for printing] A 25 @ [for return from print subroutine] G 56 F [print 1st number] O 10 @ [followed by space] [28] A #H [load 2nd integer (order set up at runtime)] T D [to 0D for printing] A 30 @ [for return from print subroutine] G 56 F [print 2nd number] [32] A #H [load 1st integer (order set up at runtime)] T 4 D [to 4D for GCD subroutine] [34] A #H [load 2nd integer (order set up at runtime)] T 6 D [to 6D for GCD subroutine] [36] A 36 @ [for return from subroutine] G 100 F [call subroutine for GCD] [Cosmetic printing, add ' GCD = '] O 10 @ O 10 @ O 5 @ O 6 @ O 7 @ O 8 @ O 4 @ O 10 @ O 9 @ O 10 @ A 4 D [load GCD] T D [to 0D for printing] A 50 @ [for return from print subroutine] G 56 F [print GCD] O 11 @ [followed by new line] O 12 @ [On to next pair] A @ [load negative count of c.f.s] A 1 @ [add 1] E 62 @ [exit if count = 0] T @ [store back] A 23 @ [order to load first of pair] A 3 @ [inc address by 4 for next c.f.] A 3 @ G 18 @ [loop back (always, since 'A' < 0)] [62] O 13 @ [null char to flush teleprinter buffer] Z F [stop] E 14 Z [define entry point] P F [acc = 0 on entry]
</lang>
- Output:
1066 2019 GCD = 1 1815 1914 GCD = 33 103785682 167928761 GCD = 1001 109876463 177777648 GCD = 1234567
Eiffel
<lang eiffel> class APPLICATION
create make
feature -- Implementation
gcd (x: INTEGER y: INTEGER): INTEGER do if y = 0 then Result := x else Result := gcd (y, x \\ y); end end
feature {NONE} -- Initialization
make -- Run application. do print (gcd (15, 10)) print ("%N") end
end </lang>
Elena
ELENA 4.x : <lang elena>import system'math; import extensions;
gcd(a,b) {
var i := a; var j := b; while(j != 0) { var tmp := i; i := j; j := tmp.mod(j) }; ^ i
}
printGCD(a,b) {
console.printLineFormatted("GCD of {0} and {1} is {2}", a, b, gcd(a,b))
}
public program() {
printGCD(1,1); printGCD(1,10); printGCD(10,100); printGCD(5,50); printGCD(8,24); printGCD(36,17); printGCD(36,18); printGCD(36,19); printGCD(36,33);
}</lang>
- 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 17 is 1 GCD of 36 and 18 is 18 GCD of 36 and 19 is 1 GCD of 36 and 33 is 3
Elixir
<lang elixir>defmodule RC do
def gcd(a,0), do: abs(a) def gcd(a,b), do: gcd(b, rem(a,b))
end
IO.puts RC.gcd(1071, 1029) IO.puts RC.gcd(3528, 3780)</lang>
- Output:
21 252
Emacs Lisp
<lang lisp>(defun gcd (a b)
(cond ((< a b) (gcd a (- b a))) ((> a b) (gcd (- a b) b)) (t a)))</lang>
Erlang
<lang erlang>% Implemented by Arjun Sunel -module(gcd). -export([main/0]).
main() ->gcd(-36,4).
gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, A rem B).</lang>
- Output:
4
ERRE
This is a iterative version. <lang ERRE> PROGRAM EUCLIDE ! calculate G.C.D. between two integer numbers ! using Euclidean algorithm
!VAR J%,K%,MCD%,A%,B%
BEGIN
PRINT(CHR$(12);"Input two numbers : ";) !CHR$(147) in C-64 version INPUT(J%,K%) A%=J% B%=K% WHILE A%<>B% DO IF A%>B% THEN A%=A%-B% ELSE B%=B%-A% END IF END WHILE MCD%=A% PRINT("G.C.D. between";J%;"and";K%;"is";MCD%)
END PROGRAM </lang>
- Output:
Input two numbers : ? 112,44 G.C.D. between 112 and 44 is 4
Euler Math Toolbox
Non-recursive version in Euler Math Toolbox. Note, that there is a built-in command.
<lang> >ggt(123456795,1234567851)
33
>function myggt (n:index, m:index) ... $ if n<m then {n,m}={m,n}; endif; $ repeat $ k=mod(n,m); $ if k==0 then return m; endif; $ if k==1 then return 1; endif; $ {n,m}={m,k}; $ end; $ endfunction >myggt(123456795,1234567851)
33
</lang>
Euphoria
Iterative Euclid algorithm
<lang euphoria>function gcd_iter(integer u, integer v)
integer t while v do t = u u = v v = remainder(t, v) end while if u < 0 then return -u else return u end if
end function</lang>
Recursive Euclid algorithm
<lang euphoria>function gcd(integer u, integer v)
if v then return gcd(v, remainder(u, v)) elsif u < 0 then return -u else return u end if
end function</lang>
Iterative binary algorithm
<lang euphoria>function gcd_bin(integer u, integer v)
integer t, k if u < 0 then -- abs(u) u = -u end if if v < 0 then -- abs(v) v = -v end if if u < v then t = u u = v v = t end if if v = 0 then return u end if k = 1 while and_bits(u,1) = 0 and and_bits(v,1) = 0 do u = floor(u/2) -- u >>= 1 v = floor(v/2) -- v >>= 1 k *= 2 -- k <<= 1 end while if and_bits(u,1) then t = -v else t = u end if while t do while and_bits(t, 1) = 0 do t = floor(t/2) end while if t > 0 then u = t else v = -t end if t = u - v end while return u * k
end function</lang>
Excel
Excel's GCD can handle multiple values. Type in a cell: <lang excel>=GCD(A1:E1)</lang>
- Sample Output:
This will get the GCD of the first 5 cells of the first row.
30 10 500 25 1000 5
Ezhil
<lang Ezhil>
- இந்த நிரல் இரு எண்களுக்கு இடையிலான மீச்சிறு பொது மடங்கு (LCM), மீப்பெரு பொது வகுத்தி (GCD) என்ன என்று கணக்கிடும்
நிரல்பாகம் மீபொவ(எண்1, எண்2)
@(எண்1 == எண்2) ஆனால்
## இரு எண்களும் சமம் என்பதால், அந்த எண்ணேதான் அதன் மீபொவ
பின்கொடு எண்1
@(எண்1 > எண்2) இல்லைஆனால்
சிறியது = எண்2 பெரியது = எண்1
இல்லை
சிறியது = எண்1 பெரியது = எண்2
முடி
மீதம் = பெரியது % சிறியது
@(மீதம் == 0) ஆனால்
## பெரிய எண்ணில் சிறிய எண் மீதமின்றி வகுபடுவதால், சிறிய எண்தான் மீப்பெரு பொதுவகுத்தியாக இருக்கமுடியும்
பின்கொடு சிறியது
இல்லை
தொடக்கம் = சிறியது - 1
நிறைவு = 1
@(எண் = தொடக்கம், எண் >= நிறைவு, எண் = எண் - 1) ஆக
மீதம்1 = சிறியது % எண்
மீதம்2 = பெரியது % எண்
## இரு எண்களையும் மீதமின்றி வகுக்கக்கூடிய பெரிய எண்ணைக் கண்டறிகிறோம்
@((மீதம்1 == 0) && (மீதம்2 == 0)) ஆனால்
பின்கொடு எண்
முடி
முடி
முடி
முடி
அ = int(உள்ளீடு("ஓர் எண்ணைத் தாருங்கள் ")) ஆ = int(உள்ளீடு("இன்னோர் எண்ணைத் தாருங்கள் "))
பதிப்பி "நீங்கள் தந்த இரு எண்களின் மீபொவ (மீப்பெரு பொது வகுத்தி, GCD) = ", மீபொவ(அ, ஆ) </lang>
F#
<lang fsharp> let rec gcd a b =
if b = 0 then abs a else 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>10 15$ [0=~][$@$@$@\/*-$]#%. { gcd(10,15)=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>
Fermat
<lang fermat>GCD(a,b)</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
Iterative binary algorithm in Fortran 2008
Fortran 2008 introduces new intrinsic functions for integer operations that nowadays usually have hardware support, such as TRAILZ to count trailing zeros. <lang fortran>! Stein’s algorithm implemented in Fortran 2008. ! Translated from my implementation for ATS/Postiats.
elemental function gcd (u, v) result (d)
implicit none integer, intent(in) :: u, v integer :: d
integer :: x, y
! gcd(x,y) = gcd(u,v), but x and y are non-negative and x <= y. x = min (abs (u), abs (v)) y = max (abs (u), abs (v))
if (x == 0) then d = y else d = gcd_pos_pos (x, y) end if
contains
elemental function gcd_pos_pos (u, v) result (d) integer, intent(in) :: u, v integer :: d
integer :: n integer :: x, y integer :: p, q
! n = the number of common factors of two in u and v. n = trailz (ior (u, v))
! Remove the common twos from u and v, giving x and y. x = ishft (u, -n) y = ishft (v, -n)
! Make both numbers odd. One of the numbers already was odd. ! There is no effect on the value of their gcd. x = ishft (x, -trailz (x)) y = ishft (y, -trailz (y))
do while (x /= y) ! If x > y then swap x and y, renaming them p ! and q. Thus p <= q, and gcd(p,q) = gcd(x,y). p = min (x, y) q = max (x, y)
x = p ! x remains odd. q = q - p y = ishft (q, -trailz (q)) ! Make y odd again. end do
! Put the common twos back in. d = ishft (x, n) end function gcd_pos_pos
end function gcd
program test_gcd
implicit none
interface elemental function gcd (u, v) result (d) integer, intent(in) :: u, v integer :: d end function gcd end interface
write (*, '("gcd (0, 0) = ", I0)') gcd (0, 0) write (*, '("gcd (0, 10) = ", I0)') gcd (0, 10) write (*, '("gcd (-6, -9) = ", I0)') gcd (-6, -9) write (*, '("gcd (64 * 5, -16 * 3) = ", I0)') gcd (64 * 5, -16 * 3) write (*, '("gcd (40902, 24140) = ", I0)') gcd (40902, 24140) write (*, '("gcd (-40902, 24140) = ", I0)') gcd (-40902, 24140) write (*, '("gcd (40902, -24140) = ", I0)') gcd (40902, -24140) write (*, '("gcd (-40902, -24140) = ", I0)') gcd (-40902, -24140) write (*, '("gcd (24140, 40902) = ", I0)') gcd (24140, 40902)
end program test_gcd</lang>
- Output:
gcd (0, 0) = 0 gcd (0, 10) = 10 gcd (-6, -9) = 3 gcd (64 * 5, -16 * 3) = 16 gcd (40902, 24140) = 34 gcd (-40902, 24140) = 34 gcd (40902, -24140) = 34 gcd (-40902, -24140) = 34 gcd (24140, 40902) = 34
Free Pascal
See #Pascal / Delphi / Free Pascal.
FreeBASIC
Iterative solution
<lang FreeBASIC>' version 17-06-2015 ' compile with: fbc -s console
Function gcd(x As ULongInt, y As ULongInt) As ULongInt
Dim As ULongInt t
While y t = y y = x Mod y x = t Wend
Return x
End Function
' ------=< MAIN >=------
Dim As ULongInt a = 111111111111111 Dim As ULongInt b = 11111
Print : Print "GCD(";a;", ";b;") = "; gcd(a, b) Print : Print "GCD(";a;", 111) = "; gcd(a, 111)
' empty keyboard buffer While InKey <> "" : Wend Print : Print : Print "hit any key to end program" Sleep End</lang>
- Output:
GCD(111111111111111, 11111) = 11111 GCD(111111111111111, 111) = 111
Recursive solution
<lang freebasic>function gcdp( a as uinteger, b as uinteger ) as uinteger
if b = 0 then return a return gcdp( b, a mod b )
end function
function gcd(a as integer, b as integer) as uinteger
return gcdp( abs(a), abs(b) )
end function</lang>
Frege
<lang fsharp>module gcd.GCD where
pure native parseInt java.lang.Integer.parseInt :: String -> Int
gcd' a 0 = a gcd' a b = gcd' b (a `mod` b)
main args = do
(a:b:_) = args println $ gcd' (parseInt a) (parseInt b)
</lang>
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>
FunL
FunL has pre-defined function gcd
in module integers
defined as:
<lang funl>def
gcd( 0, 0 ) = error( 'integers.gcd: gcd( 0, 0 ) is undefined' ) gcd( a, b ) = def _gcd( a, 0 ) = a _gcd( a, b ) = _gcd( b, a%b )
_gcd( abs(a), abs(b) )</lang>
FutureBasic
<lang futurebasic>window 1, @"Greatest Common Divisor", (0,0,480,270)
local fn gcd( a as short, b as short ) as short
short result if ( b != 0 ) result = fn gcd( b, a mod b) else result = abs(a) end if
end fn = result
print fn gcd( 6, 9 )
HandleEvents</lang>
GAP
<lang gap># Built-in GcdInt(35, 42);
- 7
- Euclidean algorithm
GcdInteger := function(a, b)
local c; a := AbsInt(a); b := AbsInt(b); while b > 0 do c := a; a := b; b := RemInt(c, b); od; return a;
end;
GcdInteger(35, 42);
- 7</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>
GFA Basic
<lang basic> ' ' Greatest Common Divisor ' a%=24 b%=112 PRINT "GCD of ";a%;" and ";b%;" is ";@gcd(a%,b%) ' ' Function computes gcd ' FUNCTION gcd(a%,b%)
LOCAL t% ' WHILE b%<>0 t%=a% a%=b% b%=t% MOD b% WEND ' RETURN ABS(a%)
ENDFUNC </lang>
GML
<lang GML>
var n,m,r; n = max(argument0,argument1); m = min(argument0,argument1); while (m != 0) { r = n mod m; n = m; m = r; } return a;
</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
Binary Euclidian
<lang go>package main
import "fmt"
func gcd(a, b int) int {
var bgcd func(a, b, res int) int
bgcd = func(a, b, res int) int {
switch { case a == b: return res * a case a % 2 == 0 && b % 2 == 0: return bgcd(a/2, b/2, 2*res) case a % 2 == 0: return bgcd(a/2, b, res) case b % 2 == 0: return bgcd(a, b/2, res) case a > b: return bgcd(a-b, b, res) default: return bgcd(a, b-a, res) }
}
return bgcd(a, b, 1)
}
func main() {
type pair struct {
a int b int
}
var testdata []pair = []pair{
pair{33, 77}, pair{49865, 69811},
}
for _, v := range testdata {
fmt.Printf("gcd(%d, %d) = %d\n", v.a, v.b, gcd(v.a, v.b))
}
} </lang>
- Output for Binary Euclidian algorithm:
gcd(33, 77) = 11 gcd(49865, 69811) = 9973
Iterative
<lang go>package main
import "fmt"
func gcd(x, y int) int {
for y != 0 { x, y = y, x%y } return x
}
func main() {
fmt.Println(gcd(33, 77)) fmt.Println(gcd(49865, 69811))
} </lang>
Builtin
(This is just a wrapper for big.GCD) <lang go>package main
import (
"fmt" "math/big"
)
func gcd(x, y int64) int64 {
return new(big.Int).GCD(nil, nil, big.NewInt(x), big.NewInt(y)).Int64()
}
func main() {
fmt.Println(gcd(33, 77)) fmt.Println(gcd(49865, 69811))
}</lang>
- Output in either case:
11 9973
Golfscript
<lang golfscript>;'2706 410' ~{.@\%.}do;</lang>
- Output:
82
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
GW-BASIC
<lang gwbasic>10 INPUT A, B 20 IF A < 0 THEN A = -A 30 IF B < 0 THEN B = -B 40 GOTO 70 50 PRINT A 60 END 70 IF B = 0 THEN GOTO 50 80 TEMP = B 90 B = A MOD TEMP 100 A = TEMP 110 GOTO 70</lang>
Haskell
That is already available as the function gcd in the Prelude. Here's the implementation, with one name adjusted to avoid a Wiki formatting glitch:
<lang haskell>gcd :: (Integral a) => a -> a -> a 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 -- among other things, GCD and boolean OR both have the same identity element: 0, and of course they produce the same numeric results on the same arguments (when we are allowed to use the usual 1 bit implementation of 0 and 1 for false and true) - more than that, though, GCD corresponds to George Boole's original "Boolean Algebra" (as it was later called). The redefinition of "Boolean algebra" to include logical negation came much later, in the 20th century).
gcd could also be defined recursively, if you do not mind a little inefficiency:
<lang J>gcd=: (| gcd [)^:(0<[)&|</lang>
Java
Iterative
<lang java>public static long gcd(long a, long b){
long factor= Math.min(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>
Optimized Iterative
<lang java> static int gcd(int a,int b) { int min=a>b?b:a,max=a+b-min, div=min; for(int i=1;i<min;div=min/++i) if(min%div==0&&max%div==0) return div; return 1; } </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>
Built-in
<lang java>import java.math.BigInteger;
public static long gcd(long a, long b){
return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).longValue();
}</lang>
JavaScript
Iterative implementation <lang javascript>function gcd(a,b) {
a = Math.abs(a); b = Math.abs(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) {
return b ? gcd_rec(b, a % b) : Math.abs(a);
}</lang>
Implementation that works on an array of integers. <lang javascript>function GCD(arr) {
var i, y, n = arr.length, x = Math.abs(arr[0]);
for (i = 1; i < n; i++) { y = Math.abs(arr[i]);
while (x && y) { (x > y) ? x %= y : y %= x; } x += y; } return x;
}
//For example: GCD([57,0,-45,-18,90,447]); //=> 3 </lang>
Joy
DEFINE gcd == [0 >] [dup rollup rem] while pop.
jq
<lang jq>def recursive_gcd(a; b):
if b == 0 then a else recursive_gcd(b; a % b) end ;</lang>Recent versions of jq include support for tail recursion optimization for arity-0 filters (which can be thought of as arity-1 functions), so here is an implementation that takes advantage of that optimization. Notice that the subfunction, rgcd, can be easily derived from recursive_gcd above by moving the arguments to the input:<lang jq>def gcd(a; b): # The subfunction expects [a,b] as input # i.e. a ~ .[0] and b ~ .[1] def rgcd: if .[1] == 0 then .[0] else [.[1], .[0] % .[1]] | rgcd end; [a,b] | rgcd ;</lang>
Julia
Julia includes a built-in gcd
function:
julia> gcd(4,12) 4 julia> gcd(6,12) 6 julia> gcd(7,12) 1
The actual implementation of this function in Julia 0.2's standard library is reproduced here: <lang julia>function gcd{T<:Integer}(a::T, b::T)
neg = a < 0 while b != 0 t = b b = rem(a, b) a = t end g = abs(a) neg ? -g : g
end</lang> (For arbitrary-precision integers, Julia calls a different implementation from the GMP library.)
K
<lang K>gcd:{:[~x;y;_f[y;x!y]]}</lang>
Klong
<lang K>gcd::{:[~x;y:|~y;x:|x>y;.f(y;x!y);.f(x;y!x)]}</lang>
Kotlin
Recursive one line solution: <lang kotlin>tailrec fun gcd(a: Int, b: Int): Int = if (b == 0) kotlin.math.abs(a) else gcd(b, a % b)</lang>
LabVIEW
It may be helpful to read about Recursion in LabVIEW.
This image is a VI Snippet, an executable image of LabVIEW code. The LabVIEW version is shown on the top-right hand corner. You can download it, then drag-and-drop it onto the LabVIEW block diagram from a file browser, and it will appear as runnable, editable code.
Lambdatalk
<lang scheme>
{def gcd
{lambda {:a :b} {if {= :b 0} then :a else {gcd :b {% :a :b}}}}}
-> gcd
{gcd 12 3} -> 3
{gcd 123 122} -> 1
{S.map {gcd 123} {S.serie 1 30}} -> 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3
A simpler one if a and b are greater than zero
{def GCD
{lambda {:a :b} {if {= :a :b} then :a else {if {> :a :b} then {GCD {- :a :b} :b} else {GCD :a {- :b :a}}}}}}
-> GCD
{S.map {GCD 123} {S.serie 1 30}} -> 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 </lang>
LFE
<lang lisp> > (defun gcd
"Get the greatest common divisor." ((a 0) a) ((a b) (gcd b (rem a b))))
</lang>
Usage:
> (gcd 12 8) 4 > (gcd 12 -8) 4 > (gcd 96 27) 3 > (gcd 51 34) 17
Liberty BASIC
<lang lb>'iterative Euclid algorithm print GCD(-2,16) end
function GCD(a,b)
while b c = a a = b b = c mod b wend GCD = abs(a) end function </lang>
Limbo
<lang Limbo>gcd(x: int, y: int): int { if(y == 0) return x; return gcd(y, x % y); } </lang>
LiveCode
<lang LiveCode>function gcd x,y
repeat until y = 0 put x mod y into z put y into x put z into y end repeat return x
end gcd</lang>
Logo
<lang logo>to gcd :a :b
if :b = 0 [output :a] output gcd :b modulo :a :b
end</lang>
LOLCODE
<lang LOLCODE>HAI 1.3
HOW IZ I gcd YR a AN YR b a R BIGGR OF a AN PRODUKT OF a AN -1 BTW absolute value of a b R BIGGR OF b AN PRODUKT OF b AN -1 BTW absolute value of b BOTH SAEM a AN b, O RLY? YA RLY FOUND YR a OIC BOTH SAEM a AN 0, O RLY? YA RLY FOUND YR b OIC BOTH SAEM b AN 0, O RLY? YA RLY FOUND YR a OIC BOTH SAEM b AN BIGGR OF a AN b, O RLY? BTW make sure a is the larger of (a, b) YA RLY I HAS A temp ITZ a a R b b R temp OIC
IM IN YR loop I HAS A temp ITZ b b R MOD OF a AN b a R temp BOTH SAEM b AN 0, O RLY? YA RLY FOUND YR a OIC IM OUTTA YR loop IF U SAY SO
VISIBLE I IZ gcd YR 40902 AN YR 24140 MKAY
KTHXBYE</lang> Try it online!
LSE
<lang LSE>(*
- MÉTHODE D'EUCLIDE POUR TROUVER LE PLUS GRAND DIVISEUR COMMUN D'UN
- NUMÉRATEUR ET D'UN DÉNOMINATEUR.
- )
PROCÉDURE &PGDC(ENTIER U, ENTIER V) : ENTIER LOCAL U, V
ENTIER T TANT QUE U > 0 FAIRE SI U< V ALORS T<-U U<-V V<-T FIN SI U <- U - V BOUCLER RÉSULTAT V
FIN PROCÉDURE
PROCÉDURE &DEMO(ENTIER U, ENTIER V) LOCAL U, V
AFFICHER ['Le PGDC de ',U,'/',U,' est ',U,/] U, V, &PGDC(U,V)
FIN PROCÉDURE
&DEMO(9,12) &DEMO(6144,8192) &DEMO(100,5) &DEMO(7,23)</lang>
Resultats:
Le PGDC de 9/12 est 3 Le PGDC de 6144/8192 est 2048 Le PGDC de 100/5 est 5 Le PGDC de 7/23 est 1
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
Faster iterative solution of Euclid: <lang lua>function gcd(a,b)
while b~=0 do a,b=b,a%b end return math.abs(a)
end </lang>
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>
Luck
<lang luck>function gcd(a: int, b: int): int = (
if a==0 then b else if b==0 then a else if a>b then gcd(b, a % b) else gcd(a, b % a)
)</lang>
M2000 Interpreter
<lang M2000 Interpreter> gcd=lambda (u as long, v as long) -> {
=if(v=0&->abs(u), lambda(v, u mod v))
} gcd_Iterative= lambda (m as long, n as long) -> {
while m { let old_m = m m = n mod m n = old_m } =abs(n)
} Module CheckGCD (f){
Print f(49865, 69811)=9973 Def ExpType$(x)=Type$(x) Print ExpType$(f(49865, 69811))="Long"
} CheckGCD gcd CheckGCD gcd_Iterative </lang>
m4
This should work in any POSIX-compliant m4. I have tested it with GNU m4, OpenBSD m4, and Heirloom Devtools m4. It is Euler’s algorithm. <lang m4>divert(-1) define(`gcd',
`ifelse(eval(`0 <= (' $1 `)'),`0',`gcd(eval(`-(' $1 `)'),eval(`(' $2 `)'))', eval(`0 <= (' $2 `)'),`0',`gcd(eval(`(' $1 `)'),eval(`-(' $2 `)'))', eval(`(' $1 `) == 0'),`0',`gcd(eval(`(' $2 `) % (' $1 `)'),eval(`(' $1 `)'))', eval(`(' $2 `)'))')
divert`'dnl dnl gcd(0, 0) = 0 gcd(24140, 40902) = 34 gcd(-24140, -40902) = 34 gcd(-40902, 24140) = 34 gcd(40902, -24140) = 34</lang>
- Output:
0 = 0 34 = 34 34 = 34 34 = 34 34 = 34
Maple
To compute the greatest common divisor of two integers in Maple, use the procedure igcd.
<lang Maple>igcd( a, b )</lang>
For example, <lang Maple> > igcd( 24, 15 );
3
</lang>
Mathematica / Wolfram Language
<lang mathematica>GCD[a, b]</lang>
MATLAB
<lang Matlab>function [gcdValue] = greatestcommondivisor(integer1, integer2)
gcdValue = gcd(integer1, integer2);</lang>
Maxima
<lang maxima>/* There is a function gcd(a, b) in Maxima, but one can rewrite it */ gcd2(a, b) := block([a: abs(a), b: abs(b)], while b # 0 do [a, b]: [b, mod(a, b)], a)$
/* both will return 2^97 * 3^48 */ gcd(100!, 6^100), factor; gcd2(100!, 6^100), factor;</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>
Mercury
Recursive Euclid algorithm
<lang Mercury>:- module gcd.
- - interface.
- - import_module integer.
- - func gcd(integer, integer) = integer.
- - implementation.
- - pragma memo(gcd/2).
gcd(A, B) = (if B = integer(0) then A else gcd(B, A mod B)).</lang>
An example console program to demonstrate the gcd module: <lang Mercury>:- module test_gcd.
- - interface.
- - import_module io.
- - pred main(io::di, io::uo) is det.
- - implementation.
- - import_module char.
- - import_module gcd.
- - import_module integer.
- - import_module list.
- - import_module string.
main(!IO) :-
command_line_arguments(Args, !IO), filter(is_all_digits, Args, CleanArgs),
Arg1 = list.det_index0(CleanArgs, 0), Arg2 = list.det_index0(CleanArgs, 1), A = integer.det_from_string(Arg1), B = integer.det_from_string(Arg2),
Fmt = integer.to_string, GCD = gcd(A, B), io.format("gcd(%s, %s) = %s\n", [s(Fmt(A)), s(Fmt(B)), s(Fmt(GCD))], !IO).</lang>
Example output: <lang Bash>gcd(70000000000000000000000, 60000000000000000000000000) = 10000000000000000000000</lang>
MINIL
<lang minil>// Greatest common divisor 00 0E GCD: ENT R0 01 1E ENT R1 02 21 Again: R2 = R1 03 10 Loop: R1 = R0 04 02 R0 = R2 05 2D Minus: DEC R2 06 8A JZ Stop 07 1D DEC R1 08 C5 JNZ Minus 09 83 JZ Loop 0A 1D Stop: DEC R1 0B C2 JNZ Again 0C 80 JZ GCD // Display GCD in R0</lang>
MiniScript
Using an iterative Euclidean algorithm: <lang MiniScript>gcd = function(a, b)
while b temp = b b = a % b a = temp end while return abs(a)
end function
print gcd(18,12)</lang>
- Output:
6
MiniZinc
<lang MiniZinc>function var int: gcd(int:a2,int:b2) =
let { int:a1 = max(a2,b2); int:b1 = min(a2,b2); array[0..a1,0..b1] of var int: gcd; constraint forall(a in 0..a1)( forall(b in 0..b1)( gcd[a,b] == if (b == 0) then a else gcd[b, a mod b] endif ) ) } in gcd[a1,b1];
var int: gcd1 = gcd(8,12); solve satisfy; output [show(gcd1),"\n"];</lang>
- Output:
6
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>
МК-61/52
ИПA ИПB / П9 КИП9 ИПA ИПB ПA ИП9 * - ПB x=0 00 ИПA С/П
Enter: n = РA, m = РB (n > m).
ML
mLite
<lang ocaml>fun gcd (a, 0) = a
| (0, b) = b | (a, b) where (a < b) = gcd (a, b rem a) | (a, b) = gcd (b, a rem b)
</lang>
ML / Standard ML
See also #Standard ML.
<lang sml>fun gcd a 0 = a
| gcd a b = gcd b (a mod b)</lang>
Modula-2
<lang modula2>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
Monicelli
<lang Monicelli>
#main function (needs two ints from stdin)
Lei ha clacsonato bitumatissimi cari amici ospiti voglio arrivata, Necchi bitumati qui tra noi benvenuti ENERGIAAh voglio espertizzata, Necchi mi porga arrivata mi porga espertizzata bitumata mi raccomando voglio garantita, Necchi come se fosse prematurata la supercazzola accanita con arrivata, espertizzata o scherziamo? brematurata la supercazzola novella o scherziamo? bitumata ma dai garantita a posterdati
- gcd function
blinda la supercazzola Necchi accanita con visibilio Necchi, sgomento Necchi o scherziamo? voglio la catarsi, Necchi bituma, e come bituma lui non bituma nessuno voglio l'entusiasmo, Necchi bituma, chi di bituma vive bitumato muore che cos'è il visibilio? sgomento: vaffanzum visibilio! o magari maggiore di sgomento: catarsi come fosse visibilio meno sgomento bitumato ma non troppo entusiasmo come fosse sgomento bitumato anche piu del necessario o tarapia tapioco: catarsi come fosse sgomento meno il visibilio bitumante dai tempi andati entusiasmo come fosse visibilio e velocità di esecuzione voglio la spensierataggine, Necchi come fosse prematurata la supercazzola accanita con catarsi, entusiasmo o scherziamo? vaffanzum la spensierataggine!
- prints new line
blinda la supercazzola novella o scherziamo? voglio novita, Mascetti come se fosse 10 bituma come fosse una lungaggine, uno scherzo di mano novita a posterdati! </lang>
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
MySQL
<lang mysql> DROP FUNCTION IF EXISTS gcd; DELIMITER |
CREATE FUNCTION gcd(x INT, y INT) RETURNS INT BEGIN
SET @dividend=GREATEST(ABS(x),ABS(y)); SET @divisor=LEAST(ABS(x),ABS(y)); IF @divisor=0 THEN RETURN @dividend; END IF; SET @gcd=NULL; SELECT gcd INTO @gcd FROM (SELECT @tmp:=@dividend, @dividend:=@divisor AS gcd, @divisor:=@tmp % @divisor AS remainder FROM mysql.help_relation WHERE @divisor>0) AS x WHERE remainder=0; RETURN @gcd;
END;|
DELIMITER ;
SELECT gcd(12345, 9876); </lang>
+------------------+ | gcd(12345, 9876) | +------------------+ | 2469 | +------------------+ 1 row in set (0.00 sec)
Nanoquery
Iterative
<lang Nanoquery>def gcd(a, b) factor = a.min(b)
for loop in range(factor, 2) if (a % loop = 0) and (b % loop = 0) return loop end end
return 1 end</lang>
Iterative Euclid's Method
<lang Nanoquery>def gcd_euclid(a, b) while b > 0 c = a % b a = b b = c end return a end</lang>
NetRexx
<lang NetRexx>/* NetRexx */ options replace format comments java crossref symbols nobinary
numeric digits 2000 runSample(arg) return
-- 09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)~~ -- Euclid's algorithm - iterative implementation method gcdEucidI(a_, b_) public static
loop while b_ > 0 c_ = a_ // b_ a_ = b_ b_ = c_ end return a_
-- 09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)~~ -- Euclid's algorithm - recursive implementation method gcdEucidR(a_, b_) public static
if b_ \= 0 then a_ = gcdEucidR(b_, a_ // b_) return a_
-- 09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)~~ method runSample(arg) private static
-- pairs of numbers, each number in the pair separated by a colon, each pair separated by a comma parse arg tests if tests = then tests = '0:0, 6:4, 7:21, 12:36, 33:77, 41:47, 99:51, 100:5, 7:23, 1989:867, 12345:9876, 40902:24140, 49865:69811, 137438691328:2305843008139952128'
-- most of what follows is for formatting xiterate = 0 xrecurse = 0 ll_ = 0 lr_ = 0 lgi = 0 lgr = 0 loop i_ = 1 until tests = xiterate[0] = i_ xrecurse[0] = i_ parse tests pair ',' tests parse pair l_ ':' r_ .
-- get the GCDs gcdi = gcdEucidI(l_, r_) gcdr = gcdEucidR(l_, r_)
xiterate[i_] = l_ r_ gcdi xrecurse[i_] = l_ r_ gcdr ll_ = ll_.max(l_.strip.length) lr_ = lr_.max(r_.strip.length) lgi = lgi.max(gcdi.strip.length) lgr = lgr.max(gcdr.strip.length) end i_ -- save formatter sizes in stems xiterate[-1] = ll_ lr_ lgi xrecurse[-1] = ll_ lr_ lgr
-- present results showResults(xiterate, 'Euclids algorithm - iterative') showResults(xrecurse, 'Euclids algorithm - recursive') say if verifyResults(xiterate, xrecurse) then say 'Success: Results of iterative and recursive methods match' else say 'Error: Results of iterative and recursive methods do not match' say return
-- 09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)~~ method showResults(stem, title) public static
say say title parse stem[-1] ll lr lg loop v_ = 1 to stem[0] parse stem[v_] lv rv gcd . say lv.right(ll)',' rv.right(lr) ':' gcd.right(lg) end v_ return
-- 09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)09:53, 27 August 2022 (UTC)~~ method verifyResults(stem1, stem2) public static returns boolean
if stem1[0] \= stem2[0] then signal BadArgumentException T = (1 == 1) F = \T verified = T loop i_ = 1 to stem1[0] if stem1[i_] \= stem2[i_] then do verified = F leave i_ end end i_ return verified
</lang>
- Output:
Euclid's algorithm - iterative 0, 0 : 0 6, 4 : 2 7, 21 : 7 12, 36 : 12 33, 77 : 11 41, 47 : 1 99, 51 : 3 100, 5 : 5 7, 23 : 1 1989, 867 : 51 12345, 9876 : 2469 40902, 24140 : 34 49865, 69811 : 9973 137438691328, 2305843008139952128 : 262144 Euclid's algorithm - recursive 0, 0 : 0 6, 4 : 2 7, 21 : 7 12, 36 : 12 33, 77 : 11 41, 47 : 1 99, 51 : 3 100, 5 : 5 7, 23 : 1 1989, 867 : 51 12345, 9876 : 2469 40902, 24140 : 34 49865, 69811 : 9973 137438691328, 2305843008139952128 : 262144 Success: Results of iterative and recursive methods match
NewLISP
<lang NewLISP>(gcd 12 36)
→ 12</lang>
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>
Nim
Recursive Euclid algorithm
<lang nim>func gcd_recursive*(u, v: SomeSignedInt): int64 =
if u mod v != 0: result = gcd_recursive(v, u mod v) else: result = abs(v)
when isMainModule:
import strformat let (x, y) = (49865, 69811) echo &"gcd({x}, {y}) = {gcd_recursive(49865, 69811)}"</lang>
- Output:
gcd(49865, 69811) = 9973
Iterative Euclid algorithm
<lang nim>func gcd_iterative*(u, v: SomeSignedInt): int64 =
var u = u var v = v while v != 0: u = u mod v swap u, v result = abs(u)
when isMainModule:
import strformat let (x, y) = (49865, 69811) echo &"gcd({x}, {y}) = {gcd_iterative(49865, 69811)}")</lang>
- Output:
gcd(49865, 69811) = 9973
Iterative binary algorithm
<lang nim>template isEven(n: int64): bool = (n and 1) == 0
func gcd_binary*(u, v: int64): int64 =
var u = abs(u) var v = abs(v) if u < v: swap u, v
if v == 0: return u
var k = 1 while u.isEven and v.isEven: u = u shr 1 v = v shr 1 k = k shl 1 var t = if u.isEven: u else: -v while t != 0: while t.isEven: t = ashr(t, 1) if t > 0: u = t else: v = -t t = u - v result = u * k
when isMainModule:
import strformat let (x, y) = (49865, 69811) echo &"gcd({x}, {y}) = {gcd_binary(49865, 69811)}"</lang>
- Output:
gcd(49865, 69811) = 9973
Oberon-2
Works with oo2c version 2 <lang oberon2> MODULE GCD; (* Greatest Common Divisor *) IMPORT
Out; PROCEDURE Gcd(a,b: LONGINT):LONGINT; VAR r: LONGINT; BEGIN LOOP r := a MOD b; IF r = 0 THEN RETURN b END; a := b;b := r END END Gcd;
BEGIN
Out.String("GCD of 12 and 8 : ");Out.LongInt(Gcd(12,8),4);Out.Ln; Out.String("GCD of 100 and 5 : ");Out.LongInt(Gcd(100,5),4);Out.Ln; Out.String("GCD of 7 and 23 : ");Out.LongInt(Gcd(7,23),4);Out.Ln; Out.String("GCD of 24 and -112 : ");Out.LongInt(Gcd(12,8),4);Out.Ln; Out.String("GCD of 40902 and 24140 : ");Out.LongInt(Gcd(40902,24140),4);Out.Ln
END GCD.
</lang>
Output:
GCD of 12 and 8 : 4 GCD of 100 and 5 : 5 GCD of 7 and 23 : 1 GCD of 24 and -112 : 4 GCD of 40902 and 24140 : 34
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>
A little more idiomatic version: <lang ocaml>let rec gcd1 a b =
match (a mod b) with 0 -> b | r -> gcd1 b r</lang>
Built-in
<lang ocaml>#load "nums.cma";; open Big_int;; let gcd a b =
int_of_big_int (gcd_big_int (big_int_of_int a) (big_int_of_int b))</lang>
Octave
<lang octave>r = gcd(a, b)</lang>
Oforth
gcd is already defined into Integer class : <lang Oforth>128 96 gcd</lang>
Source of this method is (see Integer.of file) : <lang Oforth>Integer method: gcd self while ( dup ) [ tuck mod ] drop ;</lang>
Ol
<lang scheme> (print (gcd 1071 1029))
- ==> 21
</lang>
Order
<lang c>#include <order/interpreter.h>
- define ORDER_PP_DEF_8gcd ORDER_PP_FN( \
8fn(8U, 8V, \
8if(8isnt_0(8V), 8gcd(8V, 8remainder(8U, 8V)), 8U)))
// No support for negative numbers</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 program GCF (INPUT, OUTPUT);
var a,b,c:integer; begin writeln('Enter 1st number'); read(a); writeln('Enter 2nd number'); read(b); while (a*b<>0) do begin c:=a; a:=b mod a; b:=c; end; writeln('GCF :=', a+b ); end.
By: NG
Pascal / Delphi / Free Pascal
Recursive Euclid algorithm
<lang pascal> PROGRAM EXRECURGCD.PAS;
{$IFDEF FPC}
{$mode objfpc}{$H+}{$J-}{R+}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
(*)
Free Pascal Compiler version 3.2.0 [2020/06/14] for x86_64 The free and readable alternative at C/C++ speeds compiles natively to almost any platform, including raspberry PI
(*)
FUNCTION gcd_recursive(u, v: longint): longint;
BEGIN IF ( v = 0 ) THEN Exit ( u ) ; result := gcd_recursive ( v, u MOD v ) ; END;
BEGIN
WriteLn ( gcd_recursive ( 231, 7 ) ) ;
END.
</lang>JPD 2021/03/14
Iterative Euclid algorithm
<lang fortran>function gcd_iterative(u, v: longint): longint;
var t: longint; begin while v <> 0 do begin t := u; u := v; v := t mod v; end; gcd_iterative := abs(u); end;</lang>
Iterative binary algorithm
<lang Pascal>function gcd_binary(u, v: longint): longint;
var t, k: longint; begin u := abs(u); v := abs(v); if u < v then begin t := u; u := v; v := t; end; if v = 0 then gcd_binary := u else begin k := 1; while (u mod 2 = 0) and (v mod 2 = 0) do begin u := u >> 1; v := v >> 1;
k := k << 1;
end; if u mod 2 = 0 then t := u else t := -v; while t <> 0 do begin while t mod 2 = 0 do t := t div 2; if t > 0 then u := t else v := -t; t := u - v; end; gcd_binary := u * k; end; end;</lang>
Demo program:
<lang pascal>Program GreatestCommonDivisorDemo(output); begin
writeln ('GCD(', 49865, ', ', 69811, '): ', gcd_iterative(49865, 69811), ' (iterative)'); writeln ('GCD(', 49865, ', ', 69811, '): ', gcd_recursive(49865, 69811), ' (recursive)'); writeln ('GCD(', 49865, ', ', 69811, '): ', gcd_binary (49865, 69811), ' (binary)');
end.</lang> Output:
GCD(49865, 69811): 9973 (iterative) GCD(49865, 69811): 9973 (recursive) GCD(49865, 69811): 9973 (binary)
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>
Modules
All three modules will take large integers as input, e.g. gcd("68095260063025322303723429387", "51306142182612010300800963053"). Other possibilities are Math::Cephes euclid, Math::GMPz gcd and gcd_ui. <lang perl># Fastest, takes multiple inputs use Math::Prime::Util "gcd"; $gcd = gcd(49865, 69811);
- In CORE. Slowest, takes multiple inputs, result is a Math::BigInt unless converted
use Math::BigInt; $gcd = Math::BigInt::bgcd(49865, 69811)->numify;
- Result is a Math::Pari object unless converted
use Math::Pari "gcd"; $gcd = gcd(49865, 69811)->pari2iv </lang>
Notes on performance
<lang perl>use Benchmark qw(cmpthese); use Math::BigInt; use Math::Pari; use Math::Prime::Util;
my $u = 40902; my $v = 24140; cmpthese(-5, {
'gcd_rec' => sub { gcd($u, $v); }, 'gcd_iter' => sub { gcd_iter($u, $v); }, 'gcd_bin' => sub { gcd_bin($u, $v); }, 'gcd_bigint' => sub { Math::BigInt::bgcd($u,$v)->numify(); }, 'gcd_pari' => sub { Math::Pari::gcd($u,$v)->pari2iv(); }, 'gcd_mpu' => sub { Math::Prime::Util::gcd($u,$v); },
});</lang>
Output on 'Intel i3930k 4.2GHz' / Linux / Perl 5.20:
Rate gcd_bigint gcd_bin gcd_rec gcd_iter gcd_pari gcd_mpu gcd_bigint 39939/s -- -83% -94% -95% -98% -99% gcd_bin 234790/s 488% -- -62% -70% -88% -97% gcd_rec 614750/s 1439% 162% -- -23% -68% -91% gcd_iter 793422/s 1887% 238% 29% -- -58% -89% gcd_pari 1896544/s 4649% 708% 209% 139% -- -73% gcd_mpu 7114798/s 17714% 2930% 1057% 797% 275% --
Phix
result is always positive, except for gcd(0,0) which is 0
atom parameters allow greater precision, but any fractional parts are immediately and deliberately discarded.
Actually, it is an autoinclude, reproduced below. The first parameter can be a sequence, in which case the second parameter (if provided) is ignored.
function gcd(object u, atom v=0) atom t if sequence(u) then v = u[1] -- (for the typecheck) t = floor(abs(v)) for i=2 to length(u) do v = u[i] -- (for the typecheck) t = gcd(t,v) end for return t end if u = floor(abs(u)) v = floor(abs(v)) while v do t = u u = v v = remainder(t, v) end while return u end function
Sample results
?gcd(0,0) -- 0 ?gcd(24,-112) -- 8 ?gcd(0, 10) -- 10 ?gcd(10, 0) -- 10 ?gcd(-10, 0) -- 10 ?gcd(0, -10) -- 10 ?gcd(9, 6) -- 3 ?gcd(6, 9) -- 3 ?gcd(-6, 9) -- 3 ?gcd(9, -6) -- 3 ?gcd(6, -9) -- 3 ?gcd(-9, 6) -- 3 ?gcd(40902, 24140) -- 34 printf(1,"%d\n",gcd(70000000000000000000, 60000000000000000000000)) -- 10000000000000000000 ?gcd({57,0,-45,-18,90,447}) -- 3
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>
PicoLisp
<lang PicoLisp>(de gcd (A B)
(until (=0 B) (let M (% A B) (setq A B B M) ) ) (abs A) )</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> With no external lib, recursive <lang postscript> /gcd {
dup 0 ne { dup 3 1 roll mod gcd } { pop } ifelse
} def </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>
or shorter (taken from Python implementation) <lang powershell>function Get-GCD ($x, $y) {
if ($y -eq 0) { $x } else { Get-GCD $y ($x%$y) }
}</lang>
Iterative Euclid Algorithm
based on Python implementation <lang powershell> Function Get-GCD( $x, $y ) {
while ($y -ne 0) { $x, $y = $y, ($x % $y) } [Math]::abs($x)
} </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>
(Note that fractions.gcd is now deprecated in Python 3) <lang python>from math 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
Quackery
<lang Quackery>
[ [ dup while tuck mod again ] drop abs ] is gcd ( n n --> n )
</lang>
Qi
<lang Qi> (define gcd
A 0 -> A A B -> (gcd B (MOD A B)))
</lang>
R
Recursive: <lang R>"%gcd%" <- function(u, v) {
ifelse(u %% v != 0, v %gcd% (u%%v), v)
}</lang> Iterative: <lang R>"%gcd%" <- function(v, t) {
while ( (c <- v%%t) != 0 ) { v <- t t <- c } t
}</lang>
- Output:
Same either way.
> print(50 %gcd% 75) [1] 25
Racket
Racket provides a built-in gcd function. Here's a program that computes the gcd of 14 and 63:
<lang racket>#lang racket
(gcd 14 63)</lang>
Here's an explicit implementation. Note that since Racket is tail-calling, the memory behavior of this program is "loop-like", in the sense that this program will consume no more memory than a loop-based implementation.
<lang racket>#lang racket
- given two nonnegative integers, produces their greatest
- common divisor using Euclid's algorithm
(define (gcd a b)
(if (= b 0) a (gcd b (modulo a b))))
- some test cases!
(module+ test
(require rackunit) (check-equal? (gcd (* 2 3 3 7 7) (* 3 3 7 11)) (* 3 3 7)) (check-equal? (gcd 0 14) 14) (check-equal? (gcd 13 0) 13))</lang>
Raku
(formerly 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 = { ($^a.abs, $^b.abs, * % * ... 0)[*-2] }</lang>
Actually, it's a built-in infix
<lang perl6>my $gcd = $a gcd $b;</lang> Because it's an infix, you can use it with various meta-operators: <lang perl6>[gcd] @list; # reduce with gcd @alist Zgcd @blist; # lazy zip with gcd @alist Xgcd @blist; # lazy cross with gcd @alist »gcd« @blist; # parallel gcd</lang>
Rascal
Iterative Euclidean algorithm
<lang rascal> public int gcd_iterative(int a, b){ if(a == 0) return b; while(b != 0){ if(a > b) a -= b; else b -= a;} return a; } </lang> An example: <lang rascal> rascal>gcd_iterative(1989, 867) int: 51 </lang>
Recursive Euclidean algorithm
<lang rascal> public int gcd_recursive(int a, b){ return (b == 0) ? a : gcd_recursive(b, a%b); } </lang> An example: <lang rascal> rascal>gcd_recursive(1989, 867) int: 51 </lang>
Raven
Recursive Euclidean algorithm
<lang Raven>define gcd use $u, $v
$v 0 > if $u $v % $v gcd else $u abs
24140 40902 gcd</lang>
- Output:
34
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
version 1
The GCD subroutine can handle any number of arguments, it can also handle any number of integers within any
argument(s), making it easier to use when computing Frobenius numbers (also known as postage stamp or
coin numbers).
<lang rexx>/*REXX program calculates the GCD (Greatest Common Divisor) of any number of integers.*/
numeric digits 2000 /*handle up to 2k decimal dig integers.*/
call gcd 0 0 ; call gcd 55 0 ; call gcd 0 66
call gcd 7,21 ; call gcd 41,47 ; call gcd 99 , 51
call gcd 24, -8 ; call gcd -36, 9 ; call gcd -54, -6
call gcd 14 0 7 ; call gcd 14 7 0 ; call gcd 0 14 7
call gcd 15 10 20 30 55 ; call gcd 137438691328 2305843008139952128 /*◄──2 perfect#s*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
gcd: procedure; $=; do i=1 for arg(); $=$ arg(i); end /*arg list.*/
parse var $ x z .; if x=0 then x=z; x=abs(x) /* 0 case? */
do j=2 to words($); y=abs(word($,j)); if y=0 then iterate /*is zero? */ do until _==0; _=x//y; x=y; y=_; end /* ◄────────── the heavy lifting.*/ end /*j*/
say 'GCD (Greatest Common Divisor) of ' translate(space($),",",' ') " is " x return x</lang>
output
GCD (Greatest Common Divisor) of 0,0 is 0 GCD (Greatest Common Divisor) of 55,0 is 55 GCD (Greatest Common Divisor) of 0,66 is 66 GCD (Greatest Common Divisor) of 7,21 is 7 GCD (Greatest Common Divisor) of 41,47 is 1 GCD (Greatest Common Divisor) of 99,51 is 3 GCD (Greatest Common Divisor) of 24,-8 is 8 GCD (Greatest Common Divisor) of -36,9 is 9 GCD (Greatest Common Divisor) of -54,-6 is 6 GCD (Greatest Common Divisor) of 14,0,7 is 7 GCD (Greatest Common Divisor) of 14,7,0 is 7 GCD (Greatest Common Divisor) of 0,14,7 is 7 GCD (Greatest Common Divisor) of 15,10,20,30,55 is 5 GCD (Greatest Common Divisor) of 137438691328,2305843008139952128 is 262144
version 2
Recursive function (as in PL/I): <lang REXX> /* REXX ***************************************************************
- using PL/I code extended to many arguments
- 17.08.2012 Walter Pachl
- 18.08.2012 gcd(0,0)=0
- /
numeric digits 300 /*handle up to 300 digit numbers.*/ Call test 7,21 ,'7 ' Call test 4,7 ,'1 ' Call test 24,-8 ,'8' Call test 55,0 ,'55' Call test 99,15 ,'3 ' Call test 15,10,20,30,55,'5' Call test 496,8128 ,'16' Call test 496,8128 ,'8' /* test wrong expectation */ Call test 0,0 ,'0' /* by definition */ Exit
test: /**********************************************************************
- Test the gcd function
- /
n=arg() /* Number of arguments */ gcde=arg(n) /* Expected result */ gcdx=gcd(arg(1),arg(2)) /* gcd of the first 2 numbers */ Do i=2 To n-2 /* proceed with all the others */
If arg(i+1)<>0 Then gcdx=gcd(gcdx,arg(i+1)) End
If gcdx=arg(arg()) Then /* result is as expected */
tag='as expected'
Else /* result is not correct */
Tag='*** wrong. expected:' gcde
numbers=arg(1) /* build string to show the input*/ Do i=2 To n-1
numbers=numbers 'and' arg(i) End
say left('the GCD of' numbers 'is',45) right(gcdx,3) tag Return
GCD: procedure /**********************************************************************
- Recursive procedure as shown in PL/I
- /
Parse Arg a,b if b = 0 then return abs(a) return GCD(b,a//b)</lang> Output:
the GCD of 7 and 21 is 7 as expected the GCD of 4 and 7 is 1 as expected the GCD of 24 and -8 is 8 as expected the GCD of 55 and 0 is 55 as expected the GCD of 99 and 15 is 3 as expected the GCD of 15 and 10 and 20 and 30 and 55 is 5 as expected the GCD of 496 and 8128 is 16 as expected the GCD of 496 and 8128 is 16 *** wrong. expected: 8 the GCD of 0 and 0 is 0 as expected
version 3
using different argument handling-
Use as gcd(a,b,c,---)
Considerably faster than version 1 (and version 2)
See http://rosettacode.org/wiki/Least_common_multiple#REXX for reasoning.
<lang rexx>gcd: procedure
x=abs(arg(1))
do j=2 to arg()
y=abs(arg(j)) If y<>0 Then Do do until z==0 z=x//y x=y y=z end end end
return x</lang>
Ring
<lang> see gcd (24, 32) func gcd gcd, b
while b c = gcd gcd = b b = c % b end return gcd
</lang>
Ruby
That is already available as the gcd method of integers:
<lang ruby> 40902.gcd(24140) # => 34</lang>
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>
Run BASIC
<lang Runbasic>print abs(gcd(-220,160)) function gcd(gcd,b)
while b c = gcd gcd = b b = c mod b wend
end function </lang>
Rust
num crate
<lang rust>extern crate num; use num::integer::gcd;</lang>
Iterative Euclid algorithm
<lang rust>fn gcd(mut m: i32, mut n: i32) -> i32 {
while m != 0 { let old_m = m; m = n % m; n = old_m; } n.abs()
}</lang>
Recursive Euclid algorithm
<lang rust>fn gcd(m: i32, n: i32) -> i32 {
if m == 0 { n.abs() } else { gcd(n % m, m) }
}</lang>
Stein's Algorithm
Stein's algorithm is very much like Euclid's except that it uses bitwise operators (and consequently slightly more performant) and the integers must be unsigned. The following is a recursive implementation that leverages Rust's pattern matching.
<lang rust>use std::cmp::{min, max}; fn gcd(a: usize, b: usize) -> usize {
match ((a, b), (a & 1, b & 1)) { ((x, y), _) if x == y => y, ((0, x), _) | ((x, 0), _) => x, ((x, y), (0, 1)) | ((y, x), (1, 0)) => gcd(x >> 1, y), ((x, y), (0, 0)) => gcd(x >> 1, y >> 1) << 1, ((x, y), (1, 1)) => { let (x, y) = (min(x, y), max(x, y)); gcd((y - x) >> 1, x) } _ => unreachable!(), }
}</lang>
Tests
<lang rust>
println!("{}",gcd(399,-3999)); println!("{}",gcd(0,3999)); println!("{}",gcd(13*13,13*29));
3 3999 13</lang>
Sass/SCSS
Iterative Euclid's Algorithm
<lang coffeescript> @function gcd($a,$b) { @while $b > 0 { $c: $a % $b; $a: $b; $b: $c; } @return $a; } </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>
S-BASIC
<lang basic> rem - return p mod q function mod(p, q = integer) = integer end = p - q * (p / q)
rem - return greatest common divisor of x and y function gcd(x, y = integer) = integer
var r, temp = integer if x < y then begin temp = x x = y y = temp end r = mod(x, y) while r <> 0 do begin x = y y = r r = mod(x, y) end
end = y
rem - exercise the function
print "The GCD of 21 and 35 is"; gcd(21,35) print "The GCD of 23 and 35 is"; gcd(23,35) print "The GCD of 1071 and 1029 is"; gcd(1071, 1029) print "The GCD of 3528 and 3780 is"; gcd(3528,3780)
end </lang>
- Output:
The GCD of 21 and 35 is 7 The GCD of 23 and 35 is 1 The GCD of 1071 and 1029 is 21 The GCD of 3528 and 3780 is 252
Scala
<lang scala>def gcd(a: Int, b: Int): Int = if (b == 0) a.abs else gcd(b, a % b)</lang>
Using pattern matching
<lang scala>@tailrec def gcd(a: Int, b: Int): Int = {
b match { case 0 => a case _ => 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: gcd is 0; local var integer: help is 0; begin while a <> 0 do help := b rem a; b := a; a := help; end while; gcd := b; end func;</lang>
Original source: [1]
SequenceL
Tail Recursive Greatest Common Denominator using Euclidian Algorithm <lang sequencel>gcd(a, b) := a when b = 0 else gcd(b, a mod b);</lang>
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>
Sidef
Built-in
<lang ruby>var arr = [100, 1_000, 10_000, 20]; say Math.gcd(arr...);</lang>
Recursive Euclid algorithm
<lang ruby>func gcd(a, b) {
b.is_zero ? a.abs : gcd(b, a % b);
}</lang>
Simula
For a recursive variant, see Sum multiples of 3 and 5. <lang algolw>BEGIN
INTEGER PROCEDURE GCD(a, b); INTEGER a, b; BEGIN IF a = 0 THEN a := b ELSE WHILE 0 < b DO BEGIN INTEGER i; i := MOD(a, b); a := b; b := i; END; GCD := a END;
INTEGER a, b; !outint(SYSOUT.IMAGE.MAIN.LENGTH, 0);!OUTIMAGE;!OUTIMAGE; !SYSOUT.IMAGE :- BLANKS(132); ! this may or may not work; FOR b := 1 STEP 5 UNTIL 37 DO BEGIN FOR a := 0 STEP 2 UNTIL 21 DO BEGIN OUTTEXT(" ("); OUTINT(a, 0); OUTCHAR(','); OUTINT(b, 2); OUTCHAR(')'); OUTINT(GCD(a, b), 3); END; OUTIMAGE END
END</lang>
- Output:
(0, 1) 1 (2, 1) 1 (4, 1) 1 (6, 1) 1 (8, 1) 1 (10, 1) 1 (12, 1) 1 (14, 1) 1 (16, 1) 1 (18, 1) 1 (20, 1) 1 (0, 6) 6 (2, 6) 2 (4, 6) 2 (6, 6) 6 (8, 6) 2 (10, 6) 2 (12, 6) 6 (14, 6) 2 (16, 6) 2 (18, 6) 6 (20, 6) 2 (0,11) 11 (2,11) 1 (4,11) 1 (6,11) 1 (8,11) 1 (10,11) 1 (12,11) 1 (14,11) 1 (16,11) 1 (18,11) 1 (20,11) 1 (0,16) 16 (2,16) 2 (4,16) 4 (6,16) 2 (8,16) 8 (10,16) 2 (12,16) 4 (14,16) 2 (16,16) 16 (18,16) 2 (20,16) 4 (0,21) 21 (2,21) 1 (4,21) 1 (6,21) 3 (8,21) 1 (10,21) 1 (12,21) 3 (14,21) 7 (16,21) 1 (18,21) 3 (20,21) 1 (0,26) 26 (2,26) 2 (4,26) 2 (6,26) 2 (8,26) 2 (10,26) 2 (12,26) 2 (14,26) 2 (16,26) 2 (18,26) 2 (20,26) 2 (0,31) 31 (2,31) 1 (4,31) 1 (6,31) 1 (8,31) 1 (10,31) 1 (12,31) 1 (14,31) 1 (16,31) 1 (18,31) 1 (20,31) 1 (0,36) 36 (2,36) 2 (4,36) 4 (6,36) 6 (8,36) 4 (10,36) 2 (12,36) 12 (14,36) 2 (16,36) 4 (18,36) 18 (20,36) 4
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 reimplementation of the Iterative Euclid's algorithm would be:
<lang smalltalk>|gcd_iter|
gcd_iter := [ :a :b |
|u v| u := a. v := b. [ v > 0 ] whileTrue: [ |t| t := u. u := v. 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>
Sparkling
<lang sparkling>function factors(n) { var f = {};
for var i = 2; n > 1; i++ { while n % i == 0 { n /= i; f[i] = f[i] != nil ? f[i] + 1 : 1; } }
return f; }
function GCD(n, k) { let f1 = factors(n); let f2 = factors(k);
let fs = map(f1, function(factor, multiplicity) { let m = f2[factor]; return m == nil ? 0 : min(m, multiplicity); });
let rfs = {}; foreach(fs, function(k, v) { rfs[sizeof rfs] = pow(k, v); });
return reduce(rfs, 1, function(x, y) { return x * y; }); }
function LCM(n, k) { return n * k / GCD(n, k); }</lang>
SQL
Demonstration of Oracle 12c WITH Clause Enhancements <lang SQL>drop table tbl; create table tbl (
u number, v number
);
insert into tbl ( u, v ) values ( 20, 50 ); insert into tbl ( u, v ) values ( 21, 50 ); insert into tbl ( u, v ) values ( 21, 51 ); insert into tbl ( u, v ) values ( 22, 50 ); insert into tbl ( u, v ) values ( 22, 55 );
commit;
with
function gcd ( ui in number, vi in number ) return number is u number := ui; v number := vi; t number; begin while v > 0 loop t := u; u := v; v:= mod(t, v ); end loop; return abs(u); end gcd; select u, v, gcd ( u, v ) from tbl
/ </lang>
- Output:
Table dropped. Table created. 1 row created. 1 row created. 1 row created. 1 row created. 1 row created. Commit complete. U V GCD(U,V) ---------- ---------- ---------- 20 50 10 21 50 1 21 51 3 22 50 2 22 55 11
Demonstration of SQL Server 2008 <lang SQL>CREATE FUNCTION gcd (
@ui INT, @vi INT
) RETURNS INT
AS
BEGIN
DECLARE @t INT DECLARE @u INT DECLARE @v INT
SET @u = @ui SET @v = @vi
WHILE @v > 0 BEGIN SET @t = @u; SET @u = @v; SET @v = @t % @v; END; RETURN abs( @u );
END
GO
CREATE TABLE tbl (
u INT, v INT
);
INSERT INTO tbl ( u, v ) VALUES ( 20, 50 ); INSERT INTO tbl ( u, v ) VALUES ( 21, 50 ); INSERT INTO tbl ( u, v ) VALUES ( 21, 51 ); INSERT INTO tbl ( u, v ) VALUES ( 22, 50 ); INSERT INTO tbl ( u, v ) VALUES ( 22, 55 );
SELECT u, v, dbo.gcd ( u, v )
FROM tbl;
DROP TABLE tbl;
DROP FUNCTION gcd; </lang>
PostgreSQL function using a recursive common table expression <lang SQL>CREATE FUNCTION gcd(integer, integer) RETURNS integer LANGUAGE sql AS $function$ WITH RECURSIVE x (u, v) AS (
SELECT ABS($1), ABS($2) UNION SELECT v, u % v FROM x WHERE v > 0
) SELECT min(u) FROM x; $function$ </lang>
- Output:
postgres> select gcd(40902, 24140); gcd ----- 34 SELECT 1 Time: 0.012s
Standard ML
See also #ML / Standard ML.
<lang sml>(* Euclid’s algorithm. *)
fun gcd (u, v) =
let fun loop (u, v) = if v = 0 then u else loop (v, u mod v) in loop (abs u, abs v) end
(* Using the Rosetta Code example for assertions in Standard ML. *) fun assert cond =
if cond then () else raise Fail "assert"
val () = assert (gcd (0, 0) = 0) val () = assert (gcd (0, 10) = 10) val () = assert (gcd (~10, 0) = 10) val () = assert (gcd (9, 6) = 3) val () = assert (gcd (~6, ~9) = 3) val () = assert (gcd (40902, 24140) = 34) val () = assert (gcd (40902, ~24140) = 34) val () = assert (gcd (~40902, 24140) = 34) val () = assert (gcd (~40902, ~24140) = 34) val () = assert (gcd (24140, 40902) = 34) val () = assert (gcd (~24140, 40902) = 34) val () = assert (gcd (24140, ~40902) = 34) val () = assert (gcd (~24140, ~40902) = 34)</lang>
Stata
<lang stata>function gcd(a_,b_) { a = abs(a_) b = abs(b_) while (b>0) { a = mod(a,b) swap(a,b) } return(a) }</lang>
Swift
<lang Swift>// Iterative
func gcd(var a: Int, var b: Int) -> Int {
a = abs(a); b = abs(b) if (b > a) { swap(&a, &b) }
while (b > 0) { (a, b) = (b, a % b) } return a
}
// Recursive
func gcdr (var a: Int, var b: Int) -> Int {
a = abs(a); b = abs(b)
if (b > a) { swap(&a, &b) } return gcd_rec(a,b)
}
private func gcd_rec(a: Int, b: Int) -> Int {
return b == 0 ? a : gcd_rec(b, a % b)
}
for (a,b) in [(1,1), (100, -10), (10, -100), (-36, -17), (27, 18), (30, -42)] {
println("Iterative: GCD of \(a) and \(b) is \(gcd(a, b))") println("Recursive: GCD of \(a) and \(b) is \(gcdr(a, b))")
}</lang>
- Output:
Iterative: GCD of 1 and 1 is 1 Recursive: GCD of 1 and 1 is 1 Iterative: GCD of 100 and -10 is 10 Recursive: GCD of 100 and -10 is 10 Iterative: GCD of 10 and -100 is 10 Recursive: GCD of 10 and -100 is 10 Iterative: GCD of -36 and -17 is 1 Recursive: GCD of -36 and -17 is 1 Iterative: GCD of 27 and 18 is 9 Recursive: GCD of 27 and 18 is 9 Iterative: GCD of 30 and -42 is 6 Recursive: GCD of 30 and -42 is 6
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)
The ) can be omitted in TI-83 basic
Tiny BASIC
<lang Tiny BASIC>10 PRINT "First number" 20 INPUT A 30 PRINT "Second number" 40 INPUT B 50 IF A<0 THEN LET A=-A 60 IF B<0 THEN LET B=-B 70 IF A>B THEN GOTO 130 80 LET B = B - A 90 IF A=0 THEN GOTO 110 100 GOTO 50 110 PRINT B 120 END 130 LET C=A 140 LET A=B 150 LET B=C 160 GOTO 70</lang>
Transact-SQL
<lang Transact-SQL> CREATE OR ALTER FUNCTION [dbo].[PGCD]
( @a BigInt , @b BigInt )
RETURNS BigInt WITH RETURNS NULL ON NULL INPUT -- Calculates the Greatest Common Denominator of two numbers (1 if they are coprime). BEGIN DECLARE @PGCD BigInt;
WITH Vars(A, B) As ( SELECT Max(V.N) As A
, Min(V.N) As B FROM ( VALUES ( Abs(@a) , Abs(@b)) ) Params(A, B) -- First, get absolute value Cross APPLY ( VALUES (Params.A) , (Params.B) ) V(N) -- Then, order parameters without Greatest/Least functions WHERE Params.A > 0 And Params.B > 0 -- If 0 passed in, NULL shall be the output ) , Calc(A, B)
As ( SELECT A
, B FROM Vars
UNION ALL
SELECT B As A , A % B As B -- Self-ordering FROM Calc WHERE Calc.A > 0 And Calc.B > 0 )
SELECT @PGCD = Min(A) FROM Calc WHERE Calc.B = 0
RETURN @PGCD;
END </lang>
True BASIC
<lang basic> REM Solución iterativa FUNCTION gcdI(x, y)
DO WHILE y > 0 LET t = y LET y = remainder(x, y) LET x = t LOOP LET gcdI = x
END FUNCTION
LET a = 111111111111111
LET b = 11111
PRINT PRINT "GCD(";a;", ";b;") = "; gcdI(a, b) PRINT PRINT "GCD(";a;", 111) = "; gcdI(a, 111) END </lang>
TSE SAL
<lang TSE SAL>
// library: math: get: greatest: common: divisor <description>greatest common divisor whole numbers. Euclid's algorithm. Recursive version</description> <version control></version control> <version>1.0.0.0.3</version> <version control></version control> (filenamemacro=getmacdi.s) [<Program>] [<Research>] [kn, ri, su, 20-01-2013 14:22:41] INTEGER PROC FNMathGetGreatestCommonDivisorI( INTEGER x1I, INTEGER x2I )
// IF ( x2I == 0 ) // RETURN( x1I ) // ENDIF // RETURN( FNMathGetGreatestCommonDivisorI( x2I, x1I MOD x2I ) ) //
END
PROC Main()
STRING s1[255] = "353" STRING s2[255] = "46" REPEAT IF ( NOT ( Ask( " = ", s1, _EDIT_HISTORY_ ) ) AND ( Length( s1 ) > 0 ) ) RETURN() ENDIF IF ( NOT ( Ask( " = ", s2, _EDIT_HISTORY_ ) ) AND ( Length( s2 ) > 0 ) ) RETURN() ENDIF Warn( FNMathGetGreatestCommonDivisorI( Val( s1 ), Val( s2 ) ) ) // gives e.g. 1 UNTIL FALSE
END
</lang>
TXR
<lang bash>$ txr -p '(gcd (expt 2 123) (expt 6 49))' 562949953421312</lang>
TypeScript
Iterative implementation <lang javascript>function gcd(a: number, b: number) {
a = Math.abs(a); b = Math.abs(b);
if (b > a) { let 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: number, b: number) {
return b ? gcd_rec(b, a % b) : Math.abs(a);
}</lang>
uBasic/4tH
<lang>Print "GCD of 18 : 12 = "; FUNC(_GCD_Iterative_Euclid(18,12)) Print "GCD of 1071 : 1029 = "; FUNC(_GCD_Iterative_Euclid(1071,1029)) Print "GCD of 3528 : 3780 = "; FUNC(_GCD_Iterative_Euclid(3528,3780))
End
_GCD_Iterative_Euclid Param(2)
Local (1) Do While b@ c@ = a@ a@ = b@ b@ = c@ % b@ Loop
Return (Abs(a@))</lang>
- Output:
GCD of 18 : 12 = 6 GCD of 1071 : 1029 = 21 GCD of 3528 : 3780 = 252 0 OK, 0:205
UNIX Shell
<lang bash>gcd() { # Calculate $1 % $2 until $2 becomes zero. until test 0 -eq "$2"; do # Parallel assignment: set -- 1 2 set -- "$2" "`expr "$1" % "$2"`" done
# Echo absolute value of $1. test 0 -gt "$1" && set -- "`expr 0 - "$1"`" echo "$1" }
gcd -47376 87843
- => 987</lang>
dash or bash
Procedural : <lang bash>gcd() { until test 0 -eq "$2";do set -- "$2" "$(($1 % $2))";done;if [ 0 -gt "$1" ];then echo "$((- $1))";else echo "$1"; fi }
gcd -47376 87843
- => 987</lang>
Recursive :
<lang bash>
gcd () { if [ "$2" -ne 0 ];then gcd "$2" "$(($1 % $2))";else echo "$1";fi }
gcd 100 75
- => 25</lang>
C Shell
<lang csh>alias gcd eval \set gcd_args=( \!*:q ) \\ @ gcd_u=$gcd_args[2] \\ @ gcd_v=$gcd_args[3] \\ while ( $gcd_v != 0 ) \\ @ gcd_t = $gcd_u % $gcd_v \\ @ gcd_u = $gcd_v \\ @ gcd_v = $gcd_t \\ end \\ if ( $gcd_u < 0 ) @ gcd_u = - $gcd_u \\ @ $gcd_args[1]=$gcd_u \\ '\'
gcd result -47376 87843 echo $result
- => 987</lang>
Ursa
<lang ursa>import "math" out (gcd 40902 24140) endl console</lang>
- Output:
34
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
VBA
<lang vb>Function gcd(u As Long, v As Long) As Long
Dim t As Long Do While v t = u u = v v = t Mod v Loop gcd = u
End Function</lang> This function uses repeated subtractions. Simple but not very efficient. <lang VBA>Public Function GCD(a As Long, b As Long) As Long While a <> b
If a > b Then a = a - b Else b = b - a
Wend GCD = a
End Function</lang>
- Output:
Example:
print GCD(1280, 240) 80 print GCD(3475689, 23566319) 7 a=123456789 b=234736437 print GCD((a),(b)) 3
A note on the last example: using brackets forces a and b to be evaluated before GCD is called. Not doing this will cause a compile error because a and b are not the same type as in the function declaration (they are Variant, not Long). Alternatively you can use the conversion function CLng as in print GCD(CLng(a),CLng(b))
VBScript
<lang VBScript>Function GCD(a,b) Do If a Mod b > 0 Then c = a Mod b a = b b = c Else GCD = b Exit Do End If Loop End Function
WScript.Echo "The GCD of 48 and 18 is " & GCD(48,18) & "." WScript.Echo "The GCD of 1280 and 240 is " & GCD(1280,240) & "." WScript.Echo "The GCD of 1280 and 240 is " & GCD(3475689,23566319) & "." WScript.Echo "The GCD of 1280 and 240 is " & GCD(123456789,234736437) & "."</lang>
- Output:
The GCD of 48 and 18 is 6. The GCD of 1280 and 240 is 80. The GCD of 1280 and 240 is 7. The GCD of 1280 and 240 is 3.
Verilog
<lang Verilog>module gcd
( input reset_l, input clk,
input [31:0] initial_u, input [31:0] initial_v, input load,
output reg [31:0] result, output reg busy );
reg [31:0] u, v;
always @(posedge clk or negedge reset_l)
if (!reset_l) begin busy <= 0; u <= 0; v <= 0; end else begin
result <= u + v; // Result (one of them will be zero)
busy <= u && v; // We're still busy...
// Repeatedly subtract smaller number from larger one if (v <= u) u <= u - v; else if (u < v) v <= v - u;
if (load) // Load new problem when high begin u <= initial_u; v <= initial_v; busy <= 1; end
end
endmodule </lang>
Visual Basic
<lang vb>Function GCD(ByVal a As Long, ByVal b As Long) As Long Dim h As Long
If a Then If b Then Do h = a Mod b a = b b = h Loop While b End If GCD = Abs(a) Else GCD = Abs(b) End If
End Function
Sub Main() ' testing the above function
Debug.Assert GCD(12, 18) = 6 Debug.Assert GCD(1280, 240) = 80 Debug.Assert GCD(240, 1280) = 80 Debug.Assert GCD(-240, 1280) = 80 Debug.Assert GCD(240, -1280) = 80 Debug.Assert GCD(0, 0) = 0 Debug.Assert GCD(0, 1) = 1 Debug.Assert GCD(1, 0) = 1 Debug.Assert GCD(3475689, 23566319) = 7 Debug.Assert GCD(123456789, 234736437) = 3 Debug.Assert GCD(3780, 3528) = 252
End Sub</lang>
Vlang
Iterative
<lang go>fn gcd(xx int, yy int) int {
mut x, mut y := xx, yy for y != 0 { x, y = y, x%y } return x
}
fn main() {
println(gcd(33, 77)) println(gcd(49865, 69811))
} </lang>
Builtin
(This is just a wrapper for big.gcd) <lang vlang>import math.big fn gcd(x i64, y i64) i64 {
return big.integer_from_i64(x).gcd(big.integer_from_i64(y)).int()
}
fn main() {
println(gcd(33, 77)) println(gcd(49865, 69811))
}</lang>
- Output in either case:
11 9973
Wortel
Operator <lang wortel>@gcd a b</lang> Number expression <lang wortel>!#~kg a b</lang> Iterative <lang wortel>&[a b] [@vars[t] @while b @:{t b b %a b a t} a]</lang> Recursive <lang wortel>&{gcd a b} ?{b !!gcd b %a b @abs a}</lang>
Wren
<lang ecmascript>var gcd = Fn.new { |x, y|
while (y != 0) { var t = y y = x % y x = t } return x.abs
}
System.print("gcd(33, 77) = %(gcd.call(33, 77))") System.print("gcd(49865, 69811) = %(gcd.call(49865, 69811))")</lang>
- Output:
gcd(33, 77) = 11 gcd(49865, 69811) = 9973
x86 Assembly
Using GNU Assembler syntax: <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>
XBasic
<lang xbasic>' Greatest common divisor PROGRAM "gcddemo" VERSION "0.001"
DECLARE FUNCTION Entry() DECLARE FUNCTION GcdRecursive(u&, v&) DECLARE FUNCTION GcdIterative(u&, v&) DECLARE FUNCTION GcdBinary(u&, v&)
FUNCTION Entry()
m& = 49865 n& = 69811 PRINT "GCD("; LTRIM$(STR$(m&)); ","; n&; "):"; GcdIterative(m&, n&); " (iterative)" PRINT "GCD("; LTRIM$(STR$(m&)); ","; n&; "):"; GcdRecursive(m&, n&); " (recursive)" PRINT "GCD("; LTRIM$(STR$(m&)); ","; n&; "):"; GcdBinary (m&, n&); " (binary)"
END FUNCTION
FUNCTION GcdRecursive(u&, v&)
IF u& MOD v& <> 0 THEN RETURN GcdRecursive(v&, u& MOD v&) ELSE RETURN v& END IF
END FUNCTION
FUNCTION GcdIterative(u&, v&)
DO WHILE v& <> 0 t& = u& u& = v& v& = t& MOD v& LOOP RETURN ABS(u&)
END FUNCTION
FUNCTION GcdBinary(u&, v&)
u& = ABS(u&) v& = ABS(v&) IF u& < v& THEN t& = u& u& = v& v& = t& END IF IF v& = 0 THEN RETURN u& ELSE k& = 1 DO WHILE (u& MOD 2 = 0) && (v& MOD 2 = 0) u& = u& >> 1 v& = v& >> 1 k& = k& << 1 LOOP IF u& MOD 2 = 0 THEN t& = u& ELSE t& = -v& END IF DO WHILE t& <> 0 DO WHILE t& MOD 2 = 0 t& = t& \ 2 LOOP IF t& > 0 THEN u& = t& ELSE v& = -t& END IF t& = u& - v& LOOP RETURN u& * k& END IF
END FUNCTION
END PROGRAM </lang>
- Output:
GCD(49865, 69811): 9973 (iterative) GCD(49865, 69811): 9973 (recursive) GCD(49865, 69811): 9973 (binary)
XLISP
GCD
is a built-in function. If we wanted to reimplement it, one (tail-recursive) way would be like this:
<lang lisp>(defun greatest-common-divisor (x y)
(if (= y 0)
x
(greatest-common-divisor y (mod x y)) ) )</lang>
XPL0
<lang XPL0>include c:\cxpl\codes;
func GCD(U, V); \Return the greatest common divisor of U and V int U, V; int T; [while V do \Euclid's method
[T:= U; U:= V; V:= rem(T/V)];
return abs(U); ];
\Display the GCD of two integers entered on command line IntOut(0, GCD(IntIn(8), IntIn(8)))</lang>
Yabasic
<lang Yabasic>sub gcd(u, v)
local t
u = int(abs(u)) v = int(abs(v)) while(v) t = u u = v v = mod(t, v) wend return u
end sub
print "Greatest common divisor: ", gcd(12345, 9876)</lang>
Z80 Assembly
Uses the iterative subtraction implementation of Euclid's algorithm because the Z80 does not implement modulus or division opcodes. <lang z80>; Inputs: a, b
- Outputs
- a = gcd(a, b)
- Destroys
- c
- Assumes
- a and b are positive one-byte integers
gcd:
cp b ret z ; while a != b
jr c, else ; if a > b
sub b ; a = a - b
jr gcd
else:
ld c, a ; Save a ld a, b ; Swap b into a so we can do the subtraction sub c ; b = b - a ld b, a ; Put a and b back where they belong ld a, c
jr gcd</lang>
zkl
This is a method on integers: <lang zkl>(123456789).gcd(987654321) //-->9</lang> Using the gnu big num library (GMP): <lang zkl>var BN=Import("zklBigNum"); BN(123456789).gcd(987654321) //-->9</lang> or <lang zkl>fcn gcd(a,b){ while(b){ t:=a; a=b; b=t%b } a.abs() }</lang>
ZX Spectrum Basic
<lang zxbasic>10 FOR n=1 TO 3 20 READ a,b 30 PRINT "GCD of ";a;" and ";b;" = "; 40 GO SUB 70 50 NEXT n 60 STOP 70 IF b=0 THEN PRINT ABS (a): RETURN 80 LET c=a: LET a=b: LET b=FN m(c,b): GO TO 70 90 DEF FN m(a,b)=a-INT (a/b)*b 100 DATA 12,16,22,33,45,67</lang>
- Recursion
- Programming Tasks
- Arithmetic operations
- 11l
- 360 Assembly
- 8th
- AArch64 Assembly
- ACL2
- Action!
- ActionScript
- Ada
- Aime
- ALGOL 60
- ALGOL 68
- ALGOL-M
- ALGOL W
- Alore
- AntLang
- APL
- AppleScript
- Applesoft BASIC
- Arendelle
- Arturo
- ATS
- AutoHotkey
- AutoIt
- AWK
- Axe
- BASIC
- IS-BASIC
- Sinclair ZX81 BASIC
- BASIC256
- Batch File
- BBC BASIC
- Bc
- BCPL
- Befunge
- BQN
- Bracmat
- C
- C sharp
- C++
- Boost
- Clojure
- CLU
- COBOL
- Cobra
- CoffeeScript
- Common Lisp
- Component Pascal
- D
- Dc
- Delphi
- Draco
- DWScript
- Dyalect
- E
- EasyLang
- EDSAC order code
- Eiffel
- Elena
- Elixir
- Emacs Lisp
- Erlang
- ERRE
- Euler Math Toolbox
- Euphoria
- Excel
- Ezhil
- F Sharp
- Factor
- FALSE
- Fantom
- Fermat
- Forth
- Fortran
- Free Pascal
- FreeBASIC
- Frege
- Frink
- FunL
- FutureBasic
- GAP
- Genyris
- GFA Basic
- GML
- Gnuplot
- Go
- Golfscript
- Groovy
- GW-BASIC
- Haskell
- HicEst
- Icon
- Unicon
- Icon Programming Library
- J
- Java
- JavaScript
- Joy
- Jq
- Julia
- K
- Klong
- Kotlin
- LabVIEW
- Lambdatalk
- LFE
- Liberty BASIC
- Limbo
- LiveCode
- Logo
- LOLCODE
- LSE
- Lua
- Lucid
- Luck
- M2000 Interpreter
- M4
- Maple
- Mathematica
- Wolfram Language
- MATLAB
- Maxima
- MAXScript
- Mercury
- MINIL
- MiniScript
- MiniZinc
- MIPS Assembly
- МК-61/52
- ML
- MLite
- Standard ML
- Modula-2
- Modula-3
- Monicelli
- MUMPS
- MySQL
- Nanoquery
- NetRexx
- NewLISP
- Nial
- Nim
- Oberon-2
- Objeck
- OCaml
- Octave
- Oforth
- Ol
- Order
- Oz
- PARI/GP
- Pascal
- Perl
- Phix
- PHP
- PicoLisp
- PL/I
- Pop11
- PostScript
- Initlib
- PowerShell
- Prolog
- PureBasic
- Purity
- Python
- Quackery
- Qi
- R
- Racket
- Raku
- Rascal
- Raven
- REBOL
- Retro
- REXX
- Ring
- Ruby
- Run BASIC
- Rust
- Sass/SCSS
- Sather
- S-BASIC
- Scala
- Scheme
- Sed
- Seed7
- SequenceL
- SETL
- Sidef
- Simula
- Slate
- Smalltalk
- SNOBOL4
- Sparkling
- SQL
- Stata
- Swift
- Tcl
- TI-83 BASIC
- TI-89 BASIC
- Tiny BASIC
- Transact-SQL
- True BASIC
- TSE SAL
- TXR
- TypeScript
- UBasic/4tH
- UNIX Shell
- Dash or bash
- C Shell
- Ursa
- Ursala
- V
- VBA
- VBScript
- Verilog
- Visual Basic
- Vlang
- Wortel
- Wren
- X86 Assembly
- XBasic
- XLISP
- XPL0
- Yabasic
- Z80 Assembly
- Zkl
- ZX Spectrum Basic