2,954
edits
GCD: Difference between revisions
Jump to navigation
Jump to search
→History: SHARP implementation year
m (Text replacement - "<source" to "<syntaxhighlight") |
(→History: SHARP implementation year) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 18: | Line 18: | ||
9 1 1 3 1 1 3 1 1 9 1 | 9 1 1 3 1 1 3 1 1 9 1 | ||
10 1 2 1 2 5 2 1 2 1 10 | 10 1 2 1 2 5 2 1 2 1 10 | ||
</ | </syntaxhighlight>{{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 <syntaxhighlight lang=apl inline>R←X∨Y</ | 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</syntaxhighlight> is chosen so that both <syntaxhighlight lang=apl inline>X÷R</syntaxhighlight> and <syntaxhighlight lang=apl inline>Y÷R</syntaxhighlight> are integers (or [[wikipedia:Gaussian integer|Gaussian integers]], when X and/or Y are [[complex]] numbers). | ||
<syntaxhighlight lang=apl> | <syntaxhighlight lang=apl> | ||
| Line 31: | Line 31: | ||
2J2 3J1÷1J1 | 2J2 3J1÷1J1 | ||
2 2J¯1 | 2 2J¯1 | ||
</ | </syntaxhighlight>{{Works in|[[Dyalog APL]]}} | ||
== 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 <syntaxhighlight lang=apl inline>0 0≡(a∨b)|a,b</ | 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</syntaxhighlight>. | ||
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. | ||
| Line 41: | Line 41: | ||
== History == | == 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> | 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> Implemented by [[SHARP APL]] in 1980,<ref>IPSA. [https://www.softwarepreservation.org/projects/apl/Manuals/SharpAPLManualCorrections/view SHARP APL Reference Manual Additions and Corrections, June 1981]</ref> this definition has become common among many APLs, with [[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]], [[APLX]], and [[Kap]], keep [[Or]] as a pure [[boolean function]] and do not extend it, while [[K]] uses the [[Maximum]] function as Or. | ||
== External links == | == External links == | ||