Efficient computation of addition chains (Q1340674): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: François Bergeron / rank | |||
Property / author | |||
Property / author: Jean Berstel / rank | |||
Property / author | |||
Property / author: Srečko Brlek / rank | |||
Property / reviewed by | |||
Property / reviewed by: A. Bijlsma / rank | |||
Revision as of 00:54, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficient computation of addition chains |
scientific article |
Statements
Efficient computation of addition chains (English)
0 references
15 May 1995
0 references
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.
0 references
addition chain
0 references
multiplication schemes
0 references
minimal length
0 references
\(cf\)-chains
0 references
sub- optimal addition chains
0 references
contained fraction expansions
0 references
complexity
0 references