On the Evaluation of Powers and Related Problems

Document Type

Conference Proceeding


Mathematics (HMC)

Publication Date



Let M be a p-by-q matrix of non-negative integers. We shall consider the problem of obtaining the p rows of M by computations in which

1. the zero vector (0,...,0) and the q unit vectors (1,...,0),...,(0,...,1) are available at no cost;

2. the sum of two (not necessarily distinct) previously computed vectors is available at a cost of one "step".

Such a computation is called an addition chain for M. Let l(M) denote the minimum possible number of steps in an addition chain for M. Let L(p, q, N) denote the maximum of l(M) over all p-by-q matrices M whose entries are drawn from {0, 1,...,N}.

Rights Information

© 1976 IEEE