Document Type
Article
Department
Mathematics (HMC)
Publication Date
1980
Abstract
Let $y_1 , \cdots ,y_p $ be monomials over the indeterminates $x_1 , \cdots ,x_q $. For every $y = (y_1 , \cdots ,y_p )$ there is some minimum number $L(y)$ of multiplications sufficient to compute $y_1 , \cdots ,y_p $ from $x_1 , \cdots ,x_q $ and the identity 1. Let $L(p,q,N)$ denote the maximum of $L(y)$ over all $y$ for which the exponent of any indeterminate in any monomial is at most $N$. We show that if $p = (N + 1^{o(q)} )$ and $q = (N + 1^{o(p)} )$, then $L(p,q,N) = \min \{ p,q\} \log N + H/\log H + o(H /\log H)$, where $H = pq\log (N + 1)$ and all logarithms have base 2.
Rights Information
© 1980 Society for Industrial and Applied Mathematics
Recommended Citation
Pippenger, Nicholas. “On the Evaluation of Powers and Monomials.” SIAM Journal on Computing 9, no. 2 (May 1980): 230-250.
