On the evaluation of powers and related problems

1 October 1976

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 258-263
https://doi.org/10.1109/sfcs.1976.21

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 \u22step\u22. 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}

Keywords

This publication has 3 references indexed in Scilit:

On the Evaluation of Powers
SIAM Journal on Computing, 1976
Remarks on number theory III. On addition chains
Acta Arithmetica, 1960
On addition chains
Bulletin of the American Mathematical Society, 1939