Rosetta Code

Greatest common divisor: Difference between revisions

Page Discussion

Greatest common divisor (view source)

Revision as of 12:37, 14 March 2024

4,914 bytes added ,  2 months ago
Add bruijn
(Improved example moved to main page)
(Add bruijn)
 
(27 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,612 ⟶ 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,144 ⟶ 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,556 ⟶ 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,613 ⟶ 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,888 ⟶ 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,412 ⟶ 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.
 
[[File:New_app_in_finder.png|200px|frameless]]
Line 3,426 ⟶ 3,641:
[[File:Running_app.png|280px|frameless]]
 
<syntaxhighlight lang="FutureBASICfuturebasic">
begin enum 1 // Object tags
_fldA
Line 3,464 ⟶ 3,679:
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 )
Line 3,483 ⟶ 3,698:
on dialog fn doDialog
handleevents
 
</syntaxhighlight>
{{output}}
[[File:GCD_of_1234567890_and_9876543210Screenshot 2023-07-30 at 1.01.00 AM.png|200px|framed]]
 
=={{header|GAP}}==
Line 3,701 ⟶ 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,469 ⟶ 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,537 ⟶ 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,551 ⟶ 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,564 ⟶ 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,763 ⟶ 7,013:
return b ? gcd_rec(b, a % b) : Math.abs(a);
}</syntaxhighlight>
 
== [[:Category:Uiua|Uiua]] ==
<syntaxhighlight>
⊙◌⍢(⊃∘◿:)(±,)
</syntaxhighlight>
 
=={{header|UNIX Shell}}==
Line 6,959 ⟶ 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/347094...361886"