# zbMATH — the first resource for mathematics

Efficient computation of addition chains. (English) Zbl 0812.11072
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 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.

##### MSC:
 11Y16 Number-theoretic algorithms; complexity 11Y65 Continued fraction calculations (number-theoretic aspects) 68Q25 Analysis of algorithms and problem complexity
Full Text: