GCD: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
(Changed redirect target from Greatest Common Divisor to Or#Extended definition)
Tag: Redirect target changed
(→‎History: SHARP implementation year)
 
(8 intermediate revisions by 2 users not shown)
Line 1: Line 1:
#REDIRECT [[Or#Extended_definition]]
{{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]] 0, 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.
 
<syntaxhighlight 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
</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</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>
      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
</syntaxhighlight>{{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 <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.
 
== 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> 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 ==
 
=== Documentation ===
 
* [https://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]]

Latest revision as of 21:37, 17 February 2024

∨

GCD (∨) is a dyadic scalar function which returns the 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 0, 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. 

      ∘.∨⍨ 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
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 R←X∨Y is chosen so that both X÷R and Y÷R are integers (or Gaussian integers, when X and/or Y are complex numbers). 

      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
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 0 0≡(a∨b)|a,b.

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.[1] Implemented by SHARP APL in 1980,[2] this definition has become common among many APLs, with Dyalog APL (as of 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

Documentation

References

  1. ↑ Eugene McDonnell. "A Notation for the GCD and LCM Functions" (web) at APL75.
  2. ↑ IPSA. SHARP APL Reference Manual Additions and Corrections, June 1981
APL built-ins [edit]
Primitives (Timeline) Functions
Scalar
Monadic Conjugate ∙ Negate ∙ Signum ∙ Reciprocal ∙ Magnitude ∙ Exponential ∙ Natural Logarithm ∙ Floor ∙ Ceiling ∙ Factorial ∙ Not ∙ Pi Times ∙ Roll ∙ Type ∙ Imaginary ∙ Square Root ∙ Round
Dyadic Add ∙ Subtract ∙ Times ∙ Divide ∙ Residue ∙ Power ∙ Logarithm ∙ Minimum ∙ Maximum ∙ Binomial ∙ Comparison functions ∙ Boolean functions (And, Or, Nand, Nor) ∙ GCD ∙ LCM ∙ Circular ∙ Complex ∙ Root
Non-Scalar
Structural Shape ∙ Reshape ∙ Tally ∙ Depth ∙ Ravel ∙ Enlist ∙ Table ∙ Catenate ∙ Reverse ∙ Rotate ∙ Transpose ∙ Raze ∙ Mix ∙ Split ∙ Enclose ∙ Nest ∙ Cut (K) ∙ Pair ∙ Link ∙ Partitioned Enclose ∙ Partition
Selection First ∙ Pick ∙ Take ∙ Drop ∙ Unique ∙ Identity ∙ Stop ∙ Select ∙ Replicate ∙ Expand ∙ Set functions (Intersection ∙ Union ∙ Without) ∙ Bracket indexing ∙ Index ∙ Cartesian Product ∙ Sort
Selector Index generator ∙ Grade ∙ Index Of ∙ Interval Index ∙ Indices ∙ Deal ∙ Prefix and suffix vectors
Computational Match ∙ Not Match ∙ Membership ∙ Find ∙ Nub Sieve ∙ Encode ∙ Decode ∙ Matrix Inverse ∙ Matrix Divide ∙ Format ∙ Execute ∙ Materialise ∙ Range
Operators Monadic Each ∙ Commute ∙ Constant ∙ Replicate ∙ Expand ∙ Reduce ∙ Windowed Reduce ∙ Scan ∙ Outer Product ∙ Key ∙ I-Beam ∙ Spawn ∙ Function axis ∙ Identity (Null, Ident)
Dyadic Bind ∙ Compositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner Product ∙ Determinant ∙ Power ∙ At ∙ Under ∙ Rank ∙ Depth ∙ Variant ∙ Stencil ∙ Cut ∙ Direct definition (operator) ∙ Identity (Lev, Dex)
Quad names Index origin ∙ Comparison tolerance ∙ Migration level ∙ Atomic vector
Retrieved from ‘https://aplwiki.com/index.php?title=GCD&oldid=10965’