Efficient computation of addition chains
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.
- Minimizing sums of addition chains
- Efficient Generation of Minimal Length Addition Chains
- Efficient generation of shortest addition-multiplication chains
- Effect of Improved Multiplication Efficiency on Exponentiation Algorithms Derived from Addition Chains
- A new strategy for generating shortest addition sequences
- Star reduction among minimal length addition chains
- Improved generation of minimal addition chains
- Addition chains, vector chains, and efficient computation
- scientific article; zbMATH DE number 1946632
- Rule based representation of integer for a new addition chain method
- A lower bound for the length of addition chains
- Addition chains and solutions of \(\ell(2n)=\ell(n)\) and \(\ell(2^n-1)= n+\ell(n)-1\)
- Addition chains using continued fractions
- Computing Sequences with Addition Chains
- Efficient computation of addition chains
- scientific article; zbMATH DE number 3808949 (Why is no real title available?)
- scientific article; zbMATH DE number 3750146 (Why is no real title available?)
- On addition chains l(mn) 1 (n)-b and lower bounds for c(r)
- On the Evaluation of Powers
- The Computing Time of the Euclidean Algorithm
- The Scholz-Brauer problem in addition chains
- The Scholz-Brauer problem on addition chains
- Efficient computation of addition chains
- Accelerated shift-and-add algorithms
- Addition chains, vector chains, and efficient computation
- On a generalization of addition chains: addition-multiplication chains
- Binary addition chain on EREW PRAM
- scientific article; zbMATH DE number 7235119 (Why is no real title available?)
- Computing When Multiplications Cost Nothing
- Effect of Improved Multiplication Efficiency on Exponentiation Algorithms Derived from Addition Chains
- Efficient Generation of Minimal Length Addition Chains
- Addition chains using continued fractions
- Computing special powers in finite fields
- On-line evaluation of powers using Euclid's algorithm
- Hensel-lifting torsion points on Jacobians and Galois representations
- Addition chains meet postage stamps: reducing the number of multiplications
- A new strategy for generating shortest addition sequences
- Calculating optimal addition chains
- Mechanically proving termination using polynomial interpretations
- Improved generation of minimal addition chains
This page was built for publication: Efficient computation of addition chains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1340674)
