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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.