Greatest common divisor: Difference between revisions
Add bruijn
imported>Msicilia |
(Add bruijn) |
||
| (13 intermediate revisions by 10 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">
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
EndProcedure
Debug GCD(18, 12) ; 6
Debug GCD(1071, 1029) ; 21
Debug GCD(3528, -3780) ; 252
</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,558 ⟶ 2,727:
=={{header|dt}}==
{{works with|dt|1
<syntaxhighlight lang="dt">[
=={{header|DWScript}}==
Line 2,619 ⟶ 2,786:
=={{header|EasyLang}}==
<syntaxhighlight
func gcd a b .
while b <> 0
b =
.
return a
Line 2,893 ⟶ 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 5,492 ⟶ 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,560 ⟶ 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,788 ⟶ 7,013:
return b ? gcd_rec(b, a % b) : Math.abs(a);
}</syntaxhighlight>
== [[:Category:Uiua|Uiua]] ==
<syntaxhighlight>
⊙◌⍢(⊃∘◿:)(±,)
</syntaxhighlight>
=={{header|UNIX Shell}}==
Line 6,984 ⟶ 7,214:
=={{header|Wren}}==
<syntaxhighlight lang="
while (y != 0) {
var t = y
| |||