Rosetta Code

Greatest common divisor: Difference between revisions

Page Discussion

Greatest common divisor (view source)

Revision as of 12:37, 14 March 2024

3,770 bytes added ,  2 months ago
Add bruijn
(Added Gambas)
(Add bruijn)
 
(39 intermediate revisions by 16 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 1,503 ⟶ 1,640:
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}}===
Line 1,545 ⟶ 1,702:
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|Gambas}}===
====Iterative solution====
<syntaxhighlight lang="vbnet">Public Sub Main()
Dim a As Long = 111111111111111
Dim b As Long = 11111
Print "\nGCD("; a; ", "; b; ") = "; gcd(a, b)
Print "\nGCD("; a; ", 111) = "; gcd(a, 111)
End
 
Function gcd(x As Long, y As Long) As Long
 
Dim t As Long
While y
t = y
y = x Mod y
x = t
Wend
Return x
 
End Function</syntaxhighlight>
{{out}}
<pre>GCD(111111111111111, 11111) = 11111
GCD(111111111111111, 111) = 111</pre>
 
====Recursive solution====
<syntaxhighlight lang="vbnet">Function gcdp(a As Long, b As Long) As Long
If b = 0 Then Return a
Return gcdp(b, a Mod b)
End Function
Function gcd(a As Long, b As Long) As Long
Return gcdp(Abs(a), Abs(b))
End Function</syntaxhighlight>
 
==={{header|GFA Basic}}===
Line 1,666 ⟶ 1,769:
==={{header|PureBasic}}===
====Iterative====
<syntaxhighlight lang="purebasic">Procedure GCD(x, y)
Import "" ;msvcrt.lib
Protected r
AbsI(Quad.q) As "_abs64"
While y <> 0
AbsL(Long.l) As "labs"
r = x % y
EndImport
x = y
Procedure.i GCD(u.i, v.i)
y = r
Protected.i t
While v <> 0
t = v
v = u % v
u = t
Wend
ProcedureReturn yAbsI(u) ; Avoid float conversion with Abs(u).
EndProcedure</syntaxhighlight>
Debug GCD(18, 12) ; 6
 
Debug GCD(1071, 1029) ; 21
====Recursive====
Debug GCD(3528, -3780) ; 252
<syntaxhighlight lang="purebasic">Procedure GCD(x, y)
</syntaxhighlight>
Protected r
r = x % y
If (r > 0)
y = GCD(y, r)
EndIf
ProcedureReturn y
EndProcedure</syntaxhighlight>
 
==={{header|QuickBASIC}}===
Line 2,198 ⟶ 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,610 ⟶ 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,667 ⟶ 2,786:
=={{header|EasyLang}}==
 
<syntaxhighlight lang="text">
procfunc gcd a b . res .
while b <> 0
h = swap a b
b = ab mod ba
a = h.
return a
.
res = a
.
callprint gcd 120 35 r
print r
</syntaxhighlight>
 
Line 2,942 ⟶ 3,059:
</pre>
 
=={{header|Emacs LispElm}}==
<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 3,466 ⟶ 3,627:
_gcd( abs(a), abs(b) )</syntaxhighlight>
 
=={{header|FutureBASICFutureBasic}}==
This is a nearly-trivial 6-line function, so we've dressed it up a bit to show how easily FutureBASICFB 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.
 
[[New_app_in_finder.png ]]
[[File:New_app_in_finder.png|200px|frameless]]
 
It also appears in the dock, where you can run it again with a single click.
 
[[New_app_in_finder.png]]
[[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]]
[[Running app.png]]
 
<syntaxhighlight lang="futurebasic">
'''CODE'''
begin enum 1 // Object tags
<syntaxhighlight>
_fldA
_ansA
_fldB
_ansB
_rand
end enum
 
void local fn BuildMacInterface //15-line GUI
begin enum 1 // Object tags
window 1, @"Greatest Common Divisor", ( 0, 0, 380, 130 ), NSWindowStyleMaskTitled + NSWindowStyleMaskClosable
_fldA
textfield _fldA,,, ( 20, 89, 156, 21 )
_ansA
ControlSetAlignment( _fldA, NSTextAlignmentRight )
_fldB
ControlSetFormat( _fldA, @"0123456789", Yes, 18, 0 )
_ansB
textfield _fldB,,, ( 20, 57, 156, 24 )
_rand
ControlSetAlignment( _fldB, NSTextAlignmentRight )
end enum
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
void local fn BuildMacInterface //15-line GUI
while b
window 1, @"Greatest Common Divisor", ( 0, 0, 380, 130 ), NSWindowStyleMaskTitled + NSWindowStyleMaskClosable
long c = a mod b
textfield _fldA,,, ( 20, 89, 156, 21 )
a = b : b = c
ControlSetAlignment( _fldA, NSTextAlignmentRight )
wend
ControlSetFormat( _fldA, @"0123456789", Yes, 18, 0 )
end fn = a
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
 
void local fn GCDDoDialog( aev as longLong, btag as long ) as long //theThis makes requestedit functioninteractive
long a, b, c
while b
select ev
long c = a mod b
case _textFieldDidchange //Find GCD of edit fields' contents
a = b : b = c
a = fn ControlIntegerValue( _fldA )
wend
b = fn ControlIntegerValue( _fldB )
end fn = a
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
void local fn DoDialog( ev as Long, tag as long ) //This makes it interactive
on dialog fn doDialog
long a, b, c
handleevents
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, @"=" : textlabel _ansB, @"=" : 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]]
'''OUTPUT'''
{{out}}
<pre>
[[GCD of 814997010 and 4644003.png]] [[GCD of 1234567890 and 9876543210.png]] [[GCD of 51015 and 15051.png]] [[GCD of 1881 and 8118.png]] [[GCD of 42426466 and 2445968527.png ]] [[GCD of 123 and empty field.png]]
</pre>
 
 
 
=={{header|GAP}}==
Line 3,758 ⟶ 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 5,526 ⟶ 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,594 ⟶ 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 6,608 ⟶ 6,799:
<syntaxhighlight lang="swift">// Iterative
 
func gcd(var a: Int, var b: Int) -> Int {
var a = abs(a); b = abs(b)
var b = abs(b)
if (b > a) { swap(&a, &b) }
Line 6,621 ⟶ 6,813:
// Recursive
 
func gcdr (var a: Int, var b: Int) -> Int {
var a = abs(a); b = abs(b)
var b = abs(b)
 
if (b > a) { swap(&a, &b) }
Line 6,820 ⟶ 7,013:
return b ? gcd_rec(b, a % b) : Math.abs(a);
}</syntaxhighlight>
 
== [[:Category:Uiua|Uiua]] ==
<syntaxhighlight>
⊙◌⍢(⊃∘◿:)(±,)
</syntaxhighlight>
 
=={{header|UNIX Shell}}==
Line 7,016 ⟶ 7,214:
 
=={{header|Wren}}==
<syntaxhighlight lang="ecmascriptwren">var gcd = Fn.new { |x, y|
while (y != 0) {
var t = y
Marvin
55

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/347072...361886"