Greatest common divisor: Difference between revisions
Add bruijn
(→{{header|Tiny BASIC}}: Works with (Tom Pittman's) TinyBasic.) |
(Add bruijn) |
||
| (62 intermediate revisions by 25 users not shown) | |||
Line 88:
<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>
Line 457 ⟶ 594:
COMMENT - EXERCISE THE FUNCTION;
WRITE("THE
WRITE("THE
WRITE("THE
WRITE("THE
END</syntaxhighlight>
{{out}}
<pre>THE
THE
THE
THE
</pre>
Line 478 ⟶ 615:
a := abs( m );
b := abs( n );
newA := b;
end gcd ;
write( gcd( -21, 35 ) );
end.
</syntaxhighlight>
=={{header|Alore}}==
Line 555 ⟶ 688:
end hcf</syntaxhighlight>
=={{header|Arendelle}}==
<pre>< a , b >
Line 1,459 ⟶ 1,583:
=={{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}}
===
<syntaxhighlight lang="freebasic">
function gcdI(x, y)
Line 1,532 ⟶ 1,619:
</pre>
===
<syntaxhighlight lang="freebasic">
function gcdp(a, b)
Line 1,544 ⟶ 1,631:
</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}}==
Line 1,569 ⟶ 2,184:
echo GCD {a} {b}
echo.</syntaxhighlight>
=={{header|Bc}}==
Line 1,695 ⟶ 2,300:
<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}}==
Line 2,107 ⟶ 2,725:
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}}==
Line 2,164 ⟶ 2,786:
=={{header|EasyLang}}==
<syntaxhighlight
func gcd
while
.
.
=={{header|EDSAC order code}}==
Line 2,437 ⟶ 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
Line 2,488 ⟶ 3,154:
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,894 ⟶ 3,595:
=={{header|Free Pascal}}==
See [[#Pascal / Delphi / Free Pascal]].
=={{header|Frege}}==
Line 2,971 ⟶ 3,626:
_gcd( abs(a), abs(b) )</syntaxhighlight>
=={{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}}==
Line 3,029 ⟶ 3,741:
v = tmp
u</syntaxhighlight>
=={{header|GML}}==
<syntaxhighlight lang="gml">
var n,m,r;
Line 3,204 ⟶ 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:
Line 3,243 ⟶ 3,915:
ENDIF
END</syntaxhighlight>
=={{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}}==
Line 3,280 ⟶ 3,971:
=={{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===
<syntaxhighlight lang="java">public static long gcd(long a, long b){
Line 3,446 ⟶ 4,145:
=={{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}}==
Line 3,517 ⟶ 4,221:
17
</pre>
=={{header|Limbo}}==
<syntaxhighlight lang="limbo">gcd(x: int, y: int): int
{
Line 3,822 ⟶ 4,510:
Example output:
<syntaxhighlight lang="bash">gcd(70000000000000000000000, 60000000000000000000000000) = 10000000000000000000000</syntaxhighlight>
=={{header|min}}==
{{works with|min|0.37.0}}
<syntaxhighlight lang="min">((dup 0 !=) (swap over mod) while pop abs) ^gcd</syntaxhighlight>
=={{header|MINIL}}==
Line 4,382 ⟶ 5,074:
=={{header|OCaml}}==
<syntaxhighlight lang="ocaml">let rec gcd a
| b -> gcd b (a mod b)</syntaxhighlight>
=== Built-in ===
Line 4,851 ⟶ 5,535:
gcd(X, Y, D):- X =< Y, !, Z is Y - X, gcd(X, Z, D).
gcd(X, Y, D):- gcd(Y, X, D).</syntaxhighlight>
=={{header|Purity}}==
Line 4,963 ⟶ 5,625:
<tt>gcd_bin(40902, 24140)</tt> takes us about '''41''' µsec
=={{header|Qi}}==
Line 4,976 ⟶ 5,631:
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>
Line 5,040 ⟶ 5,702:
multi gcd (Int $a, 0) { abs $a }
multi gcd (Int $a, Int $b) { gcd $b, $a % $b }</syntaxhighlight>
===Recursive(inline coderef)===
<syntaxhighlight lang="raku" line>{ $^b ?? &?BLOCK( $^b, $^a % $^b ) !! $^a }</syntaxhighlight>
===Concise===
Line 5,108 ⟶ 5,773:
m
]</syntaxhighlight>
=={{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}}==
Line 5,247 ⟶ 5,924:
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 5,263 ⟶ 5,955:
u
end</syntaxhighlight>
=={{header|Rust}}==
Line 5,406 ⟶ 6,088:
end;
end;</syntaxhighlight>
=={{header|Scala}}==
Line 6,159 ⟶ 6,799:
<syntaxhighlight lang="swift">// Iterative
func gcd(
var a = abs(a
var b = abs(b)
if (b > a) { swap(&a, &b) }
Line 6,172 ⟶ 6,813:
// Recursive
func gcdr (
var a = abs(a
var b = abs(b)
if (b > a) { swap(&a, &b) }
Line 6,268 ⟶ 6,910:
gcd - 5.73969 microseconds per iteration
gcd_bin - 9.25613 microseconds per iteration</pre>
=={{header|Transact-SQL}}==
Line 6,336 ⟶ 6,955:
END
</syntaxhighlight>
=={{header|TSE SAL}}==
Line 6,421 ⟶ 7,014:
}</syntaxhighlight>
== [[:Category:Uiua|Uiua]] ==
<syntaxhighlight>
⊙◌⍢(⊃∘◿:)(±,)
</syntaxhighlight>
=={{header|UNIX Shell}}==
Line 6,547 ⟶ 7,122:
|1071 1029 gcd
=21
=={{header|Verilog}}==
Line 6,649 ⟶ 7,170:
endmodule
</syntaxhighlight>
=={{header|V (Vlang)}}==
Line 6,733 ⟶ 7,214:
=={{header|Wren}}==
<syntaxhighlight lang="
while (y != 0) {
var t = y
Line 6,777 ⟶ 7,258:
leave
ret</syntaxhighlight>
=={{header|XLISP}}==
Line 6,880 ⟶ 7,279:
\Display the GCD of two integers entered on command line
IntOut(0, GCD(IntIn(8), IntIn(8)))</syntaxhighlight>
=={{header|Z80 Assembly}}==
Line 6,921 ⟶ 7,304:
jr gcd</syntaxhighlight>
=={{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}}==
Line 6,930 ⟶ 7,324:
or
<syntaxhighlight lang="zkl">fcn gcd(a,b){ while(b){ t:=a; a=b; b=t%b } a.abs() }</syntaxhighlight>
| |||