# Evaluating addition chains

I hope this is a suitable place to ask this question.

An addition chain of size $$n$$ is a sequence $$x_1, \dots, x_n$$, where $$x_1$$ is fixed to 1 and $$x_i = x_j + x_k$$ for some $$j,k < i$$. I am interested in efficient algorithms to evaluate $$x_n$$ over $$\mathbb N$$.

### Upper bounds

The obvious algorithm is to evaluate every $$x_i$$ as a binary number and store the results. This uses $$\mathcal O(\sum \log x_i)$$ time and space. Clearly, if $$x_1 = 1$$ then $$x_i < 2^i$$ so the time and space can be bounded by $$\mathcal O(\sum i) = \mathcal O(n^2)$$. There exist chains with $$x_i = \Theta(2^i)$$ e.g. $$x_{i+1} = x_i + x_i$$, so this bound is also tight.

There is an improvement that uses $$\mathcal O(n)$$ space: the idea is to calculate one bit of the result at a time, while using $$\mathcal O(1)$$ bits for each term to store the carry to the next bit. However, the running time is still quadratic.

### Lower bounds

We can implement multiplication of $$\frac n 4$$-bit numbers using an addition chain of size $$n$$. This gives a non-trivial lower bound of $$M(\frac n 4)$$ which is $$\Omega(n \log n)$$ (based on the best known multiplication algorithms).

A better bound via matrix multiplication: use a size-$$\frac n 3$$ chain to encode rows of a square matrix over $$GF(2)$$ with side length $$\mathcal O(n^{1/2}/\log n)$$, where the $$\log n$$ is spent on padding each entry with some zeroes to avoid overflow. We add another size-$$\frac n 3$$ chain to express linear combinations of these rows, and a final $$\frac n 3$$ chain to construct a single integer $$x_n$$ that contains all bits of the result. This implies a lower bound of $$n^{\omega/2 - \epsilon}$$ where $$\omega$$ is the difficulty of matrix multiplication (currently about $$2.37$$).

I am wondering if there is a better lower or upper bound for evaluating $$x_n$$.

This problem comes up in data structures that compress a very large tree into a DAG. Calculating the size of the underlying tree is equivalent to evaluating an addition chain over the graph.