7
$\begingroup$

An addition chain for $n$ is a finite sequence of integers starting at 1 and ending at $n$, such that each element is a sum of two previous elements. A short addition chain for $n$ can be used, for example, to calculate $x^n$ quickly by multiplying previously-calculated values.

Let $l(n)$ be the length of the shortest addition chain for $n$. I am looking for an upper bound on $l(n)$ of the form:

$$l(n) \leq C \cdot \log_2(n)$$

where $C$ is a constant.

The Wikipedia page cites the following bound from 1975: $$l(n) \leq \log_2(n) + \log_2(n)(1+o(1))/\log_2(\log_2(n)) < 2\log_2(n)$$

The OEIS page states several bounds, but without a clear reference: $$l(n) \leq (5/2) \log(n) = 1.73 \log_2(n)$$ $$l(n) \leq (4/3) \lfloor\log_2(n)\rfloor + 2$$

What is a reference for the best known upper bound of the form $l(n) \leq C \cdot \log_2(n)$ (the smallest value of $C$)?

$\endgroup$
4
+50
$\begingroup$

Alfred Brauer, On addition chains, Bull. Amer. Math. Soc. 45 (1939), 736-739 http://www.ams.org/journals/bull/1939-45-10/S0002-9904-1939-07068-7/

gives inequalities of the type you mention: equation (11), ($\log n$ being the log with base e).

If $2^m < n<2^{m+1}$, then $$l(n) \leq \min_{1\leq r \leq m} \Bigl( (1+\frac{1}{r})\frac{\log n}{\log 2}+2^r-2 \Bigr) .$$ Choosing a good (but maybe not yet optimal value of $r=[\log \log n]+1$) he obtains for $n\geq 3$: $l(n)< \frac{\log n}{\log 2}\Bigl(1+\frac{1}{\log \log n}+\frac{2\log 2}{(\log n)^{1-\log 2}}\Bigr)$.

So, you get $l(n)< (1+\varepsilon)\frac{\log n}{\log 2}$, for any $\varepsilon>0$, valid if $n > n_{\varepsilon}$. This threshold $n_{\varepsilon}$ can be worked out from $\frac{1}{\log \log n}+\frac{2\log 2}{(\log n)^{1-\log 2}}\leq \varepsilon $.

If $n$ is large, then the expression $\frac{1}{\log \log n}$ will be the dominating one on the left hand side, and so $n_{\varepsilon}$ is about $\exp(\exp(1/\varepsilon))$.

As Brauer's result is stronger than the form $l(n)\leq C \log n$ you ask about there will not be much literature on this. In any case, $C$ may tend to $1$, but is close to $1$ only for quite large values of $n$.

Update: For a numerical value of $C$ proceed as follows: 1) The OEIS page links to the first 100.000 values of the sequence: http://oeis.org/A003313/b003313.txt Calculating for these values the corresponding value of $C$ shows that for n=71 the value $9/\log_2 n=1.46347$ is the maximal value. (Based on this data I would conjecture that this is for all $n$ the maximal value, I am not sure if there is more data available, maybe you have a fast algorithm to check it.)

In order to prove an upper bound: Brauer's calculation (see equation 11 in the reference given) does not choose the best value of $r$. Choosing $r=[ \frac{\log \log n}{\log 2} -2\frac{\log \log \log n}{\log 2}+c ]$ somewhat improves the estimate. (Here $c$ is a constant to be optimized below).

The expression $$\Bigl( (1+\frac{1}{r})\frac{\log n}{\log 2}+2^r-2 \Bigr) $$ then gives (ignoring the floor functon in the definition of $r$) $$1 - \frac{\log 4}{\log n} + \frac{2^c \log 2}{(\log \log n)^2} + \frac{\log 2}{ c \log 2 + \log \log n - 2 \log \log \log n}.$$ Then evaluating the function for various values $c$ and for a large value where one has numerical data, here with $n=100.000$, gives with $c=1.3$ a value of $C=1.61043$.

With the value of $r$ rounded to an integer, the expression is (in Mathematica Code) 1/Floor[(c Log[2] + Log[Log[n]] - 2 Log[Log[Log[n]]])/Log[2]] + ( 2^Floor[(c Log[2] + Log[Log[n]] - 2 Log[Log[Log[n]]])/Log[2]] Log[ 2] + Log[n/4])/Log[n]

With $c=2$ this gives a value of $C=1.620412$. In other words, if $n> 10^5$, the function $l(n)\leq 1.620412 \frac{\log n}{\log 2}$ by Brauer's bound, assuming one accepts (or formally proves) that for fixed $c$ and increasing $n$ the function above is decreasing. For smaller values one has the numerical data.

(Asymptotically, this value of $c$ is not the best possible value. If you have numerical data up to some other bound, you can optimize this $c$ again).

$\endgroup$
  • $\begingroup$ So, $C$ can be made arbitrarily close to 1 for sufficiently large values of $n$? $\endgroup$ – Erel Segal-Halevi Sep 18 '15 at 8:47
  • $\begingroup$ Should't the inequality be: $\frac{1}{\log \log n}+\frac{2\log 2}{(\log n)^{1-\log 2}}\leq \varepsilon$? $\endgroup$ – Erel Segal-Halevi Sep 18 '15 at 9:51
  • $\begingroup$ (e.g, for $n=29$, the smallest length is 7 which is slightly above the bound). $\endgroup$ – Erel Segal-Halevi Sep 18 '15 at 10:20
  • $\begingroup$ Yes, some minor correction just added. $C$ is close to 1, for quite large values of $n$. $\endgroup$ – Christian Elsholtz Sep 18 '15 at 13:43
  • $\begingroup$ This leaves open the question: what is the smallest value of $C$ such that $l(n)\leq C\cdot \log_2(n)$ for every $n$ (or at least for $n\geq 3$)? $\endgroup$ – Erel Segal-Halevi Sep 19 '15 at 17:19
3
$\begingroup$

There is a new OEIS sequence A264803 in which Neill Clift's table of l(n), provided at A. Flammenkamp's web page, is used to determine the maximum values of l(n)/log2(n) in intervals 2^m < n < 2^(m+1) for m<=30

$\endgroup$
2
$\begingroup$

In this paper:

Wattel, E. & Jensen, G. "Efficient calculation of powers in a semigroup" Stichting Mathematisch Centrum. Zuivere Wiskunde, 1968, 1-18

they prove that $l(n)/log_2(n)\le1.463$ and takes on this value for $n=71$. This paper is interesting since it's an earlier usage of the Thurber sliding window method than the Thurber paper. The only reason I know about this paper is that it was referenced by a student doing a term paper and he was given the paper by one of the authors. I don't understand the interest in a bound like this mind you.

$\endgroup$
1
$\begingroup$

Subbarao, M. "Addition chains-some results and problems." Number theory and applications (1989): 555-574.

A slightly outdated reference, but seems like the best available for the problem.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.