Effect of improved multiplication efficiency on exponentiation algorithms derived from addition chains. (English) Zbl 0608.68027

McCarthy, D. P.

Math. Comput. 46, 603-608 (1986).

To compute the n-th power of x one considers ”additon chains” \(A_ n=(a_ 1,...,a_ k)\) where \(a_ 1=1\), \(a_ k=n\) and for al \(i>1\) there exist \(j,m<i\) s.t. \(a_ i=a_ j+a_ m\). The power \(x^ n\) arises as the last result in a sequence of multiplications of the form \(x^{a_ i}=x^{a_ j}\cdot x^{a_ m}.\)
In the paper, four different multiplication chains are considered, among them repeated multiplication by x having the addition chain \(R_ n=(1,2,3,...,n)\) and the binary algorithm with the addition chain \(B_ n=(1,...,a_ i,...,n)\) where \(a_ i=a_{i-1}+1\) if \(a_ i\) is odd and \(a_ i=a_{i-1}+a_{i-1}\) if \(a_ i\) is even.
Under the complexity measure \[ CA_ n=\sum^{k}_{i=2}(a_{j(i)}\cdot a_{m(i)})^{\alpha} \] it turns out that for \(\alpha <1\) the binary algorithm sould be used, and for \(\alpha >1\) repeated multiplication should be used. For \(\alpha =1\), the binary algorithm is about twice as fast as repeated multiplication, but the latter yields all the intermediate powers of x.

Reviewer: G.Wechsung

MSC:

68Q25	Analysis of algorithms and problem complexity
68W30	Symbolic computation and algebraic computation

Keywords:

additon chains; multiplication chains; repeated multiplication; binary algorithm