Greatest common divisor: Difference between revisions
Add bruijn
(Add bruijn) |
|||
(94 intermediate revisions by 35 users not shown) | |||
Line 23:
{{trans|Python}}
<
L v != 0
(u, v) = (v, u % v)
Line 35:
print(gcd(-6, 9))
print(gcd(8, 45))
print(gcd(40902, 24140))</
{{out}}
Line 53:
For maximum compatibility, this program uses only the basic instruction set (S/360)
with 2 ASSIST macros (XDECO,XPRNT).
<
GCD CSECT
USING GCD,R15 use calling register
Line 84:
XDEC DS CL12 temp for edit
YREGS
END GCD</
{{out}}
<pre>
gcd( 1071, 1029)= 21
</pre>
=={{header|PowerPC Assembly}}==
Compile with:
<pre>
gcc -mbig -mregnames -nostartfiles -nodefaultlibs -o gcd gcd.S
</pre>
<syntaxhighlight lang="asm" line="1">
#include <syscall.h>
_gcd_string:
.ascii "gcd("
_gcd_string_len = . - _gcd_string
_gcd_close_string:
.ascii ") = "
_gcd_close_string_len = . - _gcd_close_string
.equiv STDIN, 0
.equiv STDOUT, 1
.align 4
.section ".text"
.global _start
.section ".opd","aw"
.align 3
_start:
.quad ._start,.TOC.@tocbase,0
.previous
.global ._start
._start:
li r30, 1071
li r31, 1029
# move the loaded values into the argument registers
mr r3, r30
mr r4, r31
bl gcd
# save the result for printing later
mr r29, r3
addis r4, r2, _gcd_string@toc@ha
addi r4, r4, _gcd_string@toc@l
li r5, _gcd_string_len
bl print_string
mr r3, r30
bl print_integer
li r3, ','
bl print_char
mr r3, r31
bl print_integer
addis r4, r2, _gcd_close_string@toc@ha
addi r4, r4, _gcd_close_string@toc@l
li r5, _gcd_close_string_len
bl print_string
mr r3, r29
bl print_integer
li r3, '\n'
bl print_char
li r0,SYS_exit # syscall number (sys_exit)
li r3,0 # first argument: exit code
sc # call kernel
gcd:
cmpd r3, r4
bge _gcd
mr r5, r3
mr r3, r4
mr r4, r5
_gcd:
cmpdi r4, 0
beqlr
mr r5, r3
mr r3, r4
modud r4, r5, r4
b _gcd
# r4 is the address of the string
# r5 is the length of the string
print_string:
li r0, SYS_write
li r3, STDOUT
sc
blr
print_char:
mr r4, r3
li r0, SYS_write
li r3, STDOUT
stb r4, -1(sp)
addi r4, sp, -1
li r5, 1
sc
blr
print_integer:
# r3 is the integer to print
# r4 is the working register
# r5 holds the current address to write to the string
# r6 is 10 for division operations
# r7 is working storage
mr r5, sp
li r6, 10
neg r4, r3
cmpdi r3, 0
bne 1f
li r7, '0'
stbu r7, -1(r5)
b 3f
1:
isellt r4, r4, r3 # r4 = abs(r3)
1:
modsd r7, r4, r6
divd r4, r4, r6
addi r7, r7, '0'
stbu r7, -1(r5)
cmpdi r4, 0
beq 1f
b 1b
1:
cmpdi r3, 0
blt 2f
3:
mr r4, r5
subf r5, r5, sp
mflr r14
bl print_string
mtlr r14
blr
2:
li r7, '-'
stbu r7, -1(r5)
b 3b
</syntaxhighlight>
{{out}}
<pre>
gcd(1071,1029) = 21
</pre>
=={{header|8th}}==
<
dup 0 n:= if drop ;; then
tuck \ b a b
Line 105 ⟶ 242:
bye
</syntaxhighlight>
{{out}}
<pre>GCD of 5 and 100 = 5
Line 113 ⟶ 250:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program calPgcd64.s */
Line 256 ⟶ 393:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|ACL2}}==
<
(defun gcd$ (x y)
Line 265 ⟶ 402:
nil)
((zp y) x)
(t (gcd$ y (mod x y)))))</
=={{header|Action!}}==
<
CARD tmp
Line 296 ⟶ 433:
Test(123,1)
Test(0,0)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Greatest_common_divisor.png Screenshot from Atari 8-bit computer]
Line 308 ⟶ 445:
=={{header|ActionScript}}==
<
function gcd(a:int,b:int):int
{
Line 327 ⟶ 464:
}
return a;
}</
=={{header|Ada}}==
<
procedure Gcd_Test is
Line 350 ⟶ 487:
Put_Line("GCD of 5, 100 is" & Integer'Image(Gcd(5, 100)));
Put_Line("GCD of 7, 23 is" & Integer'Image(Gcd(7, 23)));
end Gcd_Test;</
Output:
Line 360 ⟶ 497:
=={{header|Aime}}==
<
o_byte('\n');
o_integer(gcd(49865, 69811));
o_byte('\n');</
=={{header|ALGOL 60}}==
<
comment Greatest common divisor - algol 60;
Line 390 ⟶ 527:
outinteger(1,gcd(21,35))
end
</syntaxhighlight>
{{Out}}
<pre>
Line 402 ⟶ 539:
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of FORMATted transput}}
<
IF a = 0 THEN
b
Line 418 ⟶ 555:
INT c = 49865, d = 69811;
printf(($x"The gcd of"g" and "g" is "gl$,c,d,gcd(c,d)))
)</
Output:
<pre>
Line 426 ⟶ 563:
=={{header|ALGOL-M}}==
<
% RETURN P MOD Q %
Line 457 ⟶ 594:
COMMENT - EXERCISE THE FUNCTION;
WRITE("THE
WRITE("THE
WRITE("THE
WRITE("THE
END</
{{out}}
<pre>THE
THE
THE
THE
</pre>
=={{header|ALGOL W}}==
<
% iterative Greatest Common Divisor routine %
integer procedure gcd ( integer value m, n ) ;
Line 478 ⟶ 615:
a := abs( m );
b := abs( n );
newA := b;
end gcd ;
write( gcd( -21, 35 ) );
end.
</syntaxhighlight>
=={{header|Alore}}==
<
while b != 0
a,b = b, a mod b
end
return Abs(a)
end</
=={{header|AntLang}}==
AntLang has a built-in gcd function.
<syntaxhighlight lang
It is not recommended, but possible to implement it on your own.
<
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]]}</
=={{header|APL}}==
Line 528 ⟶ 661:
By recursion:
<
on gcd(a, b)
if b ≠ 0 then
Line 540 ⟶ 673:
end if
end gcd
</syntaxhighlight>
And just for the sake of it, the same thing iteratively:
<
repeat until (b = 0)
set x to a
Line 553 ⟶ 686:
if (a < 0) then return -a
return a
end hcf</
=={{header|Arendelle}}==
<pre>< a , b >
Line 584 ⟶ 708:
=={{header|Arturo}}==
<syntaxhighlight lang
{{out}}
Line 593 ⟶ 717:
{{works with|ATS|Postiats 0.4.1}}
===Stein’s algorithm, without proofs===
Here is an implementation of Stein’s algorithm, without proofs of termination or correctness.
<syntaxhighlight lang="ats">(********************************************************************)
(*
Line 798 ⟶ 926:
end
(********************************************************************)</
===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.
<
(*
Line 1,020 ⟶ 1,151:
end
(********************************************************************)</
===Euclid’s algorithm, with proof of termination and correctness===
Here is an implementation of Euclid’s algorithm, with a proof of correctness.
<syntaxhighlight 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
(********************************************************************)</syntaxhighlight>
===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.
<syntaxhighlight lang="ats">(* Typecheck this file with ‘patscc -tcats gcd-proofs.dats’. *)
(* Definition of the gcd by Euclid’s algorithm, using subtractions;
Line 1,156 ⟶ 1,526:
else
gcd_isfun__nat_nat__ (pfd, pfe)
end</
=={{header|AutoHotkey}}==
Contributed by Laszlo on the ahk [http://www.autohotkey.com/forum/post-276379.html#276379 forum]
<
Return b=0 ? Abs(a) : Gcd(b,mod(a,b))
}</
Significantly faster than recursion:
<
while b
b := Mod(a | 0x0, a := b)
return a
}</
=={{header|AutoIt}}==
<
_GCD(18, 12)
_GCD(1071, 1029)
Line 1,186 ⟶ 1,556:
WEnd
EndFunc ;==>_GCD
</syntaxhighlight>
Output: <pre>GCD of 18 : 12 = 6
Line 1,194 ⟶ 1,564:
=={{header|AWK}}==
The following scriptlet defines the gcd() function, then reads pairs of numbers from stdin, and reports their gcd on stdout.
<
12 16
4
Line 1,200 ⟶ 1,570:
11
45 67
1</
=={{header|Axe}}==
<
r₁→A
r₂→B
Line 1,210 ⟶ 1,580:
Return
End
GCD(B,A^B)</
=={{header|BASIC}}==
==={{header|Applesoft BASIC}}===
<syntaxhighlight lang="applesoftbasic">0 A = ABS(INT(A))
1 B = ABS(INT(B))
2 GCD =
3 FOR B = B + A * NOT B TO 0 STEP 0
4
5
6 B = A - INT (A / GCD) * GCD
7 NEXT B</syntaxhighlight>
==={{header|
{{trans|FreeBASIC}}
===
<
function gcdI(x, y)
while y
Line 1,280 ⟶ 1,613:
print : print "GCD(";a;", ";b;") = "; gcdI(a, b)
print : print "GCD(";a;", 111) = "; gcdI(a, 111)
end</
{{out}}
<pre>
Line 1,286 ⟶ 1,619:
</pre>
===
<
function gcdp(a, b)
if b = 0 then return a
Line 1,296 ⟶ 1,629:
return gcdp(abs(a), abs(b))
end function
</syntaxhighlight>
==={{header|BBC BASIC}}===
<syntaxhighlight lang="bbcbasic"> DEF FN_GCD_Iterative_Euclid(A%, B%)
LOCAL C%
WHILE B%
C% = A%
A% = B%
B% = C% MOD B%
ENDWHILE
= ABS(A%)</syntaxhighlight>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{trans|BASIC256}}
====Iterative====
<syntaxhighlight lang="qbasic">100 cls
110 a = 40902
120 b = 24140
130 print : print "GCD(";a;", ";b;") = ";gcdi(a,b)
140 print : print "GCD(";a;", 111) = ";gcdi(a,111)
170 end
190 sub gcdi(x,y)
200 while y
210 t = y
220 y = x mod y
230 x = t
240 wend
250 gcdi = x
260 end sub</syntaxhighlight>
==={{header|FreeBASIC}}===
====Iterative solution====
<syntaxhighlight 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</syntaxhighlight>
{{out}}
<pre>GCD(111111111111111, 11111) = 11111
GCD(111111111111111, 111) = 111</pre>
====Recursive solution====
<syntaxhighlight 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</syntaxhighlight>
==={{header|GFA Basic}}===
<syntaxhighlight 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
</syntaxhighlight>
==={{header|GW-BASIC}}===
<syntaxhighlight 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</syntaxhighlight>
==={{header|IS-BASIC}}===
<syntaxhighlight 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)</syntaxhighlight>
==={{header|Liberty BASIC}}===
{{works with|Just BASIC}}
<syntaxhighlight 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
</syntaxhighlight>
==={{header|PureBasic}}===
====Iterative====
<syntaxhighlight lang="purebasic">
Import "" ;msvcrt.lib
AbsI(Quad.q) As "_abs64"
AbsL(Long.l) As "labs"
EndImport
Procedure.i GCD(u.i, v.i)
Protected.i t
While v <> 0
t = v
v = u % v
u = t
Wend
ProcedureReturn AbsI(u) ; Avoid float conversion with Abs(u).
EndProcedure
Debug GCD(18, 12) ; 6
Debug GCD(1071, 1029) ; 21
Debug GCD(3528, -3780) ; 252
</syntaxhighlight>
==={{header|QuickBASIC}}===
{{works with|QuickBASIC|4.5}}
====Iterative====
<syntaxhighlight lang="qbasic">DECLARE FUNCTION gcd (a%, b%)
PRINT gcd(18, 30)
END
FUNCTION gcd (a%, b%)
WHILE b% <> 0
t% = b%
b% = a% MOD b%
a% = t%
WEND
gcd = ABS(a%)
END FUNCTION</syntaxhighlight>
{{out}}
<pre>
6
</pre>
====Recursive====
<syntaxhighlight lang="qbasic">DECLARE FUNCTION gcd (a%, b%)
PRINT gcd(30, 18)
END
FUNCTION gcd (a%, b%)
IF b% = 0 THEN
gcd = ABS(a%)
ELSE
gcd = gcd(b%, a% MOD b%)
END IF
END FUNCTION</syntaxhighlight>
{{out}}
<pre>
6
</pre>
==={{header|Run BASIC}}===
{{works with|Just BASIC}}
<syntaxhighlight lang="runbasic">print abs(gcd(-220,160))
function gcd(gcd,b)
while b
c = gcd
gcd = b
b = c mod b
wend
end function </syntaxhighlight>
==={{header|S-BASIC}}===
<syntaxhighlight 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
</syntaxhighlight>
{{out}}
<pre>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
</pre>
==={{header|Sinclair ZX81 BASIC}}===
<syntaxhighlight 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</syntaxhighlight>
{{out}}
<pre>17</pre>
==={{header|TI-83 BASIC}}, {{header|TI-89 BASIC}}===
gcd(A,B)
The ) can be omitted in TI-83 basic
==={{header|Tiny BASIC}}===
{{works with|TinyBasic}}
<syntaxhighlight lang="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</syntaxhighlight>
==={{header|True BASIC}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic">
REM Iterative solution
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
</syntaxhighlight>
==={{header|uBasic/4tH}}===
{{trans|BBC BASIC}}
<syntaxhighlight lang="text">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@))</syntaxhighlight>
{{out}}
<pre>GCD of 18 : 12 = 6
GCD of 1071 : 1029 = 21
GCD of 3528 : 3780 = 252
0 OK, 0:205</pre>
==={{header|VBA}}===
<syntaxhighlight 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</syntaxhighlight>
This function uses repeated subtractions. Simple but not very efficient.
<syntaxhighlight 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</syntaxhighlight>{{out}}
Example:
<pre>print GCD(1280, 240)
80
print GCD(3475689, 23566319)
7
a=123456789
b=234736437
print GCD((a),(b))
3 </pre>
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))
==={{header|VBScript}}===
<syntaxhighlight 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) & "."</syntaxhighlight>
{{Output}}
<pre>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.</pre>
==={{header|Visual Basic}}===
{{works with|Visual Basic|5}}
{{works with|Visual Basic|6}}
{{works with|VBA|6.5}}
{{works with|VBA|7.1}}
<syntaxhighlight 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</syntaxhighlight>
==={{header|XBasic}}===
{{works with|Windows XBasic}}
<syntaxhighlight 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
</syntaxhighlight>
{{out}}
<pre>
GCD(49865, 69811): 9973 (iterative)
GCD(49865, 69811): 9973 (recursive)
GCD(49865, 69811): 9973 (binary)
</pre>
==={{header|Yabasic}}===
<syntaxhighlight 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)</syntaxhighlight>
==={{header|ZX Spectrum Basic}}===
<syntaxhighlight 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</syntaxhighlight>
=={{header|Batch File}}==
Recursive method
<
@echo off
:gcd
Line 1,322 ⟶ 2,183:
echo Syntax:
echo GCD {a} {b}
echo.</
=={{header|Bc}}==
Line 1,339 ⟶ 2,190:
Utility functions:
<
{
if ( a % 2 == 0 ) {
Line 1,355 ⟶ 2,206:
return(a);
}
}</
'''Iterative (Euclid)'''
<
{
while(v) {
Line 1,366 ⟶ 2,217:
}
return(abs(u));
}</
'''Recursive'''
<
{
if (v) {
Line 1,377 ⟶ 2,228:
return (abs(u));
}
}</
'''Iterative (Binary)'''
<
{
u = abs(u);
Line 1,412 ⟶ 2,263:
}
return (u * k);
}</
=={{header|BCPL}}==
<
let gcd(m,n) = n=0 -> m, gcd(n, m rem n)
Line 1,426 ⟶ 2,277:
show(1071,1029)
show(3528,3780)
$)</
{{out}}
<pre>gcd(18, 12) = 6
Line 1,433 ⟶ 2,284:
=={{header|Befunge}}==
<
:<\g05%p05:_^#</
=={{header|BQN}}==
<
Example:
<syntaxhighlight lang
<pre>7</pre>
=={{header|Bracmat}}==
Bracmat uses the Euclidean algorithm to simplify fractions. The <code>den</code> function extracts the denominator from a fraction.
<
Example:
<pre>{?} gcd$(49865.69811)
{!} 9973</pre>
=={{header|Bruijn}}==
As defined in <code>std/Math</code>.
<syntaxhighlight lang="bruijn">
:import std/Combinator .
:import std/Number .
gcd y [[[=?0 1 (2 0 (1 % 0))]]]
:test ((gcd (+2) (+4)) =? (+2)) ([[1]])
:test ((gcd (+10) (+5)) =? (+5)) ([[1]])
:test ((gcd (+3) (+8)) =? (+1)) ([[1]])
</syntaxhighlight>
=={{header|C}}==
===Iterative Euclid algorithm===
<
gcd_iter(int u, int v) {
if (u < 0) u = -u;
Line 1,458 ⟶ 2,322:
if (v) while ((u %= v) && (v %= u));
return (u + v);
}</
===Recursive Euclid algorithm===
<
return (v != 0)?gcd(v, u%v):u;
}</
===Iterative binary algorithm===
<syntaxhighlight lang="c">int gcd_bin(int u, int v) {
int t, k;
Line 1,481 ⟶ 2,344:
k = 1;
while ((u & 1) == 0 && (v & 1) == 0) { /* u, v - even */
u >>= 1; v >>= 1;
k <<= 1;
Line 1,488 ⟶ 2,351:
t = (u & 1) ? -v : u;
while (t) {
while ((t & 1) == 0)
t >>= 1;
Line 1,499 ⟶ 2,362:
}
return u * k;
}</
=={{header|c sharp|C#}}==
===Iterative===
<
static void Main()
{
Line 1,529 ⟶ 2,392:
return a;
}
</syntaxhighlight>
Example output:
Line 1,551 ⟶ 2,414:
</pre>
===Recursive===
<
static void Main(string[] args)
{
Line 1,575 ⟶ 2,438:
return b==0 ? a : gcd(b, a % b);
}
</syntaxhighlight>
Example output:
Line 1,598 ⟶ 2,461:
=={{header|C++}}==
<
#include <numeric>
int main() {
std::cout << "The greatest common divisor of 12 and 18 is " << std::gcd(12, 18) << " !\n";
}</
{{libheader|Boost}}
<
#include <iostream>
int main() {
std::cout << "The greatest common divisor of 12 and 18 is " << boost::math::gcd(12, 18) << "!\n";
}</
{{out}}
Line 1,620 ⟶ 2,483:
===Euclid's Algorithm===
<
"(gcd a b) computes the greatest common divisor of a and b."
[a b]
(if (zero? b)
a
(recur b (mod a b))))</
That <code>recur</code> call is the same as <code>(gcd b (mod a b))</code>, but makes use of Clojure's explicit tail call optimization.
Line 1,631 ⟶ 2,494:
This can be easily extended to work with variadic arguments:
<
"greatest common divisor of a list of numbers"
[& lst]
(reduce gcd
lst))</
=== Stein's Algorithm (Binary GCD) ===
<
(cond
(zero? a) b
Line 1,646 ⟶ 2,509:
(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))))</
=={{header|CLU}}==
<
while b~=0 do
a, b := b, a//b
Line 1,665 ⟶ 2,528:
|| int$unparse(gcd(as[i], bs[i])))
end
end start_up</
{{out}}
<pre>gcd(18, 12) = 6
Line 1,672 ⟶ 2,535:
=={{header|COBOL}}==
<
PROGRAM-ID. GCD.
Line 1,699 ⟶ 2,562:
END-PERFORM
DISPLAY "The gcd is " A
STOP RUN.</
=={{header|Cobra}}==
<
class Rosetta
def gcd(u as number, v as number) as number
Line 1,716 ⟶ 2,579:
print "gcd of [96] and [27] is [.gcd(27, 96)]"
print "gcd of [51] and [34] is [.gcd(34, 51)]"
</syntaxhighlight>
Output:
Line 1,729 ⟶ 2,592:
Simple recursion
<
gcd = (x, y) ->
if y == 0 then x else gcd y, x % y
</syntaxhighlight>
Since JS has no TCO, here's a version with no recursion
<
gcd = (x, y) ->
[1..(Math.min x, y)].reduce (acc, v) ->
if x % v == 0 and y % v == 0 then v else acc
</syntaxhighlight>
=={{header|Common Lisp}}==
Common Lisp provides a ''gcd'' function.
<
7</
Here is an implementation using the do macro. We call the function <code>gcd*</code> so as not to conflict with <code>common-lisp:gcd</code>.
<
(do () ((zerop b) (abs a))
(shiftf a b (mod a b))))</
Here is a tail-recursive implementation.
<
(if (zerop b)
a
(gcd2 b (mod a b))))</
The last implementation is based on the loop macro.
<
(loop for x = a then y
and y = b then (mod x y)
until (zerop y)
finally (return x)))</
=={{header|Component Pascal}}==
BlackBox Component Builder
<
MODULE Operations;
IMPORT StdLog,Args,Strings;
Line 1,799 ⟶ 2,662:
END Operations.
</syntaxhighlight>
Execute:<br/>
^Q Operations.DoGcd 12 8 ~<br/>
Line 1,814 ⟶ 2,677:
=={{header|D}}==
<
long myGCD(in long x, in long y) pure nothrow @nogc {
Line 1,825 ⟶ 2,688:
gcd(15, 10).writeln; // From Phobos.
myGCD(15, 10).writeln;
}</
{{out}}
<pre>5
Line 1,831 ⟶ 2,694:
=={{header|Dc}}==
<syntaxhighlight lang
This code assumes that there are two integers on the stack.
<pre>dc -e'28 24 [dSa%Lard0<G]dsGx+ p'</pre>
Line 1,839 ⟶ 2,702:
=={{header|Draco}}==
<
word t;
while n ~= 0 do
Line 1,857 ⟶ 2,720:
show(1071, 1029);
show(3528, 3780)
corp</
{{out}}
<pre>gcd(18, 12) = 6
gcd(1071, 1029) = 21
gcd(3528, 3780) = 252</pre>
=={{header|dt}}==
{{works with|dt|1.3.1}}
<syntaxhighlight lang="dt">[[a b]: a [b a b % gcd] b do?] \gcd def</syntaxhighlight>
=={{header|DWScript}}==
<
Output:
<pre>21</pre>
Line 1,872 ⟶ 2,739:
{{trans|Go}}
<
func bgcd(a, b, res) {
if a == b {
Line 1,890 ⟶ 2,757:
return bgcd(a, b, 1)
}
var testdata = [
(a
(a
]
for v in testdata {
print("gcd(\(v
}</
{{out}}
Line 1,908 ⟶ 2,775:
{{trans|Python}}
<
while (v != 0) {
def r := u %% v
Line 1,915 ⟶ 2,782:
}
return u.abs()
}</
=={{header|EasyLang}}==
<syntaxhighlight>
func gcd
while
.
.
</syntaxhighlight>
=={{header|EDSAC order code}}==
The EDSAC had no division instruction,
so the GCD routine below has to include its own code for division.
<
[Greatest common divisor for Rosetta Code.
Program for EDSAC, Initial Orders 2.]
Line 2,085 ⟶ 2,952:
E 14 Z [define entry point]
P F [acc = 0 on entry]
</syntaxhighlight>
{{out}}
<pre>
Line 2,097 ⟶ 2,964:
{{trans|D}}
<
class
APPLICATION
Line 2,125 ⟶ 2,992:
end
</syntaxhighlight>
=={{header|Elena}}==
{{trans|C#}}
ELENA 4.x :
<
import extensions;
Line 2,163 ⟶ 3,030:
printGCD(36,19);
printGCD(36,33);
}</
{{out}}
<pre>
Line 2,178 ⟶ 3,045:
=={{header|Elixir}}==
<
def gcd(a,0), do: abs(a)
def gcd(a,b), do: gcd(b, rem(a,b))
Line 2,184 ⟶ 3,051:
IO.puts RC.gcd(1071, 1029)
IO.puts RC.gcd(3528, 3780)</
{{out}}
Line 2,192 ⟶ 3,059:
</pre>
=={{header|
<syntaxhighlight lang="elm">import Html exposing (Html, div, h1, p, text)
import Html.Attributes exposing (style)
-- Test cases
nr1 : Int
nr1 =
2 * 3 * 5 * 7 * 11
nr2 : Int
nr2 =
7 * 11 * 13 * 17 * 23
main : Html msg
main =
div [ style "margin" "5%", style "font-size" "1.5em", style "color" "blue" ]
[ h1 [ style "font-size" "1.5em" ] [ text "GCD Calculator" ]
, text
("number a = "
++ String.fromInt nr1
++ ", number b = "
++ String.fromInt nr2
)
, p [] [ text ("GCD = " ++ String.fromInt (gcd nr1 nr2)) ]
]
gcd : Int -> Int -> Int
gcd anr bnr =
if bnr /= 0 then
gcd bnr (modBy bnr anr)
else
abs anr
</syntaxhighlight>
{{out}}
<pre>
number a = 2310, number b = 391391
GCD = 77
</pre>
=={{header|Emacs Lisp}}==
<syntaxhighlight lang="lisp">(defun gcd (a b)
(cond
((< a b) (gcd a (- b a)))
((> a b) (gcd (- a b) b))
(t a)))</
=={{header|Erlang}}==
<
-module(gcd).
-export([main/0]).
Line 2,210 ⟶ 3,121:
gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, A rem B).</
{{out}}
<pre>4
Line 2,217 ⟶ 3,128:
=={{header|ERRE}}==
This is a iterative version.
<syntaxhighlight lang="erre">
PROGRAM EUCLIDE
! calculate G.C.D. between two integer numbers
Line 2,239 ⟶ 3,150:
PRINT("G.C.D. between";J%;"and";K%;"is";MCD%)
END PROGRAM
</syntaxhighlight>
{{out}}
Input two numbers : ? 112,44
G.C.D. between 112 and 44 is 4
=={{header|Euler}}==
The original Euler didn't have built-in loops, this defines a while-loop procedure, as in the [[Steady Squares#Euler]] sample.
<br>
'''begin'''
'''new''' while; '''new''' gcd;
while <- ` '''formal''' condition; '''formal''' loopBody;
'''begin'''
'''label''' again;
again: '''if''' condition '''then''' '''begin''' loopBody; '''goto''' again '''end''' '''else''' 0
'''end'''
'
;
gcd <- ` '''formal''' m; '''formal''' n;
'''begin'''
'''new''' a; '''new''' b; '''new''' newA;
a <- '''abs''' m;
b <- '''abs''' n;
while( ` b <> 0 '
, ` '''begin'''
newA <- b;
b <- a '''mod''' b;
a <- newA
'''end'''
'
);
a
'''end'''
'
;
'''out''' gcd( -21, 35 )
'''end''' $
=={{header|Euler Math Toolbox}}==
Line 2,248 ⟶ 3,194:
Non-recursive version in Euler Math Toolbox. Note, that there is a built-in command.
<syntaxhighlight lang="text">
>ggt(123456795,1234567851)
33
Line 2,262 ⟶ 3,208:
>myggt(123456795,1234567851)
33
</syntaxhighlight>
=={{header|Euphoria}}==
{{trans|C/C++}}
===Iterative Euclid algorithm===
<
integer t
while v do
Line 2,279 ⟶ 3,225:
return u
end if
end function</
===Recursive Euclid algorithm===
<
if v then
return gcd(v, remainder(u, v))
Line 2,290 ⟶ 3,236:
return u
end if
end function</
===Iterative binary algorithm===
<
integer t, k
if u < 0 then -- abs(u)
Line 2,332 ⟶ 3,278:
end while
return u * k
end function</
=={{header|Excel}}==
Excel's GCD can handle multiple values. Type in a cell:
<
{{Out|Sample Output}}
This will get the GCD of the first 5 cells of the first row.
Line 2,343 ⟶ 3,289:
=={{header|Ezhil}}==
<syntaxhighlight lang="ezhil">
## இந்த நிரல் இரு எண்களுக்கு இடையிலான மீச்சிறு பொது மடங்கு (LCM), மீப்பெரு பொது வகுத்தி (GCD) என்ன என்று கணக்கிடும்
Line 2,404 ⟶ 3,350:
பதிப்பி "நீங்கள் தந்த இரு எண்களின் மீபொவ (மீப்பெரு பொது வகுத்தி, GCD) = ", மீபொவ(அ, ஆ)
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
<
let rec gcd a b =
if b = 0
Line 2,414 ⟶ 3,360:
>gcd 400 600
val it : int = 200</
=={{header|Factor}}==
<
[ abs ] [
[ nip ] [ mod ] 2bi gcd
] if-zero ;</
=={{header|FALSE}}==
<
=={{header|Fantom}}==
<
class Main
{
Line 2,448 ⟶ 3,394:
}
}
</syntaxhighlight>
=={{header|Fermat}}==
<syntaxhighlight lang
=={{header|Forth}}==
<
begin dup while tuck mod repeat drop ;</
=={{header|Fortran}}==
{{works with|Fortran|95 and later}}
===Recursive Euclid algorithm===
<
integer :: gcd
integer, intent(in) :: u, v
Line 2,469 ⟶ 3,415:
gcd = v
end if
end function gcd_rec</
===Iterative Euclid algorithm===
<
integer, intent(out) :: value
integer, intent(inout) :: u, v
Line 2,483 ⟶ 3,429:
enddo
value = abs(u)
end subroutine gcd_iter</
A different version, and implemented as function
<
integer :: gcd
integer, intent(in) :: v, t
Line 2,501 ⟶ 3,447:
end do
gcd = b ! abs(b)
end function gcd</
===Iterative binary algorithm===
<
integer, intent(out) :: value
integer, intent(inout) :: u, v
Line 2,543 ⟶ 3,489:
enddo
value = u * k
end subroutine gcd_bin</
===Notes on performance===
Line 2,555 ⟶ 3,501:
{{trans|ATS}}
Fortran 2008 introduces new intrinsic functions for integer operations that nowadays usually have hardware support, such as TRAILZ to count trailing zeros.
<
! Translated from my implementation for ATS/Postiats.
Line 2,634 ⟶ 3,580:
write (*, '("gcd (24140, 40902) = ", I0)') gcd (24140, 40902)
end program test_gcd</
{{out}}
Line 2,649 ⟶ 3,595:
=={{header|Free Pascal}}==
See [[#Pascal / Delphi / Free Pascal]].
=={{header|Frege}}==
<
pure native parseInt java.lang.Integer.parseInt :: String -> Int
Line 2,707 ⟶ 3,607:
(a:b:_) = args
println $ gcd' (parseInt a) (parseInt b)
</syntaxhighlight>
=={{header|Frink}}==
Frink has a builtin <CODE>gcd[x,y]</CODE> function that returns the GCD of two integers (which can be arbitrarily large.)
<
println[gcd[12345,98765]]
</syntaxhighlight>
=={{header|FunL}}==
FunL has pre-defined function <code>gcd</code> in module <code>integers</code> defined as:
<
gcd( 0, 0 ) = error( 'integers.gcd: gcd( 0, 0 ) is undefined' )
gcd( a, b ) =
Line 2,725 ⟶ 3,625:
_gcd( a, b ) = _gcd( b, a%b )
_gcd( abs(a), abs(b) )</
=={{header|FutureBasic}}==
This is a nearly-trivial 6-line function, so we've dressed it up a bit to show how easily FB builds a full, interactive application. In FB, when you complete your code and hit RUN, the built app can open in as little as 3 seconds.
[[File:New_app_in_finder.png|200px|frameless]]
It also appears in the dock, where you can run it again with a single click.
[[File:New_app_in_Mac_dock.png|45px|frameless]]
The running app looks like this—we added a button to generate random examples to
process, and an interactive design that instantly responds to each change in an input field.
[[File:Running_app.png|280px|frameless]]
<syntaxhighlight lang="futurebasic">
begin enum 1 // Object tags
_fldA
_ansA
_fldB
_ansB
_rand
end enum
void local fn BuildMacInterface //15-line GUI
window 1, @"Greatest Common Divisor", ( 0, 0, 380, 130 ), NSWindowStyleMaskTitled + NSWindowStyleMaskClosable
textfield _fldA,,, ( 20, 89, 156, 21 )
ControlSetAlignment( _fldA, NSTextAlignmentRight )
ControlSetFormat( _fldA, @"0123456789", Yes, 18, 0 )
textfield _fldB,,, ( 20, 57, 156, 24 )
ControlSetAlignment( _fldB, NSTextAlignmentRight )
ControlSetFormat( _fldB, @"0123456789", Yes, 18, 0 )
textlabel _ansA, @"= ", ( 182, 91, 185, 16 )
textlabel _ansB, @"= ", ( 182, 62, 185, 16 )
button _rand,,,@"Random demo", ( 129, 13, 122, 32 )
menu 1,,, @"File" : menu 1,0,, @"Close", @"w" : MenuItemSetAction(1,0,@"performClose:")
editmenu 2
WindowMakeFirstResponder( 1, _fldA )
end fn
local fn GCD( a as long, b as long ) as long //the requested function
while b
long c = a mod b
a = b : b = c
wend
end fn = a
void local fn DoDialog( ev as Long, tag as long ) //This makes it interactive
long a, b, c
select ev
case _textFieldDidchange //Find GCD of edit fields' contents
a = fn ControlIntegerValue( _fldA )
b = fn ControlIntegerValue( _fldB )
if a + b == 0 then textlabel _ansA, @"= 0" : textlabel _ansB, @"= 0" : exit fn
c = fn GCD( a, b )
textlabel _ansA, fn stringwithformat(@"= %ld x %ld", c, a / c )
textlabel _ansB, fn stringwithformat(@"= %ld x %ld", c, b / c )
case _btnclick //Fill edit fields with random content, then process
select tag
case _rand
c = rnd(65536)
textfield _fldA,,str( c * rnd(65536) )
textfield _fldB,,str( c * rnd(65536) )
fn DoDialog( _textFieldDidchange, 0 )
end select
case _windowWillClose : end
end select
end fn
fn BuildMacInterface
on dialog fn doDialog
handleevents
</syntaxhighlight>
{{output}}
[[File:Screenshot 2023-07-30 at 1.01.00 AM.png]]
=={{header|GAP}}==
<
GcdInt(35, 42);
# 7
Line 2,761 ⟶ 3,721:
GcdInteger(35, 42);
# 7</
=={{header|Genyris}}==
===Recursive===
<
u = (abs u)
v = (abs v)
cond
(equal? v 0) u
else (gcd v (% u v))</
===Iterative===
<
u = (abs u)
v = (abs v)
Line 2,780 ⟶ 3,740:
u = v
v = tmp
u</
=={{header|GML}}==
<syntaxhighlight lang="gml">
var n,m,r;
n = max(argument0,argument1);
Line 2,820 ⟶ 3,754:
}
return a;
</syntaxhighlight>
=={{header|gnuplot}}==
<
Example:
<syntaxhighlight lang
Output:
<syntaxhighlight lang="text">11</
=={{header|Go}}==
===Binary Euclidian===
<
import "fmt"
Line 2,873 ⟶ 3,807:
}
}
</syntaxhighlight>
{{out|Output for Binary Euclidian algorithm}}
<pre>
Line 2,880 ⟶ 3,814:
</pre>
===Iterative===
<
import "fmt"
Line 2,895 ⟶ 3,829:
fmt.Println(gcd(49865, 69811))
}
</syntaxhighlight>
===Builtin===
(This is just a wrapper for <tt>big.GCD</tt>)
<
import (
Line 2,912 ⟶ 3,846:
fmt.Println(gcd(33, 77))
fmt.Println(gcd(49865, 69811))
}</
{{out|Output in either case}}
<pre>
Line 2,920 ⟶ 3,854:
=={{header|Golfscript}}==
<
~{.@\%.}do;</
{{out}}
<pre>
Line 2,929 ⟶ 3,863:
=={{header|Groovy}}==
===Recursive===
<
gcdR = { m, n -> m = m.abs(); n = n.abs(); n == 0 ? m : m%n == 0 ? n : gcdR(n, m%n) }</
===Iterative===
<
Test program:
<
println "gcd(28, 0) = ${gcdR(28, 0)} == ${gcdI(28, 0)}"
println "gcd(0, 28) = ${gcdR(0, 28)} == ${gcdI(0, 28)}"
Line 2,944 ⟶ 3,878:
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)}"</
Output:
Line 2,956 ⟶ 3,890:
gcd(800, 70) = 10 == 10
gcd(27, -70) = 1 == 1</pre>
=={{header|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:
<
gcd x y = gcd_ (abs x) (abs y)
where
gcd_ a 0 = a
gcd_ a b = gcd_ b (a `rem` b)</
=={{header|HicEst}}==
<
IF(b == 0) THEN
gcd = ABS(a)
Line 2,994 ⟶ 3,914:
ENDDO
ENDIF
END</
=={{header|Hoon}}==
<syntaxhighlight lang="hoon">::
:: Greatest common divisor (gcd), Euclid's algorithm.
::
|= [a=@ud b=@ud]
^- @ud
?> (gth b 0)
?: =((mod a b) 0)
b
$(a b, b (mod a b))</syntaxhighlight>
<pre>
An example of use at dojo (assuming the gate is pinned as gcd):
> (gcd 123 36)
3
</pre>
=={{header|Icon}} and {{header|Unicon}}==
<
procedure main(args)
write(gcd(arg[1], arg[2])) | "Usage: gcd n m")
end</
{{libheader|Icon Programming Library}} [http://www.cs.arizona.edu/icon/library/procs/numbers.htm numbers] implements this as:
<
local r
Line 3,015 ⟶ 3,954:
j := r
}
end</
=={{header|J}}==
<syntaxhighlight lang
For example:
<
6</
Note that <code>+.</code> 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).
Line 3,029 ⟶ 3,968:
gcd could also be defined recursively, if you do not mind a little inefficiency:
<
=={{header|Java}}==
From ''javax.swing.table.DefaultTableModel''
<syntaxhighlight lang="java">
/* recursive */
int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
</syntaxhighlight>
===Iterative===
<
long factor= Math.min(a, b);
for(long loop= factor;loop > 1;loop--){
Line 3,041 ⟶ 3,988:
}
return 1;
}</
===Iterative Euclid's Algorithm===
<
public static int gcd(int a, int b) //valid for positive integers.
{
Line 3,055 ⟶ 4,002:
return a;
}
</syntaxhighlight>
===Optimized Iterative===
<
static int gcd(int a,int b)
{
Line 3,067 ⟶ 4,014:
return 1;
}
</syntaxhighlight>
===Iterative binary algorithm===
{{trans|C/C++}}
<
long t, k;
Line 3,100 ⟶ 4,047:
}
return u * k;
}</
===Recursive===
<
if(a == 0) return b;
if(b == 0) return a;
if(a > b) return gcd(b, a % b);
return gcd(a, b % a);
}</
===Built-in===
<
public static long gcd(long a, long b){
return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).longValue();
}</
=={{header|JavaScript}}==
Iterative implementation
<
a = Math.abs(a);
b = Math.abs(b);
Line 3,133 ⟶ 4,080:
if (b === 0) { return a; }
}
}</
Recursive.
<
return b ? gcd_rec(b, a % b) : Math.abs(a);
}</
Implementation that works on an array of integers.
<
var i, y,
n = arr.length,
Line 3,159 ⟶ 4,106:
//For example:
GCD([57,0,-45,-18,90,447]); //=> 3
</syntaxhighlight>
=={{header|Joy}}==
<
=={{header|jq}}==
<
if b == 0 then a
else recursive_gcd(b; a % b)
end ;</
# The subfunction expects [a,b] as input
# i.e. a ~ .[0] and b ~ .[1]
Line 3,174 ⟶ 4,121:
else [.[1], .[0] % .[1]] | rgcd
end;
[a,b] | rgcd ;</
=={{header|Julia}}==
Line 3,185 ⟶ 4,132:
1</pre>
The actual implementation of this function in Julia 0.2's standard library is reproduced here:
<
neg = a < 0
while b != 0
Line 3,194 ⟶ 4,141:
g = abs(a)
neg ? -g : g
end</
(For arbitrary-precision integers, Julia calls a different implementation from the GMP library.)
=={{header|K}}==
===K3===
{{works with|Kona}}
<syntaxhighlight lang="k">gcd:{:[~x;y;_f[y;x!y]]}</syntaxhighlight>
===K6===
{{works with|ngn/k}}
<syntaxhighlight lang="k">gcd:{$[~x;y;o[x!y;x]]}</syntaxhighlight>
=={{header|Klong}}==
<
=={{header|Kotlin}}==
Recursive one line solution:
<
=={{header|LabVIEW}}==
Line 3,214 ⟶ 4,166:
=={{header|Lambdatalk}}==
<
{def gcd
Line 3,245 ⟶ 4,197:
{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
</syntaxhighlight>
=={{header|LFE}}==
Line 3,251 ⟶ 4,203:
{{trans|Clojure}}
<
> (defun gcd
"Get the greatest common divisor."
((a 0) a)
((a b) (gcd b (rem a b))))
</syntaxhighlight>
Usage:
Line 3,269 ⟶ 4,221:
17
</pre>
=={{header|Limbo}}==
<syntaxhighlight lang="limbo">gcd(x: int, y: int): int
{
if(y == 0)
Line 3,293 ⟶ 4,229:
return gcd(y, x % y);
}
</syntaxhighlight>
=={{header|LiveCode}}==
<
repeat until y = 0
put x mod y into z
Line 3,303 ⟶ 4,239:
end repeat
return x
end gcd</
=={{header|Logo}}==
<
if :b = 0 [output :a]
output gcd :b modulo :a :b
end</
=={{header|LOLCODE}}==
<
HOW IZ I gcd YR a AN YR b
Line 3,349 ⟶ 4,285:
VISIBLE I IZ gcd YR 40902 AN YR 24140 MKAY
KTHXBYE</
[https://tio.run/##jVJNU8IwFDw3v2KPOoNOwV48Oal8NAMlTpuK5ZZARMcydVrw79ekrUhlRHNJ3kt2377Ny/Jsla91VQWUoX99Q0jAF2BLMGxWa6QRJOjc7oo4EhF8NplE4OMm/xDxYTIVh/iqD8AXC0CqMs/2O40Pme018mdI4qhjAvWDQP1FYBT4XASI6ShsyqkeOKJZekccJ6X2ZA7OmCfzYS3dRJzdn8Dc8zB1ClP/gMlfYF3HDpLRrLrXrXzTKPeFNm9eS@xeNDJZbHRh276QPajLTk2GgMag2OntO5hY1rXr77Haa5vtVSuIOCwEqz8xy3ObPcFbmEWFfPitlDSULdMZM46Ude1o/DDVeSIE/RIAwsZIDFeKmBPyyGLmz0Zm4szYtUPnubfuoB28gdf3XIRTmhIyFcGTn46q6hM Try it online!]
=={{header|LSE}}==
<syntaxhighlight lang="lse">(*
** MÉTHODE D'EUCLIDE POUR TROUVER LE PLUS GRAND DIVISEUR COMMUN D'UN
** NUMÉRATEUR ET D'UN DÉNOMINATEUR.
Line 3,377 ⟶ 4,313:
&DEMO(6144,8192)
&DEMO(100,5)
&DEMO(7,23)</
Resultats:
Line 3,389 ⟶ 4,325:
=={{header|Lua}}==
{{trans|C}}
<
if b ~= 0 then
return gcd(b, a % b)
Line 3,403 ⟶ 4,339:
demo(100, 5)
demo(5, 100)
demo(7, 23)</
Output:
Line 3,413 ⟶ 4,349:
Faster iterative solution of Euclid:
<
while b~=0 do
a,b=b,a%b
Line 3,419 ⟶ 4,355:
return math.abs(a)
end
</syntaxhighlight>
=={{header|Lucid}}==
===dataflow algorithm===
<
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</
=={{header|Luck}}==
<
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)
)</
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
gcd=lambda (u as long, v as long) -> {
=if(v=0&->abs(u), lambda(v, u mod v))
Line 3,458 ⟶ 4,394:
CheckGCD gcd
CheckGCD gcd_Iterative
</syntaxhighlight>
=={{header|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.
<syntaxhighlight 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</syntaxhighlight>
{{out}}
<pre>0 = 0
34 = 34
34 = 34
34 = 34
34 = 34</pre>
=={{header|Maple}}==
To compute the greatest common divisor of two integers in Maple, use the procedure igcd.
<syntaxhighlight lang
For example,
<syntaxhighlight lang="maple">
> igcd( 24, 15 );
3
</syntaxhighlight>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang
=={{header|MATLAB}}==
<
gcdValue = gcd(integer1, integer2);</
=={{header|Maxima}}==
<
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;</
=={{header|MAXScript}}==
===Iterative Euclid algorithm===
<
(
while b > 0 do
Line 3,497 ⟶ 4,456:
)
abs a
)</
===Recursive Euclid algorithm===
<
(
if b > 0 then gcdRec b (mod a b) else abs a
)</
=={{header|Mercury}}==
===Recursive Euclid algorithm===
<
:- interface.
Line 3,517 ⟶ 4,476:
:- pragma memo(gcd/2).
gcd(A, B) = (if B = integer(0) then A else gcd(B, A mod B)).</
An example console program to demonstrate the gcd module:
<
:- interface.
Line 3,547 ⟶ 4,506:
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).</
Example output:
<
=={{header|min}}==
{{works with|min|0.37.0}}
<syntaxhighlight lang="min">((dup 0 !=) (swap over mod) while pop abs) ^gcd</syntaxhighlight>
=={{header|MINIL}}==
<
00 0E GCD: ENT R0
01 1E ENT R1
Line 3,566 ⟶ 4,529:
0A 1D Stop: DEC R1
0B C2 JNZ Again
0C 80 JZ GCD // Display GCD in R0</
=={{header|MiniScript}}==
Using an iterative Euclidean algorithm:
<
while b
temp = b
Line 3,579 ⟶ 4,542:
end function
print gcd(18,12)</
{{output}}
<pre>6</pre>
=={{header|MiniZinc}}==
<syntaxhighlight 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"];</syntaxhighlight>
{{output}}
<pre>6</pre>
=={{header|MIPS Assembly}}==
<
# a0 and a1 are the two integer parameters
# return value is in v0
Line 3,597 ⟶ 4,584:
done:
move $v0, $t0
jr $ra</
=={{header|МК-61/52}}==
Line 3,609 ⟶ 4,596:
=={{header|ML}}==
==={{header|mLite}}===
<
| (0, b) = b
| (a, b) where (a < b)
Line 3,615 ⟶ 4,602:
| (a, b) = gcd (b, a rem b)
</syntaxhighlight>
==={{header|ML}} / {{header|Standard ML}}===
See also [[#Standard ML]].
<syntaxhighlight lang="sml">fun gcd a 0 = a
| gcd a b = gcd b (a mod b)</syntaxhighlight>
=={{header|Modula-2}}==
<
FROM InOut IMPORT ReadCard, WriteCard, WriteLn, WriteString, WriteBf;
Line 3,647 ⟶ 4,637:
WriteString ("u ="); WriteCard (u, 6); WriteLn;
WriteString ("v ="); WriteCard (v , 6); WriteLn
END ggTkgV.</
Producing the output
<
x = 12
y = 20
Line 3,662 ⟶ 4,652:
kgV = 10455
u = 13773
v = 7137</
=={{header|Modula-3}}==
<
IMPORT IO, Fmt;
Line 3,686 ⟶ 4,676:
IO.Put("GCD of 5, 100 is " & Fmt.Int(GCD(5, 100)) & "\n");
IO.Put("GCD of 7, 23 is " & Fmt.Int(GCD(7, 23)) & "\n");
END GCD.</
Output:
Line 3,694 ⟶ 4,684:
GCD of 7, 23 is 1
</pre>
=={{header|Monicelli}}==
<syntaxhighlight 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!
</syntaxhighlight>
=={{header|MUMPS}}==
<syntaxhighlight lang="mumps">
GCD(A,B)
QUIT:((A/1)'=(A\1))!((B/1)'=(B\1)) 0
Line 3,703 ⟶ 4,720:
IF B'=0
FOR SET T=A#B,A=B,B=T QUIT:B=0 ;ARGUEMENTLESS FOR NEEDS TWO SPACES
QUIT A</
Ouput:
Line 3,717 ⟶ 4,734:
=={{header|MySQL}}==
<
DROP FUNCTION IF EXISTS gcd;
DELIMITER |
Line 3,742 ⟶ 4,759:
SELECT gcd(12345, 9876);
</syntaxhighlight>
+------------------+
Line 3,754 ⟶ 4,771:
{{trans|Java}}
===Iterative===
<
factor = a.min(b)
Line 3,764 ⟶ 4,781:
return 1
end</
===Iterative Euclid's Method===
<
while b > 0
c = a % b
Line 3,774 ⟶ 4,791:
end
return a
end</
=={{header|NetRexx}}==
<
options replace format comments java crossref symbols nobinary
Line 3,784 ⟶ 4,801:
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 3,794 ⟶ 4,811:
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 3,800 ⟶ 4,817:
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 3,846 ⟶ 4,863:
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 3,857 ⟶ 4,874:
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
Line 3,870 ⟶ 4,887:
end i_
return verified
</syntaxhighlight>
{{out}}
<pre>
Line 3,909 ⟶ 4,926:
=={{header|NewLISP}}==
<
→ 12</
=={{header|Nial}}==
Nial provides gcd in the standard lib.
<
|gcd 6 4
=2</
defining it for arrays
<
# one is termination condition
red is cull filter (0 unequal) link [mod [rest, first] , first]
one is or [= [1 first, tally], > [2 first, first]]
gcd is fork [one, first, gcd red] sort <=</
Using it
<
=3</
=={{header|Nim}}==
{{trans|Pascal}}
===Recursive Euclid algorithm===
<
if u mod v != 0:
result = gcd_recursive(v, u mod v)
Line 3,941 ⟶ 4,958:
import strformat
let (x, y) = (49865, 69811)
echo &"gcd({x}, {y}) = {gcd_recursive(49865, 69811)}"</
{{out}}
Line 3,947 ⟶ 4,964:
===Iterative Euclid algorithm===
<
var u = u
var v = v
Line 3,958 ⟶ 4,975:
import strformat
let (x, y) = (49865, 69811)
echo &"gcd({x}, {y}) = {gcd_iterative(49865, 69811)}")</
{{out}}
Line 3,964 ⟶ 4,981:
===Iterative binary algorithm===
<
func gcd_binary*(u, v: int64): int64 =
Line 3,990 ⟶ 5,007:
import strformat
let (x, y) = (49865, 69811)
echo &"gcd({x}, {y}) = {gcd_binary(49865, 69811)}"</
{{out}}
<pre>gcd(49865, 69811) = 9973</pre>
Line 3,996 ⟶ 5,013:
=={{header|Oberon-2}}==
Works with oo2c version 2
<
MODULE GCD;
(* Greatest Common Divisor *)
Line 4,019 ⟶ 5,036:
Out.String("GCD of 40902 and 24140 : ");Out.LongInt(Gcd(40902,24140),4);Out.Ln
END GCD.
</syntaxhighlight>
Output:<br/>
<pre>
Line 4,030 ⟶ 5,047:
=={{header|Objeck}}==
<
bundle Default {
class GDC {
Line 4,054 ⟶ 5,071:
}
}
</syntaxhighlight>
=={{header|OCaml}}==
<
| b -> gcd b (a mod b)</syntaxhighlight>
=== Built-in ===
<
open Big_int;;
let gcd a b =
int_of_big_int (gcd_big_int (big_int_of_int a) (big_int_of_int b))</
=={{header|Octave}}==
<
=={{header|Oforth}}==
gcd is already defined into Integer class :
<syntaxhighlight lang
Source of this method is (see Integer.of file) :
<
=={{header|Ol}}==
<
(print (gcd 1071 1029))
; ==> 21
</syntaxhighlight>
=={{header|Order}}==
{{trans|bc}}
<
#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</
=={{header|Oz}}==
<
fun {UnsafeGCD A B}
if B == 0 then
Line 4,120 ⟶ 5,129:
end
in
{Show {GCD 456 ~632}}</
=={{header|PARI/GP}}==
<syntaxhighlight lang
[[PASCAL]]
Line 4,149 ⟶ 5,158:
===Recursive Euclid algorithm===
{{works with|Free Pascal|version 3.2.0 }}
<
PROGRAM EXRECURGCD.PAS;
Line 4,177 ⟶ 5,186:
END.
</
===Iterative Euclid algorithm===
<
var
t: longint;
Line 4,191 ⟶ 5,200:
end;
gcd_iterative := abs(u);
end;</
===Iterative binary algorithm===
<
var
t, k: longint;
Line 4,233 ⟶ 5,242:
gcd_binary := u * k;
end;
end;</
Demo program:
<
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.</
Output:
<pre>GCD(49865, 69811): 9973 (iterative)
Line 4,251 ⟶ 5,260:
=={{header|Perl}}==
===Iterative Euclid algorithm===
<
my ($u, $v) = @_;
while ($v) {
Line 4,257 ⟶ 5,266:
}
return abs($u);
}</
===Recursive Euclid algorithm===
<
my ($u, $v) = @_;
if ($v) {
Line 4,267 ⟶ 5,276:
return abs($u);
}
}</
===Iterative binary algorithm===
<
my ($u, $v) = @_;
$u = abs($u);
Line 4,299 ⟶ 5,308:
}
return $u * $k;
}</
===Modules===
All three modules will take large integers as input, e.g.
<tt>gcd("68095260063025322303723429387", "51306142182612010300800963053")</tt>. Other possibilities are Math::Cephes euclid, Math::GMPz gcd and gcd_ui.
<
use Math::Prime::Util "gcd";
$gcd = gcd(49865, 69811);
Line 4,315 ⟶ 5,324:
use Math::Pari "gcd";
$gcd = gcd(49865, 69811)->pari2iv
</syntaxhighlight>
===Notes on performance===
<
use Math::BigInt;
use Math::Pari;
Line 4,332 ⟶ 5,341:
'gcd_pari' => sub { Math::Pari::gcd($u,$v)->pari2iv(); },
'gcd_mpu' => sub { Math::Prime::Util::gcd($u,$v); },
});</
Output on 'Intel i3930k 4.2GHz' / Linux / Perl 5.20:
Line 4,349 ⟶ 5,358:
atom parameters allow greater precision, but any fractional parts are immediately and deliberately discarded.<br>
Actually, it is an autoinclude, reproduced below. The first parameter can be a sequence, in which case the second parameter (if provided) is ignored.
<!--<
<span style="color: #008080;">function</span> <span style="color: #7060A8;">gcd</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t</span>
Line 4,370 ⟶ 5,379:
<span style="color: #008080;">return</span> <span style="color: #000000;">u</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</
Sample results
<!--<
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">gcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- 0</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">gcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">24</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">112</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- 8</span>
Line 4,390 ⟶ 5,399:
<span style="color: #000080;font-style:italic;">-- 10000000000000000000</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">gcd</span><span style="color: #0000FF;">({</span><span style="color: #000000;">57</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">45</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span><span style="color: #000000;">90</span><span style="color: #0000FF;">,</span><span style="color: #000000;">447</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- 3</span>
<!--</
=={{header|PHP}}==
===Iterative===
<
function gcdIter($n, $m) {
while(true) {
Line 4,408 ⟶ 5,417:
}
}
</syntaxhighlight>
===Recursive===
<
function gcdRec($n, $m)
{
Line 4,419 ⟶ 5,428:
return abs($n);
}
</syntaxhighlight>
=={{header|PicoLisp}}==
<
(until (=0 B)
(let M (% A B)
(setq A B B M) ) )
(abs A) )</
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
GCD: procedure (a, b) returns (fixed binary (31)) recursive;
declare (a, b) fixed binary (31);
Line 4,438 ⟶ 5,447:
end GCD;
</syntaxhighlight>
=={{header|Pop11}}==
===Built-in gcd===
<
Note: the last argument gives the number of other arguments (in
this case 2).
===Iterative Euclid algorithm===
<
lvars k , l, r = l;
abs(k) -> k;
Line 4,456 ⟶ 5,465:
endwhile;
k -> r;
enddefine;</
=={{header|PostScript}}==
{{libheader|initlib}}
<
/gcd {
{
Line 4,466 ⟶ 5,475:
} loop
}.
</syntaxhighlight>
With no external lib, recursive
<
/gcd {
dup 0 ne {
Line 4,474 ⟶ 5,483:
} { pop } ifelse
} def
</syntaxhighlight>
=={{header|PowerShell}}==
===Recursive Euclid Algorithm===
<
{
if ($x -eq $y) { return $y }
Line 4,495 ⟶ 5,504:
}
return $b
}</
or shorter (taken from Python implementation)
<
if ($y -eq 0) { $x } else { Get-GCD $y ($x%$y) }
}</
===Iterative Euclid Algorithm===
based on Python implementation
<
Function Get-GCD( $x, $y ) {
while ($y -ne 0) {
Line 4,512 ⟶ 5,521:
[Math]::abs($x)
}
</syntaxhighlight>
=={{header|Prolog}}==
===Recursive Euclid Algorithm===
<
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).</
===Repeated Subtraction===
<
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).</
=={{header|Purity}}==
<syntaxhighlight lang="purity">
data Iterate = f => FoldNat <const id, g => $g . $f>
Line 4,572 ⟶ 5,559:
data gcd = Iterate (gcd => uncurry (step (curry $gcd)))
</syntaxhighlight>
=={{header|Python}}==
===Built-in===
{{works with|Python|2.6+}}
<syntaxhighlight lang
{{Works with|Python|3.7}}
(Note that '''fractions.gcd''' is now deprecated in Python 3)
<syntaxhighlight lang
===Iterative Euclid algorithm===
<
while v:
u, v = v, u % v
return abs(u)</
===Recursive Euclid algorithm===
'''Interpreter:''' [[Python]] 2.5
<
return gcd(v, u % v) if v else abs(u)</
===Tests===
Line 4,608 ⟶ 5,595:
===Iterative binary algorithm===
See [[The Art of Computer Programming]] by Knuth (Vol.2)
<
u, v = abs(u), abs(v) # u >= 0, v >= 0
if u < v:
Line 4,630 ⟶ 5,617:
v = -t
t = u - v
return u * k</
===Notes on performance===
Line 4,638 ⟶ 5,625:
<tt>gcd_bin(40902, 24140)</tt> takes us about '''41''' µsec
=={{header|Qi}}==
<syntaxhighlight lang="qi">
(define gcd
A 0 -> A
A B -> (gcd B (MOD A B)))
</syntaxhighlight>
=={{header|Quackery}}==
<syntaxhighlight lang="quackery">
[ [ dup while
tuck mod again ]
drop abs ] is gcd ( n n --> n )
</syntaxhighlight>
=={{header|R}}==
Recursive:
<
ifelse(u %% v != 0, v %gcd% (u%%v), v)
}</
Iterative:
<
while ( (c <- v%%t) != 0 ) {
v <- t
Line 4,665 ⟶ 5,652:
}
t
}</
{{out}}
Same either way.
Line 4,677 ⟶ 5,664:
Racket provides a built-in gcd function. Here's a program that computes the gcd of 14 and 63:
<
(gcd 14 63)</
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.
<
;; given two nonnegative integers, produces their greatest
Line 4,699 ⟶ 5,686:
(* 3 3 7))
(check-equal? (gcd 0 14) 14)
(check-equal? (gcd 13 0) 13))</
=={{header|Raku}}==
Line 4,705 ⟶ 5,692:
===Iterative===
<syntaxhighlight lang="raku"
$a & $b == 0 and fail;
($a, $b) = ($b, $a % $b) while $b;
return abs $a;
}</
===Recursive===
<syntaxhighlight lang="raku"
multi gcd (Int $a, 0) { abs $a }
multi gcd (Int $a, Int $b) { gcd $b, $a % $b }</
===Recursive(inline coderef)===
<syntaxhighlight lang="raku" line>{ $^b ?? &?BLOCK( $^b, $^a % $^b ) !! $^a }</syntaxhighlight>
===Concise===
<syntaxhighlight lang="raku"
===Actually, it's a built-in infix===
<syntaxhighlight lang="raku"
Because it's an infix, you can use it with various meta-operators:
<syntaxhighlight lang="raku"
@alist Zgcd @blist; # lazy zip with gcd
@alist Xgcd @blist; # lazy cross with gcd
@alist »gcd« @blist; # parallel gcd</
=={{header|Rascal}}==
===Iterative Euclidean algorithm===
<
public int gcd_iterative(int a, b){
if(a == 0) return b;
Line 4,738 ⟶ 5,728:
return a;
}
</syntaxhighlight>
An example:
<
rascal>gcd_iterative(1989, 867)
int: 51
</syntaxhighlight>
===Recursive Euclidean algorithm===
<
public int gcd_recursive(int a, b){
return (b == 0) ? a : gcd_recursive(b, a%b);
}
</syntaxhighlight>
An example:
<
rascal>gcd_recursive(1989, 867)
int: 51
</syntaxhighlight>
=={{header|Raven}}==
===Recursive Euclidean algorithm===
<
$v 0 > if
$u $v % $v gcd
Line 4,765 ⟶ 5,755:
$u abs
24140 40902 gcd</
{{out}}<pre>34</pre>
=={{header|REBOL}}==
<
{Returns the greatest common divisor of m and n.}
m [integer!]
Line 4,782 ⟶ 5,772:
]
m
]</
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
= <Prout <Gcd 3528 3780>>;
};
Gcd {
s.M 0 = s.M;
s.M s.N = <Gcd s.N <Mod s.M s.N>>;
};</syntaxhighlight>
{{out}}
<pre>252</pre>
=={{header|Retro}}==
This is from the math extensions library.
<
=={{header|REXX}}==
Line 4,794 ⟶ 5,796:
<br>argument(s), making it easier to use when computing Frobenius numbers (also known as ''postage stamp'' or
<br>''coin'' numbers).
<
numeric digits 2000 /*handle up to 2k decimal dig integers.*/
call gcd 0 0 ; call gcd 55 0 ; call gcd 0 66
Line 4,811 ⟶ 5,813:
say 'GCD (Greatest Common Divisor) of ' translate(space($),",",' ') " is " x
return x</
'''output'''
<pre>
Line 4,832 ⟶ 5,834:
===version 2===
Recursive function (as in PL/I):
<syntaxhighlight lang="rexx">
/* REXX ***************************************************************
* using PL/I code extended to many arguments
Line 4,878 ⟶ 5,880:
Parse Arg a,b
if b = 0 then return abs(a)
return GCD(b,a//b)</
Output:
<pre>
Line 4,897 ⟶ 5,899:
Considerably faster than version 1 (and version 2)
<br>See http://rosettacode.org/wiki/Least_common_multiple#REXX for reasoning.
<
x=abs(arg(1))
do j=2 to arg()
Line 4,909 ⟶ 5,911:
end
end
return x</
=={{header|Ring}}==
<syntaxhighlight lang="text">
see gcd (24, 32)
func gcd gcd, b
Line 4,921 ⟶ 5,923:
end
return gcd
</syntaxhighlight>
=={{header|RPL}}==
≪ '''WHILE''' DUP '''REPEAT''' SWAP OVER MOD '''END''' DROP ABS ≫ '<span style="color:blue">'''GCD'''</span>' STO
40902 24140 <span style="color:blue">'''GCD'''</span>
'''Output:'''
<span style="color:grey">1:</span> 34
===Using unsigned integers===
≪ DUP2 < ≪ SWAP ≫ '''IFT'''
'''WHILE''' DUP B→R '''REPEAT''' SWAP OVER / LAST ROT * - '''END''' DROP
≫ '<span style="color:blue">'''GCD'''</span>' STO
#40902d #24140d <span style="color:blue">'''GCD'''</span>
'''Output:'''
<span style="color:grey">1:</span> #34d
=={{header|Ruby}}==
Line 4,927 ⟶ 5,944:
That is already available as the ''gcd'' method of integers:
<
40902.gcd(24140) # => 34</
Here's an implementation:
<
u, v = u.abs, v.abs
while v > 0
Line 4,937 ⟶ 5,954:
end
u
end</
=={{header|Rust}}==
===num crate===
<
use num::integer::gcd;</
===Iterative Euclid algorithm===
<
while m != 0 {
let old_m = m;
Line 4,962 ⟶ 5,969:
}
n.abs()
}</
===Recursive Euclid algorithm===
<
if m == 0 {
n.abs()
Line 4,971 ⟶ 5,978:
gcd(n % m, m)
}
}</
===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.
<
fn gcd(a: usize, b: usize) -> usize {
match ((a, b), (a & 1, b & 1)) {
Line 4,988 ⟶ 5,995:
_ => unreachable!(),
}
}</
===Tests===
<
println!("{}",gcd(399,-3999));
println!("{}",gcd(0,3999));
Line 4,998 ⟶ 6,005:
3
3999
13</
=={{header|Sass/SCSS}}==
Line 5,004 ⟶ 6,011:
Iterative Euclid's Algorithm
<
@function gcd($a,$b) {
@while $b > 0 {
Line 5,013 ⟶ 6,020:
@return $a;
}
</syntaxhighlight>
=={{header|Sather}}==
{{trans|bc}}
<
gcd_iter(u, v:INT):INT is
Line 5,068 ⟶ 6,075:
end;
end;</
<
main is
a ::= 40902;
Line 5,080 ⟶ 6,087:
#OUT + a.gcd(b) + "\n";
end;
end;</
=={{header|Scala}}==
<
Using pattern matching
<
def gcd(a: Int, b: Int): Int = {
b match {
Line 5,135 ⟶ 6,100:
case _ => gcd(b, (a % b))
}
}</
=={{header|Scheme}}==
<
(if (= b 0)
a
(gcd b (modulo a b))))</
or using the standard function included with Scheme (takes any number of arguments):
<syntaxhighlight lang
=={{header|Sed}}==
<
# gcd.sed Copyright (c) 2010 by Paweł Zuzelski <pawelz@pld-linux.org>
Line 5,457 ⟶ 6,422:
b next
# END OF GSU dc.sed</
=={{header|Seed7}}==
<
result
var integer: gcd is 0;
Line 5,472 ⟶ 6,437:
end while;
gcd := b;
end func;</
Original source: [http://seed7.sourceforge.net/algorith/math.htm#gcd]
=={{header|SequenceL}}==
Tail Recursive Greatest Common Denominator using Euclidian Algorithm
<
a when b = 0
else
gcd(b, a mod b);</
=={{header|SETL}}==
<
print(" the gcd of",a," and ",b," is ",gcd(a,b));
Line 5,491 ⟶ 6,456:
proc gcd (u, v);
return if v = 0 then abs u else gcd (v, u mod v) end;
end;</
Output:
<
the gcd of 49865 and 69811 is 9973</
=={{header|Sidef}}==
===Built-in===
<
say Math.gcd(arr...);</
===Recursive Euclid algorithm===
<
b.is_zero ? a.abs : gcd(b, a % b);
}</
=={{header|Simula}}==
For a recursive variant, see [[Sum multiples of 3 and 5#Simula|Sum multiples of 3 and 5]].
<
INTEGER PROCEDURE GCD(a, b); INTEGER a, b;
BEGIN
Line 5,533 ⟶ 6,498:
OUTIMAGE
END
END</
{{out}}
<pre>(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
Line 5,549 ⟶ 6,514:
Slate's Integer type has gcd defined:
<syntaxhighlight lang
===Iterative Euclid algorithm===
<
"Euclid's algorithm for finding the greatest common divisor."
[| n m temp |
Line 5,560 ⟶ 6,525:
[n isZero] whileFalse: [temp: n. n: m \\ temp. m: temp].
m abs
].</
===Recursive Euclid algorithm===
<
[
y isZero
ifTrue: [x]
ifFalse: [y gcd: x \\ y]
].</
=={{header|Smalltalk}}==
The <tt>Integer</tt> class has its <tt>gcd</tt> method.
<syntaxhighlight lang
An reimplementation of the Iterative Euclid's algorithm would be:
<
gcd_iter := [ :a :b |
Line 5,591 ⟶ 6,556:
].
(gcd_iter value: 40902 value: 24140) printNl.</
=={{header|SNOBOL4}}==
<
gcd ?eq(i,0) :s(freturn)
?eq(j,0) :s(freturn)
Line 5,605 ⟶ 6,570:
output = gcd(1071,1029)
end</
=={{header|Sparkling}}==
<
var f = {};
Line 5,640 ⟶ 6,605:
function LCM(n, k) {
return n * k / GCD(n, k);
}</
=={{header|SQL}}==
Demonstration of Oracle 12c WITH Clause Enhancements
<
create table tbl
(
Line 5,678 ⟶ 6,643:
from tbl
/
</syntaxhighlight>
{{out}}
<pre>
Line 5,715 ⟶ 6,680:
Demonstration of SQL Server 2008
<
@ui INT,
@vi INT
Line 5,758 ⟶ 6,723:
DROP FUNCTION gcd;
</syntaxhighlight>
PostgreSQL function using a recursive common table expression
<
RETURNS integer
LANGUAGE sql
Line 5,772 ⟶ 6,737:
SELECT min(u) FROM x;
$function$
</syntaxhighlight>
{{out}}
Line 5,786 ⟶ 6,751:
=={{header|Standard ML}}==
See also [[#ML / Standard ML]].
<
fun gcd (u, v) =
Line 5,817 ⟶ 6,782:
val () = assert (gcd (~24140, 40902) = 34)
val () = assert (gcd (24140, ~40902) = 34)
val () = assert (gcd (~24140, ~40902) = 34)</
=={{header|Stata}}==
<
a = abs(a_)
b = abs(b_)
Line 5,829 ⟶ 6,794:
}
return(a)
}</
=={{header|Swift}}==
<
func gcd(
var a = abs(a
var b = abs(b)
if (b > a) { swap(&a, &b) }
Line 5,847 ⟶ 6,813:
// Recursive
func gcdr (
var a = abs(a
var b = abs(b)
if (b > a) { swap(&a, &b) }
Line 5,867 ⟶ 6,834:
println("Iterative: GCD of \(a) and \(b) is \(gcd(a, b))")
println("Recursive: GCD of \(a) and \(b) is \(gcdr(a, b))")
}</
{{out}}
<pre>
Line 5,886 ⟶ 6,853:
=={{header|Tcl}}==
===Iterative Euclid algorithm===
<
namespace path {::tcl::mathop ::tcl::mathfunc}
proc gcd_iter {p q} {
Line 5,893 ⟶ 6,860:
}
abs $p
}</
===Recursive Euclid algorithm===
<
if {$q == 0} {
return $p
}
gcd $q [expr {$p % $q}]
}</
With Tcl 8.6, this can be optimized slightly to:
<
if {$q == 0} {
return $p
}
tailcall gcd $q [expr {$p % $q}]
}</
(Tcl does not perform automatic tail-call optimization introduction because that makes any potential error traces less informative.)
===Iterative binary algorithm===
<
namespace path {::tcl::mathop ::tcl::mathfunc}
proc gcd_bin {p q} {
Line 5,933 ⟶ 6,900:
}
return [* $p $k]
}</
===Notes on performance===
<
puts [format "%-8s - %s" $proc [time {$proc $u $v} 100000]]
}</
Outputs:
<pre>gcd_iter - 4.46712 microseconds per iteration
gcd - 5.73969 microseconds per iteration
gcd_bin - 9.25613 microseconds per iteration</pre>
=={{header|Transact-SQL}}==
<syntaxhighlight lang="transact-sql">
CREATE OR ALTER FUNCTION [dbo].[PGCD]
( @a BigInt
Line 6,010 ⟶ 6,954:
END
</syntaxhighlight>
=={{header|TSE SAL}}==
<syntaxhighlight 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]
Line 6,064 ⟶ 6,982:
END
</syntaxhighlight>
=={{header|TXR}}==
<
562949953421312</
=={{header|TypeScript}}==
Iterative implementation
<
a = Math.abs(a);
b = Math.abs(b);
Line 6,089 ⟶ 7,007:
if (b === 0) { return a; }
}
}</
Recursive.
<
return b ? gcd_rec(b, a % b) : Math.abs(a);
}</
== [[:Category:Uiua|Uiua]] ==
<syntaxhighlight>
⊙◌⍢(⊃∘◿:)(±,)
</syntaxhighlight>
=={{header|UNIX Shell}}==
{{works with|Bourne Shell}}
<
# Calculate $1 % $2 until $2 becomes zero.
until test 0 -eq "$2"; do
Line 6,134 ⟶ 7,034:
gcd -47376 87843
# => 987</
==={{header|dash or bash}}===
Procedural :
<
gcd -47376 87843
# => 987</
Recursive :
<
gcd () { if [ "$2" -ne 0 ];then gcd "$2" "$(($1 % $2))";else echo "$1";fi }
gcd 100 75
# => 25</
==={{header|C Shell}}===
<
@ gcd_u=$gcd_args[2] \\
@ gcd_v=$gcd_args[3] \\
Line 6,166 ⟶ 7,066:
gcd result -47376 87843
echo $result
# => 987</
=={{header|Ursa}}==
<
out (gcd 40902 24140) endl console</
{{out}}
<pre>34</pre>
Line 6,180 ⟶ 7,080:
it includes a bit shifting optimization that happens when both operands
are even.
<
gcd = ~&B?\~&Y ~&alh^?\~&arh2faltPrXPRNfabt2RCQ @a ~&ar^?\~&al ^|R/~& ^/~&r remainder</
test program:
<
test = ^(~&,gcd)* <(25,15),(36,16),(120,45),(30,100)></
output:
<pre><
Line 6,222 ⟶ 7,122:
|1071 1029 gcd
=21
=={{header|Verilog}}==
<
(
input reset_l,
Line 6,323 ⟶ 7,169:
endmodule
</syntaxhighlight>
=={{header|
===Iterative===
<syntaxhighlight 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))
}
</syntaxhighlight>
===Builtin===
(This is just a wrapper for <tt>big.gcd</tt>)
<syntaxhighlight lang="v (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))
}</syntaxhighlight>
{{out|Output in either case}}
<pre>
11
9973
</pre>
=={{header|Wortel}}==
Operator
<syntaxhighlight lang
Number expression
<syntaxhighlight lang
Iterative
<
Recursive
<
=={{header|Wren}}==
<
while (y != 0) {
var t = y
Line 6,382 ⟶ 7,220:
x = t
}
return x.abs
}
System.print("gcd(33, 77) = %(gcd.call(33, 77))")
System.print("gcd(49865, 69811) = %(gcd.call(49865, 69811))")</
{{out}}
Line 6,396 ⟶ 7,234:
=={{header|x86 Assembly}}==
Using GNU Assembler syntax:
<
.global pgcd
Line 6,419 ⟶ 7,257:
pop %edx
leave
ret</
=={{header|XLISP}}==
<code>GCD</code> is a built-in function. If we wanted to reimplement it, one (tail-recursive) way would be like this:
<
(if (= y 0)
x
(greatest-common-divisor y (mod x y)) ) )</
=={{header|XPL0}}==
<
func GCD(U, V); \Return the greatest common divisor of U and V
Line 6,522 ⟶ 7,278:
\Display the GCD of two integers entered on command line
IntOut(0, GCD(IntIn(8), IntIn(8)))</
=={{header|Z80 Assembly}}==
Uses the iterative subtraction implementation of Euclid's algorithm because the Z80 does not implement modulus or division opcodes.
<
; Outputs: a = gcd(a, b)
; Destroys: c
Line 6,563 ⟶ 7,303:
ld a, c
jr gcd</
=={{header|Zig}}==
<syntaxhighlight lang="zig">pub fn gcd(u: anytype, v: anytype) @TypeOf(u) {
if (@typeInfo(@TypeOf(u)) != .Int) {
@compileError("non-integer type used on gcd: " ++ @typeName(@TypeOf(u)));
}
if (@typeInfo(@TypeOf(v)) != .Int) {
@compileError("non-integer type used on gcd: " ++ @typeName(@TypeOf(v)));
}
return if (v != 0) gcd(v, @mod(u,v)) else u;
}</syntaxhighlight>
=={{header|zkl}}==
This is a method on integers:
<
Using the gnu big num library (GMP):
<
BN(123456789).gcd(987654321) //-->9</
or
<
|