On the Evaluation of Powers
Author:
- Andrew Chi-Chih YaoAYAndrew Chi-Chih Yao
- 1 March 1976
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 5 (1) , 100-103
Abstract
It is shown that for any set of positive integers $\{ n_1 ,n_2 , \cdots ,n_p \} $, there exists a procedure which computes $\{ x^{n_1 } ,x^{n_2 } , \cdots ,x^{n_p } \} $ for any input x in less than $\lg N + c\sum_{i = 1}^P [\lg n_i /\lg \lg (n_i + 2)]$ multiplications for some constant c, where $N = \max _i \{ n_i \} $. This gives a partial solution to an open problem in Knuth [3, § 4.6.3, Ex. 32] and generalizes Brauer’s theorem on addition chains.
Keywords
This publication has 2 references indexed in Scilit:
- Remarks on number theory III. On addition chainsActa Arithmetica, 1960
- On addition chainsBulletin of the American Mathematical Society, 1939