Speeding Up Evaluation of Powers and Monomials.
Hatem M. Bahig, Hazem M. Bahig · FCS · 2006
An addition sequence problem is given a set of numbers X = {n1, n2, · · · , nm}, what is the minimal number of additions needed to compute all m numbers starting from 1? Downey et al. [9] showed that the addition sequence problem is NPcomplete. This problem has application in evaluating the monomials y1 , y2 , · · · , ym . In this paper, we present an algorithm to generate an addition sequence with minimal number of elements. We generalize some results on addition chain (m = 1) to addition sequence to speed up the computation. keywords: addition chain, addition sequence, vectorial addition chain, monomials evaluation, branch and bound algorithm.