Effect of improved multiplication efficiency on exponentiation algorithms derived from addition chains
Author:
D. P. McCarthy
Journal:
Math. Comp. 46 (1986), 603608
MSC:
Primary 68Q25
MathSciNet review:
829630
Fulltext 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
(49 #6592)
 [2]
Richard
J. Fateman, Polynomial multiplication, powers and asymptotic
analysis: some comments, SIAM J. Comput. 3 (1974),
196–213. MR 0431778
(55 #4773)
 [3]
W.
Morven Gentleman, Optimal multiplication chains for
computing a power of a symbolic polynomial, Math. Comp. 26 (1972), 935–939. MR 0314303
(47 #2855), http://dx.doi.org/10.1090/S00255718197203143033
 [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
(80d:68051), http://dx.doi.org/10.1016/0012365X(78)901115
 [5]
Lee
E. Heindel, Computation of powers of multivariate polynomials over
the integers, J. Comput. System Sci. 6 (1972),
1–8. MR
0311148 (46 #10241)
 [6]
Ellis
Horowitz and Sartaj
Sahni, The computation of powers of symbolic polynomials, SIAM
J. Comput. 4 (1975), 201–208. MR 0378469
(51 #14637)
 [7]
Donald
E. Knuth, The art of computer programming, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass.LondonAmsterdam, 1975.
Volume 1: Fundamental algorithms; AddisonWesley Series in Computer Science
and Information Processing. MR 0378456
(51 #14624)
 [8]
D.
P. McCarthy, The optimal algorithm to evaluate
𝑥ⁿ using elementary multiplication methods, Math. Comp. 31 (1977), no. 137, 251–256. MR 0428791
(55 #1811), http://dx.doi.org/10.1090/S0025571819770428791X
 [9]
Shmuel
Winograd, Arithmetic complexity of computations, CBMSNSF
Regional Conference Series in Applied Mathematics, vol. 33, Society
for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1980. MR 565260
(81k:68039)
 [1]
 R. J. Fateman, "On the computation of powers of sparse polynomials," Stud. Appl. Math., v. 53, 1974, pp. 145155. 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. 196213. 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. 945949. 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. 115119. MR 523407 (80d:68051)
 [5]
 L. Heindel, "Computation of powers of multivariate polynomials over the integers," J. Comput. System Sci., v. 6, 1972, pp. 18. MR 0311148 (46:10241)
 [6]
 E. Horowitz & S. Sahni, "The computation of powers of symbolic polynomials," SIAM J. Comput., v. 4, 1975, pp. 201208. MR 0378469 (51:14637)
 [7]
 D. Knuth, The Art of Computer ProgrammingVol. II, Seminumerical Algorithms, AddisonWesley, Reading, Mass., 1968. MR 0378456 (51:14624)
 [8]
 D. P. McCarthy, "The optimal algorithm to evaluate using elementary multiplication methods," Math. Comp., v. 31, 1977, pp. 251256. MR 0428791 (55:1811)
 [9]
 S. Winograd, Arithmetic Complexity of Computations, CBMSNSF 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:
http://dx.doi.org/10.1090/S00255718198608296300
PII:
S 00255718(1986)08296300
Article copyright:
© Copyright 1986 American Mathematical Society
