On the Evaluation of Powers
Lists
Only you see this
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...