Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Effect of improved multiplication efficiency on exponentiation algorithms derived from addition chains


Author: D. P. McCarthy
Journal: Math. Comp. 46 (1986), 603-608
MSC: Primary 68Q25
DOI: https://doi.org/10.1090/S0025-5718-1986-0829630-0
MathSciNet review: 829630
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The interaction between the efficiency of the basic multiplication algorithm and the addition chain used to compute $ {x^n}$ is studied. We conclude that either repeated multiplication by x or repeated squaring should be used and the provenance of each technique is established.


References [Enhancements On Off] (What's this?)

  • [1] R. J. Fateman, "On the computation of powers of sparse polynomials," Stud. Appl. Math., v. 53, 1974, pp. 145-155. MR 0341846 (49:6592)
  • [2] R. J. Fateman, "Polynomial multiplication, powers and asymptotic analysis: Some comments," SIAM J. Comput., v. 3, No. 3, 1974, pp. 196-213. MR 0431778 (55:4773)
  • [3] W. M. Gentleman, "Optimal multiplication chains for computing a power of a symbolic polynomial," Math. Comp., v. 26, 1972, pp. 945-949. MR 0314303 (47:2855)
  • [4] R. L. Graham, A. C.-C. Yao & F.-F. Yao, "Addition chains with multiplicative cost," Discrete Math., v. 23, no. 2, 1978, pp. 115-119. MR 523407 (80d:68051)
  • [5] L. Heindel, "Computation of powers of multivariate polynomials over the integers," J. Comput. System Sci., v. 6, 1972, pp. 1-8. MR 0311148 (46:10241)
  • [6] E. Horowitz & S. Sahni, "The computation of powers of symbolic polynomials," SIAM J. Comput., v. 4, 1975, pp. 201-208. MR 0378469 (51:14637)
  • [7] D. Knuth, The Art of Computer Programming--Vol. II, Seminumerical Algorithms, Addison-Wesley, Reading, Mass., 1968. MR 0378456 (51:14624)
  • [8] D. P. McCarthy, "The optimal algorithm to evaluate $ {x^n}$ using elementary multiplication methods," Math. Comp., v. 31, 1977, pp. 251-256. MR 0428791 (55:1811)
  • [9] S. Winograd, Arithmetic Complexity of Computations, CBMS-NSF Regional Conf. Series in Appl. Math., Vol. 33, SIAM, Philadelphia, PA, 1980. MR 565260 (81k:68039)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 68Q25

Retrieve articles in all journals with MSC: 68Q25


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1986-0829630-0
Article copyright: © Copyright 1986 American Mathematical Society

American Mathematical Society