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

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 is studied. We conclude that either repeated multiplication by *x* or repeated squaring should be used and the provenance of each technique is established.

**[1]**Richard J. Fateman,*On the computation of powers of sparse polynomials*, Studies in Appl. Math.**53**(1974), 145–155. MR**0341846****[2]**Richard J. Fateman,*Polynomial multiplication, powers and asymptotic analysis: some comments*, SIAM J. Comput.**3**(1974), 196–213. MR**0431778****[3]**W. Morven Gentleman,*Optimal multiplication chains for computing a power of a symbolic polynomial*, Math. Comp.**26**(1972), 935–939. MR**0314303**, 10.1090/S0025-5718-1972-0314303-3**[4]**R. L. Graham, A. C. C. Yao, and F. F. Yao,*Addition chains with multiplicative cost*, Discrete Math.**23**(1978), no. 2, 115–119. MR**523407**, 10.1016/0012-365X(78)90111-5**[5]**Lee E. Heindel,*Computation of powers of multivariate polynomials over the integers*, J. Comput. System Sci.**6**(1972), 1–8. MR**0311148****[6]**Ellis Horowitz and Sartaj Sahni,*The computation of powers of symbolic polynomials*, SIAM J. Comput.**4**(1975), 201–208. MR**0378469****[7]**Donald E. Knuth,*The art of computer programming*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**0378456****[8]**D. P. McCarthy,*The optimal algorithm to evaluate 𝑥ⁿ using elementary multiplication methods*, Math. Comp.**31**(1977), no. 137, 251–256. MR**0428791**, 10.1090/S0025-5718-1977-0428791-X**[9]**Shmuel Winograd,*Arithmetic complexity of computations*, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 33, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1980. MR**565260**

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