Greatest common divisor: Difference between revisions
Dialects of BASIC moved to the BASIC section.
m (Moved Qi into correct alphabetical order) |
(Dialects of BASIC moved to the BASIC section.) |
||
Line 555:
end hcf</syntaxhighlight>
=={{header|Arendelle}}==
<pre>< a , b >
Line 1,459 ⟶ 1,450:
=={{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,486:
</pre>
===
<syntaxhighlight lang="freebasic">
function gcdp(a, b)
Line 1,544 ⟶ 1,498:
</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|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|FutureBasic}}===
<syntaxhighlight lang="futurebasic">window 1, @"Greatest Common Divisor", (0,0,480,270)
local fn gcd( a as short, b as short ) as short
short result
if ( b != 0 )
result = fn gcd( b, a mod b)
else
result = abs(a)
end if
end fn = result
print fn gcd( 6, 9 )
HandleEvents</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">Procedure GCD(x, y)
Protected r
While y <> 0
r = x % y
x = y
y = r
Wend
ProcedureReturn y
EndProcedure</syntaxhighlight>
====Recursive====
<syntaxhighlight lang="purebasic">Procedure GCD(x, y)
Protected r
r = x % y
If (r > 0)
y = GCD(y, r)
EndIf
ProcedureReturn y
EndProcedure</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,049:
echo GCD {a} {b}
echo.</syntaxhighlight>
=={{header|Bc}}==
Line 2,894 ⟶ 3,364:
=={{header|Free Pascal}}==
See [[#Pascal / Delphi / Free Pascal]].
=={{header|Frege}}==
Line 2,971 ⟶ 3,395:
_gcd( abs(a), abs(b) )</syntaxhighlight>
=={{header|GAP}}==
Line 3,029 ⟶ 3,435:
v = tmp
u</syntaxhighlight>
=={{header|GML}}==
<syntaxhighlight lang="gml">
var n,m,r;
Line 3,204 ⟶ 3,584:
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,517 ⟶ 3,883:
17
</pre>
=={{header|Limbo}}==
<syntaxhighlight lang="limbo">gcd(x: int, y: int): int
{
Line 4,851 ⟶ 5,201:
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 5,263 ⟶ 5,591:
u
end</syntaxhighlight>
=={{header|Rust}}==
Line 5,406 ⟶ 5,724:
end;
end;</syntaxhighlight>
=={{header|Scala}}==
Line 6,268 ⟶ 6,544:
gcd - 5.73969 microseconds per iteration
gcd_bin - 9.25613 microseconds per iteration</pre>
=={{header|Transact-SQL}}==
Line 6,336 ⟶ 6,589:
END
</syntaxhighlight>
=={{header|TSE SAL}}==
Line 6,420 ⟶ 6,647:
return b ? gcd_rec(b, a % b) : Math.abs(a);
}</syntaxhighlight>
=={{header|UNIX Shell}}==
Line 6,547 ⟶ 6,751:
|1071 1029 gcd
=21
=={{header|Verilog}}==
Line 6,649 ⟶ 6,799:
endmodule
</syntaxhighlight>
=={{header|V (Vlang)}}==
Line 6,777 ⟶ 6,887:
leave
ret</syntaxhighlight>
=={{header|XLISP}}==
Line 6,880 ⟶ 6,908:
\Display the GCD of two integers entered on command line
IntOut(0, GCD(IntIn(8), IntIn(8)))</syntaxhighlight>
=={{header|Z80 Assembly}}==
Line 6,930 ⟶ 6,942:
or
<syntaxhighlight lang="zkl">fcn gcd(a,b){ while(b){ t:=a; a=b; b=t%b } a.abs() }</syntaxhighlight>
| |||