On the Evaluation of Powers

Andrew Chi-Chih Yao

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.
BibTeX
@article{yao1976evaluation,
  author = {Andrew Chi-Chih Yao},
  title = {{On the Evaluation of Powers}},
  journal = {SIAM Journal on Computing},
  year = {1976},
  url = {https://openreview.net/forum?id=MujZ6h6Esn6},
}

Loading related content...

Figure