6
$\begingroup$

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.

$\endgroup$

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.