Efficient computation of addition chains (Q1340674): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
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 | |||
Property / author | |||
Property / author: François Bergeron / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Jean Berstel / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Srečko Brlek / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: A. Bijlsma / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1994702909 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Efficient computation of addition chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Addition chains using continued fractions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Computing Time of the Euclidean Algorithm / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computing Sequences with Addition Chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Scholz-Brauer problem in addition chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3935355 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A lower bound for the length of addition chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3657431 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Addition chains and solutions of \(\ell(2n)=\ell(n)\) and \(\ell(2^n-1)= n+\ell(n)-1\) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Scholz-Brauer problem on addition chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On addition chains \(l(mn)\leq 1 (n)-b\) and lower bounds for c(r) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Evaluation of Powers / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 10:57, 23 May 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