Euclidian addition chains

When explicit multiplication (say of large matrices) is costly calculation-wise, it becomes natural to look for schemes that minimize the number of steps in the calculation of large powers $X^n$, in terms of $n$. This leads to the notion of addition chain for $n$, which is to say a sequence:

$\alpha:=(a_0,a_1,\ldots,  a_i,\ldots,a_k)$, with $a_0=1$, $a_k=n$,

and such that $a_m=a_i+a_j$ for some $0\leq i,j<m$. One says that $\ell(\alpha):=k$ is the length of the addition chain $\alpha$. This length is clearly the number of multiplication steps $X^{a_m}=X^{a_i}X^{a_j}$ in a corresponding calculation of $X^n$. This is discussed at length in The Art of Computer Programming, by D.E. Knuth (Volume 2, Seminumerical Algorithms, section 4.6.3).

Shortest length and Scholz-Brauer conjecture

One defines $\ell(n)$ to be the shortest length for an addition chain for $n$. In particular Knuth underlines that both finding the actual value of $\ell(n)$, and computing an explicit shortest length for $n$, are hard problems. The Scholz-Brauer conjecture is one of the several interesting unsolved problems along these lines. It states that, for all $n$, one has the inequality:

$\large \ell(2^n-1)\leq \ell(n)+n-1.$

Euclidean addition chain definition

Together with J. Berstel, S. Brlek, and C. Dubuc, we introduced in 1989 the notion of Euclidean addition chains. The family of such chains is recursively defined, using euclidean division. To express this, one considers the following two operations. First addition $\alpha\oplus m$,  for an integer $m$ appearing in the chain $\alpha$, is defined as:

$(a_0,a_1,\ldots ,a_k)\oplus m:=(a_0,a_1,\ldots,a_k,a_k+m).$

Then the product, $\alpha\otimes\beta$ of two chains, is set to be:

$(a_0,a_1,\ldots ,a_k)\otimes (b_0,b_1,\ldots ,b_j):=(a_0,a_1,\ldots ,a_k,a_kb_1,\ldots ,a_kb_j).$

The class of euclidean addition chains $\mathcal{E}$ is recursively constructed as follows. Let $n=qm+r$ be an euclidean division, $\gamma\in \mathcal{E}$ be any euclidean addition chain for $q$, and $\mu\in \mathcal{E}$ be an euclidean addition chain for $m$ that contains $r$. Then one constructs $\nu\in \mathcal{E}$ as:

$\nu:=(\mu\otimes \gamma)\oplus r.$

Observe that $r$ appears in $\mu\otimes \gamma$, since it appears in $\mu$, hence addition of $r$ to $\mu\otimes \gamma$ is legitimate. Moreover, since $m$ appears in $\nu$, we get a procedure to construct a chain for $n$ that contains $m$ when we have an euclidean division $n=qm+r$.

Euclidean Scholz-Brauer theorem

Let $\ell_\mathcal{E}(n)$ stand for the length of the shortest euclidean addition chain for $n$. We have shown that the following $\mathcal{E}$-analog of the Scholz-Brauer conjecture holds:

$\large\ell_\mathcal{E}(2^n-1)\leq \ell_\mathcal{E}(n)+n-1.$

There are fast explicit heuristics to construct almost optimal euclidean addition chains.

References