2,954
edits
(Changed redirect target from Greatest Common Divisor to Or#Extended definition) Tag: Redirect target changed |
(Separate from Or) Tag: Removed redirect |
||
Line 1: | Line 1: | ||
# | {{Built-in|GCD|∧}} is a [[dyadic]] [[scalar function]] which returns the '''[[wikipedia:Greatest common divisor|Greatest Common Divisor]]''' of two integer arguments. It is an extension of [[Or]] which maintains the same results on [[Boolean]] arguments and the same [[identity element]] 1, in the same way that [[LCM]] extends [[And]]. | ||
== Examples == | |||
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. | |||
<source lang=apl> | |||
∘.∨⍨ 0,⍳10 | |||
0 1 2 3 4 5 6 7 8 9 10 | |||
1 1 1 1 1 1 1 1 1 1 1 | |||
2 1 2 1 2 1 2 1 2 1 2 | |||
3 1 1 3 1 1 3 1 1 3 1 | |||
4 1 2 1 4 1 2 1 4 1 2 | |||
5 1 1 1 1 5 1 1 1 1 5 | |||
6 1 2 3 2 1 6 1 2 3 2 | |||
7 1 1 1 1 1 1 7 1 1 1 | |||
8 1 2 1 4 1 2 1 8 1 2 | |||
9 1 1 3 1 1 3 1 1 9 1 | |||
10 1 2 1 2 5 2 1 2 1 10 | |||
</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 <source lang=apl inline>R←X∨Y</source> is chosen so that both <source lang=apl inline>X÷R</source> and <source lang=apl inline>Y÷R</source> are integers (or [[wikipedia:Gaussian integer|Gaussian integers]], when X and/or Y are [[complex]] numbers). | |||
<source lang=apl> | |||
0.6∨13÷3 | |||
0.06666666667 | |||
0.6(13÷3)÷0.6∨13÷3 | |||
9 65 | |||
2J2∨3J1 | |||
1J1 | |||
2J2 3J1÷1J1 | |||
2 2J¯1 | |||
</source>{{Works in|[[Dyalog APL]]}} | |||
== 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 <source 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. | |||
== History == | |||
The use of GCD as an extension of [[Or]], and its extension to complex rational numbers, was proposed by [[Eugene McDonnell]] at [[APL75]].<ref>[[Eugene McDonnell]]. [https://doi.org/10.1145/800117.803810 "A Notation for the GCD and LCM Functions"] ([https://www.jsoftware.com/papers/eem/gcd.htm web]) at [[APL75]].</ref> This definition has become common among many APLs, with [[SHARP APL]], [[Dyalog APL]] (as of [[Dyalog APL 11.0|version 11.0]]), [[J]], [[NARS2000]], [[GNU APL]], [[ngn/apl]], and [[dzaima/APL]] adopting it. However, some APLs, such as [[APL2]] and [[APLX]], keep [[Or]] as a pure [[boolean function]] and do not extend it, while [[K]] uses the | |||
== External links == | |||
=== Documentation === | |||
* [http://help.dyalog.com/17.1/#Language/Primitive%20Functions/Or%20Greatest%20Common%20Divisor.htm Dyalog] | |||
* J [https://www.jsoftware.com/help/dictionary/d101.htm Dictionary], [https://code.jsoftware.com/wiki/Vocabulary/plusdot#dyadic NuVoc] | |||
== References == | |||
<references/> | |||
{{APL built-ins}}[[Category:Primitive functions]][[Category:Scalar dyadic functions]] |