On the Evaluation of Powers and Related Problems

Document Type

Conference Proceeding

Department

Mathematics (HMC)

Publication Date

10-1976

Abstract

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

Link to Full Text

Share

COinS