The accelerated integer GCD algorithm

ABSTRACT

Since the greatest common divisor (GCD) of two integers is a basic arithmetic operation used in many mathematical software systems, new algorithms for its computation are of widespread interest. The accelerated integer GCD algorithm discussed here is based on a reduction step proposed by Sorenson (k-ary reduction), coupled with the dmod operation similar to Norton's smod. Some practical limitations of Sorenson's reduction have been eliminated. Worst-case complexity is still O(n2) for n-bit input, but actual implementations given input about 4096 bits long perform over 5.5 times as fast as the binary GCD on one computer architecture having a multiply instruction. Independent research by Jebelean points to the same conclusions.

REFERENCES

• 1: Bruce W. Char , Keith O. Geddes , Gaston H. Gonnet, GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation, Journal of Symbolic Computation, v.7 n.1, p.31-48, Jan. 1989 [doi>10.1016/S0747-7171(89)80004-5]
• 2: GaANLUND, T. 1991. GNU MP: The GNU multiple precision arithmetic library, ed. 1.1, Free Software Foundation, Cambridge, Mass., Sept.
• 3: HEWLETT-PACKARD. 1992. times(2) on-line manual page. HP~UX Release 9.0, Hewlett-Packard Company, Palo Alto, Calif., Aug.
• 4: Tudor Jebelean, An algorithm for exact division, Journal of Symbolic Computation, v.15 n.2, p.169-180, Feb. 1993 [doi>10.1006/jsco.1993.1012 ]
• 5: JEBELEAN, T. 1993b. Comparing several GCD algorithms. In ARITH-11: IEEE Symposium on Computer Arithmetic (Windsor, Canada, June). IEEE, New York, 180-185.
• 6: T. Jebelean, A generalization of the binary GCD algorithm, Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.111-116, July 06-08, 1993, Kiev, Ukraine [doi>10.1145/164081.164102]
• 7: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 8: G. Norton, A shift-remainder GCD algorithm, Proceedings of the 5th international conference, AAECC-5 on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.350-356, June 1987, Menorca, Spain
• 9: SCH()NHAGE, A. 1971. Schnelle Berechnung yon Kettenbruchentwicklungen. Acta Informatica 1, 2, 139-144.
• 10: Jonathan Sorenson, Two fast GCD algorithms, Journal of Algorithms, v.16 n.1, p.110-144, Jan. 1994 [doi>10.1006/jagm.1994.1006 ]
• 11: STALLMAN, R. 1991. Using and Porting GCC. Free Software Foundation, Cambridge, Mass
• 12: SUN MICROSYSTEMS.1990. 9etrusage(2) on-line manual page. SunOS Release 4.1, Sun Microsystems, Meuntainview, Calif.
• 13: Paul S. Wang, A p-adic algorithm for univariate partial fractions, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.212-217, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806398]
• 14: Kenneth Weber , Paul S. Wang, Parallel integer gcd algorithms and their application to polynomial gcd, 1994

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:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms

Keywords:
GCD, integer greatest common divisor, number-theoretic computations