Efficient computation of addition chains (Q1340674)

An addition chain for a positive integer \(n\) is a finite sequence of positive integers beginning with 1 and ending with \(n\), such that each term except the first is the sum of two of its predecessors. Addition chains for \(n\) generate multiplication schemes for the computation of \(x^ n\); the smallest number of multiplications required is the minimal length \(\ell(n)\) of an addition chain for \(n\). The paper studies \(cf\)-chains as introduced by the authors and \textit{C. Duboc} [J. Algorithms 10, 403-412 (1989; Zbl 0682.68025)]. These are a class of sub-optimal addition chains, obtained through continued fraction expansions for \(n/k\), where \(1<k<n\). The length of \(cf\)-chains is asymptotically equivalent to \(\log_ 2(n)\), as in \(\ell(n)\). Most of the popular effective strategies for computing addition chains are obtained as special cases of the \(cf\)-chain method. The total number of operations required for the generation of an addition chain for all positive integers up to \(n\) is \(O(n \log^ 2 n\gamma_ n)\), where \(\gamma_ n\) is the complexity of computing the set of choices corresponding to the strategy.