A notation for the GCD and LCM functions

ABSTRACT

This paper proposes a notation to be used for the greatest common divisor (gcd) and least common multiple (1cm) functions in APL. The notation proposed is that in use for the logical or and and functions: @@@@ for gcd and &Lgr; for lcm. For this reason, special attention is paid to the cases of gcd and lcm for the arguments 0 and 1. Also, because we wish to define the functions for negative and complex rational values as well as for positive integers, we discuss the functions more generally than is the case in standard number theory texts, which usually restrict their discussions to positive integers. For this reason we give proofs of some of the basic theorems concerning gcd and lcm, written to insure that they are valid for the entire domain of values for which it is proposed the APL functions be defined. The discussion in this paper is couched in terms of integral arguments. The theoretical extension to rational arguments is an easy one, and it is assumed that the gcd and lcm functions, which depend on the residue function for their definitions, will be implemented for non-integral arguments, just as is the residue function, with all the practical difficulties which this entails. In this paper, the terms “greatest” and “least” are taken to refer to magnitudes, and the terms “divisor” and “multiple” mean integer divisor and integer multiple.

REFERENCES

• 1: Birkhoff, G., and S. MacLane, A Survey of Modern Algebra, third edition, Macmillan, New York, 1965
• 2: Greub, W. H., Linear Algebra, third edition, Springer-Verlag, New York, 1967
• 3: Falkoff, A. D., and K. E. Iverson, APL 360 User's Manual, Yorktown Heights, N. Y., 1968
• 4: Iverson, K. E., Algebra: an Algorithmic Treatment, Addison Wesley, Menlo Park, California, 1972
• 5: Kenneth E. Iverson, Formalism in programming languages, Communications of the ACM, v.7 n.2, p.80-88, Feb. 1964 [doi>10.1145/363921.363933]
• 6: McDonnell, E. E., "Complex Floor," APL Congress 73, Gjerlov et al eds., North Holland, Amsterdam, 1973
• 7: MacDuffee, C. C., "On the Concept of Divisor," American Mathematical Monthly, 51, 1944
• 8: Ore, O., Number Theory and its History, McGraw-Hill, N. Y., 1948
• 9: Vinogradov, I. M., Elements of Number Theory, Dover, N. Y., 1954

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: APL

General Terms:
Algorithms, Languages