The optimal algorithm to evaluate $x^{n}$ using elementary multiplication methods
HTML articles powered by AMS MathViewer
- by D. P. McCarthy PDF
- Math. Comp. 31 (1977), 251-256 Request permission
Abstract:
The optimality of the binary algorithm to evaluate ${x^n}$ is established where x is an integer or a completely dense polynomial modulo m, n is a positive integer, and the multiplications are done using a simple improvement on the naive algorithm.References
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- 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
Additional Information
- © Copyright 1977 American Mathematical Society
- Journal: Math. Comp. 31 (1977), 251-256
- MSC: Primary 68A20
- DOI: https://doi.org/10.1090/S0025-5718-1977-0428791-X
- MathSciNet review: 0428791