Addition chain

Last updated December 26, 2023

In mathematics, an addition chain for computing a positive integer $n$ can be given by a sequence of natural numbers starting with 1 and ending with $n$ , such that each number in the sequence is the sum of two previous numbers. The length of an addition chain is the number of sums needed to express all its numbers, which is one less than the cardinality of the sequence of numbers.^[1]

Examples

As an example: (1,2,3,6,12,24,30,31) is an addition chain for 31 of length 7, since

2 = 1 + 1

3 = 2 + 1

6 = 3 + 3

12 = 6 + 6

24 = 12 + 12

30 = 24 + 6

31 = 30 + 1

Addition chains can be used for addition-chain exponentiation. This method allows exponentiation with integer exponents to be performed using a number of multiplications equal to the length of an addition chain for the exponent. For instance, the addition chain for 31 leads to a method for computing the 31st power of any number $n$ using only seven multiplications, instead of the 30 multiplications that one would get from repeated multiplication, and eight multiplications with exponentiation by squaring:

n

² =

n

×

n

n

³ =

n

² ×

n

n

⁶ =

n

³ ×

n

³

n

¹² =

n

⁶ ×

n

⁶

n

²⁴ =

n

¹² ×

n

¹²

n

³⁰ =

n

²⁴ ×

n

⁶

n

³¹ =

n

³⁰ ×

n

Methods for computing addition chains

Calculating an addition chain of minimal length is not easy; a generalized version of the problem, in which one must find a chain that simultaneously forms each of a sequence of values, is NP-complete.^[2] There is no known algorithm which can calculate a minimal addition chain for a given number with any guarantees of reasonable timing or small memory usage. However, several techniques are known to calculate relatively short chains that are not always optimal.^[3]

One very well known technique to calculate relatively short addition chains is the binary method, similar to exponentiation by squaring. In this method, an addition chain for the number $n$ is obtained recursively, from an addition chain for $n'=\lfloor n/2\rfloor$ . If $n$ is even, it can be obtained in a single additional sum, as $n=n'+n'$ . If $n$ is odd, this method uses two sums to obtain it, by computing $n-1=n'+n'$ and then adding one.^[3]

The factor method for finding addition chains is based on the prime factorization of the number $n$ to be represented. If $n$ has a number $p$ as one of its prime factors, then an addition chain for $n$ can be obtained by starting with a chain for $n/p$ , and then concatenating onto it a chain for $p$ , modified by multiplying each of its numbers by $n/p$ . The ideas of the factor method and binary method can be combined into Brauer's m-ary method by choosing any number $m$ (regardless of whether it divides $n$ ), recursively constructing a chain for $\lfloor n/m\rfloor$ , concatenating a chain for $m$ (modified in the same way as above) to obtain $m\lfloor n/m\rfloor$ , and then adding the remainder. Additional refinements of these ideas lead to a family of methods called sliding window methods.^[3]

Chain length

Let $l(n)$ denote the smallest $s$ so that there exists an addition chain of length $s$ which computes $n$ . It is known that

\log _{2}(n)+\log _{2}(\nu (n))-2.13\leq l(n)\leq \log _{2}(n)+\log _{2}(n)(1+o(1))/\log _{2}(\log _{2}(n))

,

where $\nu (n)$ is the Hamming weight (the number of ones) of the binary expansion of $n$ .^[4]

One can obtain an addition chain for $2n$ from an addition chain for $n$ by including one additional sum $2n=n+n$ , from which follows the inequality $l(2n)\leq l(n)+1$ on the lengths of the chains for $n$ and $2n$ . However, this is not always an equality, as in some cases $2n$ may have a shorter chain than the one obtained in this way. For instance, $l(382)=l(191)=11$ , observed by Knuth.^[5] It is even possible for $2n$ to have a shorter chain than $n$ , so that $l(2n)<l(n)$ ; the smallest $n$ for which this happens is $n=375494703$ ,^[6] which is followed by $602641031$ , $619418303$ , and so on (sequence A230528 in the OEIS ).

Brauer chain

A Brauer chain or star addition chain is an addition chain in which each of the sums used to calculate its numbers uses the immediately previous number. A Brauer number is a number for which a Brauer chain is optimal.^[5]

Brauer proved that

l * (2 n -1) \leq n - 1 + l * (n)

where $l^{*}$ is the length of the shortest star chain. For many values of n, and in particular for $n < 12509$ , they are equal:^[7] $l (n) = l * (n)$ . But Hansen showed that there are some values of n for which $l (n) \neq l * (n)$ , such as $n = 26106 + 23048 + 22032 + 22016 + 1$ which has $l * (n) = 6110, l (n) \leq 6109$ . The smallest such n is 12509.

Scholz conjecture

The Scholz conjecture (sometimes called the Scholz–Brauer or Brauer–Scholz conjecture), named after Arnold Scholz and Alfred T. Brauer), is a conjecture from 1937 stating that

l(2^{n}-1)\leq n-1+l(n).

This inequality is known to hold for all Hansen numbers, a generalization of Brauer numbers; Neill Clift checked by computer that all $n\leq 5784688$ are Hansen (while 5784689 is not).^[6] Clift further verified that in fact $l(2^{n}-1)=n-1+l(n)$ for all $n\leq 64$ .^[5]

Related Research Articles

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add.

In number theory, Waring's problem asks whether each natural number k has an associated positive integer s such that every natural number is the sum of at most s natural numbers raised to the power k. For example, every natural number is the sum of at most 4 squares, 9 cubes, or 19 fourth powers. Waring's problem was proposed in 1770 by Edward Waring, after whom it is named. Its affirmative answer, known as the Hilbert–Waring theorem, was provided by Hilbert in 1909. Waring's problem has its own Mathematics Subject Classification, 11P05, "Waring's problem and variants".

Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future. Another concern is that noise in quantum circuits may undermine results, requiring additional qubits for quantum error correction.

In mathematics and computer science, the floor function is the function that takes as input a real number $x$ , and gives as output the greatest integer less than or equal to $x$ , denoted $⌊ x ⌋$ or $floor(x)$ . Similarly, the ceiling function maps $x$ to the smallest integer greater than or equal to $x$ , denoted $⌈ x ⌉$ or $ceil(x)$ .

<span class="mw-page-title-main">Exponentiation</span> Mathematical operation

In mathematics, exponentiation is an operation involving two numbers, the base and the exponent or power. Exponentiation is written as $b n$ , where $b$ is the base and $n$ is the power; this is pronounced as " $b$ (raised) to the $n$ ". When $n$ is a positive integer, exponentiation corresponds to repeated multiplication of the base: that is, $b n$ is the product of multiplying $n$ bases:

Toom–Cook, sometimes known as Toom-3, named after Andrei Toom, who introduced the new algorithm with its low complexity, and Stephen Cook, who cleaned the description of it, is a multiplication algorithm for large integers.

<span class="mw-page-title-main">Mertens function</span> Summatory function of the Möbius function

In number theory, the Mertens function is defined for all positive integers n as

In mathematics, the Scholz conjecture is a conjecture on the length of certain addition chains. It is sometimes also called the Scholz–Brauer conjecture or the Brauer–Scholz conjecture, after Arnold Scholz who formulated it in 1937 and Alfred Brauer who studied it soon afterward and proved a weaker bound.

Pollard's p − 1 algorithm is a number theoretic integer factorization algorithm, invented by John Pollard in 1974. It is a special-purpose algorithm, meaning that it is only suitable for integers with specific types of factors; it is the simplest example of an algebraic-group factorisation algorithm.

Sperner's theorem, in discrete mathematics, describes the largest possible families of finite sets none of which contain any other sets in the family. It is one of the central results in extremal set theory. It is named after Emanuel Sperner, who published it in 1928.

In mathematics and computer science, optimal addition-chain exponentiation is a method of exponentiation by a positive integer power that requires a minimal number of multiplications. Using the form of the shortest addition chain, with multiplication instead of addition, computes the desired exponent of the base. Each exponentiation in the chain can be evaluated by multiplying two of the earlier exponentiation results. More generally, addition-chain exponentiation may also refer to exponentiation by non-minimal addition chains constructed by a variety of algorithms.

In modular arithmetic computation, Montgomery modular multiplication, more commonly referred to as Montgomery multiplication, is a method for performing fast modular multiplication. It was introduced in 1985 by the American mathematician Peter L. Montgomery.

The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers, published by Arnold Schönhage and Volker Strassen in 1971. It works by recursively applying fast Fourier transform (FFT) over the integers modulo 2ⁿ+1. The run-time bit complexity to multiply two $n$ -digit numbers using the algorithm is $in big O notation .$

<span class="mw-page-title-main">Divisor summatory function</span>

In number theory, the divisor summatory function is a function that is a sum over the divisor function. It frequently occurs in the study of the asymptotic behaviour of the Riemann zeta function. The various studies of the behaviour of the divisor function are sometimes called divisor problems.

In mathematics, a Beatty sequence is the sequence of integers found by taking the floor of the positive multiples of a positive irrational number. Beatty sequences are named after Samuel Beatty, who wrote about them in 1926.

In mathematics, Abel's summation formula, introduced by Niels Henrik Abel, is intensively used in analytic number theory and the study of special functions to compute series.

In computer science, $sorting is the problem of sorting pairs of numbers by their sums. Applications of the problem include transit fare minimisation, VLSI design, and sparse polynomial multiplication. As with comparison sorting and integer sorting more generally, algorithms for this problem can be based only on comparisons of these sums, or on other operations that work only when the inputs are small integers.$

In mathematics, the set of positive real numbers, $is the subset of those real numbers that are greater than zero. The non-negative real numbers, also include zero. Although the symbols and are ambiguously used for either of these, the notation or for and or for has also been widely employed, is aligned with the practice in algebra of denoting the exclusion of the zero element with a star, and should be understandable to most practicing mathematicians.$

The Meissel–Lehmer algorithm is an algorithm that computes exact values of the prime-counting function.

References

↑ D. E. Knuth, The Art of Computer Programming , Vol 2, "Seminumerical Algorithms", Section 4.6.3, 3rd edition, 1997
↑ Downey, Peter; Leong, Benton; Sethi, Ravi (1981), "Computing sequences with addition chains", SIAM Journal on Computing , 10 (3): 638–646, doi:10.1137/0210047 . A number of other papers state that finding a shortest addition chain for a single number is NP-complete, citing this paper, but it does not claim or prove such a result.
1 2 3 Otto, Martin (2001), Brauer addition-subtraction chains (PDF), Diplomarbeit, University of Paderborn, archived from the original (PDF) on 2013-10-19, retrieved 2013-10-19.
↑ Schönhage, Arnold (1975), "A Lower Bound for the Length of Addition Chains", Theoretical Computer Science , 1 (1): 1–12, doi:10.1016/0304-3975(75)90008-0
1 2 3 Guy (2004) p.169
1 2 Clift, Neill Michael (2011). "Calculating optimal addition chains" (PDF). Computing. 91 (3): 265–284. doi: 10.1007/s00607-010-0118-8 .
↑ Achim Flammenkamp, Shortest Addition Chains

Brauer, Alfred (1939). "On addition chains". Bulletin of the American Mathematical Society . 45 (10): 736–739. doi: 10.1090/S0002-9904-1939-07068-7 . ISSN 0002-9904. MR 0000245.
Richard K. Guy (2004). Unsolved Problems in Number Theory. Springer-Verlag. ISBN 978-0-387-20860-2. OCLC 54611248. Zbl 1058.11001. Section C6.

External links

http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html
OEIS sequenceA003313(Length of shortest addition chain for n). Note that the initial "1" is not counted (so element #1 in the sequence is 0).
F. Bergeron, J. Berstel. S. Brlek "Efficient computation of addition chains"

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] D. E. Knuth, The Art of Computer Programming , Vol 2, "Seminumerical Algorithms", Section 4.6.3, 3rd edition, 1997

[2] Downey, Peter; Leong, Benton; Sethi, Ravi (1981), "Computing sequences with addition chains", SIAM Journal on Computing , 10 (3): 638–646, doi:10.1137/0210047 . A number of other papers state that finding a shortest addition chain for a single number is NP-complete, citing this paper, but it does not claim or prove such a result.

[otto-3] 1 2 3 Otto, Martin (2001), Brauer addition-subtraction chains (PDF), Diplomarbeit, University of Paderborn, archived from the original (PDF) on 2013-10-19, retrieved 2013-10-19.

[4] Schönhage, Arnold (1975), "A Lower Bound for the Length of Addition Chains", Theoretical Computer Science , 1 (1): 1–12, doi:10.1016/0304-3975(75)90008-0

[G169-5] 1 2 3 Guy (2004) p.169

[Clift-6] 1 2 Clift, Neill Michael (2011). "Calculating optimal addition chains" (PDF). Computing. 91 (3): 265–284. doi: 10.1007/s00607-010-0118-8 .

[7] Achim Flammenkamp, Shortest Addition Chains

[1]

[2]

[3]

[4]

[5]

[6]

[7]