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

McCarthy, D. P.

doi:10.1090/S0025-5718-1986-0829630-0

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