Effect of improved multiplication efficiency on exponentiation algorithms derived from addition chains
HTML articles powered by AMS MathViewer
- by D. P. McCarthy PDF
- Math. Comp. 46 (1986), 603-608 Request permission
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
- Richard J. Fateman, On the computation of powers of sparse polynomials, Studies in Appl. Math. 53 (1974), 145–155. MR 341846, DOI 10.1002/sapm1974532145
- Richard J. Fateman, Polynomial multiplication, powers and asymptotic analysis: some comments, SIAM J. Comput. 3 (1974), 196–213. MR 431778, DOI 10.1137/0203016
- W. Morven Gentleman, Optimal multiplication chains for computing a power of a symbolic polynomial, Math. Comp. 26 (1972), 935–939. MR 314303, DOI 10.1090/S0025-5718-1972-0314303-3
- 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, DOI 10.1016/0012-365X(78)90111-5
- Lee E. Heindel, Computation of powers of multivariate polynomials over the integers, J. Comput. System Sci. 6 (1972), 1–8. MR 311148, DOI 10.1016/S0022-0000(72)80037-0
- Ellis Horowitz and Sartaj Sahni, The computation of powers of symbolic polynomials, SIAM J. Comput. 4 (1975), 201–208. MR 378469, DOI 10.1137/0204016
- Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
- D. P. McCarthy, The optimal algorithm to evaluate $x^{n}$ using elementary multiplication methods, Math. Comp. 31 (1977), no. 137, 251–256. MR 428791, DOI 10.1090/S0025-5718-1977-0428791-X
- 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
Additional Information
- © Copyright 1986 American Mathematical Society
- Journal: Math. Comp. 46 (1986), 603-608
- MSC: Primary 68Q25
- DOI: https://doi.org/10.1090/S0025-5718-1986-0829630-0
- MathSciNet review: 829630