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

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
Full Text:

### Online Encyclopedia of Integer Sequences:

Length of shortest addition chain for n.