Addition Chain Methods for the Evaluation of Specific Polynomials
Authors:
- David DobkinDDDavid Dobkin
- Richard J. LiptonRLRichard J. Lipton
- 1 February 1980
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 9 (1) , 121-125
Abstract
Addition chains are considered for specific polynomials. It is shown that for a wide class of polynomials the evaluation of their first n terms requires at least $n + O(n^{2/3} )$ additions. Included in this class are the first n squares, the first n cubes, $ \cdots $, the first nkth powers. The results are established by making contact with results in combinatorics.
Keywords
This publication has 6 references indexed in Scilit:
- Proficiency Testing in Determinations of Antiepileptic DrugsJournal of Analytical Toxicology, 1977
- On the evaluation of powers and related problems1976
- On the Evaluation of PowersSIAM Journal on Computing, 1976
- Complexity measures and hierarchies for the evaluation of integers, polynomials, and n-linear forms1975
- A Remark on Mordell's ConjectureAmerican Journal of Mathematics, 1965
- Remarks on number theory III. On addition chainsActa Arithmetica, 1960