4,494
edits
GCD: Difference between revisions
Jump to navigation
Jump to search
m
Text replacement - "<source" to "<syntaxhighlight"
m (Text replacement - "http://help.dyalog.com" to "https://help.dyalog.com") |
m (Text replacement - "<source" to "<syntaxhighlight") |
||
| Line 5: | Line 5: | ||
For positive integer arguments, the GCD is the largest positive number which divides both numbers. If one of the arguments is zero, the GCD function returns the other number. | For positive integer arguments, the GCD is the largest positive number which divides both numbers. If one of the arguments is zero, the GCD function returns the other number. | ||
< | <syntaxhighlight lang=apl> | ||
∘.∨⍨ 0,⍳10 | ∘.∨⍨ 0,⍳10 | ||
0 1 2 3 4 5 6 7 8 9 10 | 0 1 2 3 4 5 6 7 8 9 10 | ||
| Line 20: | Line 20: | ||
</source>{{Works in|[[Dyalog APL]]}} | </source>{{Works in|[[Dyalog APL]]}} | ||
While the mathematical definition of GCD does not cover non-integers, some implementations accept them as arguments. In this case, the return value of < | While the mathematical definition of GCD does not cover non-integers, some implementations accept them as arguments. In this case, the return value of <syntaxhighlight lang=apl inline>R←X∨Y</source> is chosen so that both <syntaxhighlight lang=apl inline>X÷R</source> and <syntaxhighlight lang=apl inline>Y÷R</source> are integers (or [[wikipedia:Gaussian integer|Gaussian integers]], when X and/or Y are [[complex]] numbers). | ||
< | <syntaxhighlight lang=apl> | ||
0.6∨13÷3 | 0.6∨13÷3 | ||
0.06666666667 | 0.06666666667 | ||
| Line 35: | Line 35: | ||
== Description == | == Description == | ||
If both arguments are integers, the GCD is the greatest positive integer which divides both numbers evenly, or 0 if both arguments are 0. That is, each argument is an integer multiple of the GCD of both arguments. Under this definition, any number is considered a divisor of 0, because multiplying it by 0 results in 0. Using [[Residue]], we might also write the divisibility criterion as < | If both arguments are integers, the GCD is the greatest positive integer which divides both numbers evenly, or 0 if both arguments are 0. That is, each argument is an integer multiple of the GCD of both arguments. Under this definition, any number is considered a divisor of 0, because multiplying it by 0 results in 0. Using [[Residue]], we might also write the divisibility criterion as <syntaxhighlight lang=apl inline>0 0≡(a∨b)|a,b</source>. | ||
Because 1 divides every integer, there is always some common divisor of any pair of arguments, and the GCD is well-defined. The [[identity element]] for GCD is 0 on the domain of non-negative real numbers, because the other argument will always be a divisor of 0, and so it is returned as the result (for an arbitrary real number, the result is its [[absolute value]]). Because 1 is the only positive divisor of itself, the GCD of 1 and any other number is 1. | Because 1 divides every integer, there is always some common divisor of any pair of arguments, and the GCD is well-defined. The [[identity element]] for GCD is 0 on the domain of non-negative real numbers, because the other argument will always be a divisor of 0, and so it is returned as the result (for an arbitrary real number, the result is its [[absolute value]]). Because 1 is the only positive divisor of itself, the GCD of 1 and any other number is 1. | ||