An Introduction & Supplement to Knuth's Introduction to Addition Chains
(See Addition Chains as Polymorphic Higherorder Functions for a different way of working with addition chains that works for very large numbers.)
Let's learn a bit about addition chains. Addition chains are representations of positive numbers, constructed from only the value 1 and the addition operation as building blocks. The best introduction to addition chains is Section 4.6.3 of The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd Edition) by Donald Knuth. The presentation here is intended to supplement what Knuth wrote. The nondescript names of the functions r
, d
, f
, λ
, and v
are consistent with other descriptions of addition chains, Knuth's in particular.
I wrote some Haskell code to help with our exploration. I didn't use any language extensions beyond GHCi 8.0.1's defaults, and I didn't use any library code outside the base package. I lack a proper background in algebra so I avoided abstractions like Semigroup
, Functor
, and Monad
. I didn't even use folds and maps. The result is the module AdditionChainConstruction
in the file AdditionChainConstruction.lhs. I use binary literal notation in the discussion (e.g. 0b101 == 5
), but not in the code. You can enable this at the GHCi prompt with :set XBinaryLiterals
or with {# LANGUAGE BinaryLiterals #}
at the top of your source files, but it isn't required.
module AdditionChainConstruction(
Peano(..), peano_42,
DoubleAndAdd1(..), doubleAndAdd1_42, doubleAndAdd1_45,
AdditionChain(..), _45, add, double,
Denotable(denote),
ToBits(bits), bitString,
r, d, f, λ, lambda, v,
Components, Measurable,
) where
import Data.Bits
import Data.Char(intToDigit)
import Data.List(nub)
import Numeric(showIntAtBase)
import Numeric.Natural
The simplest representation of positive integers is the Peano encoding, which uses only the unit 1
and an n + 1
operation. (In other presentations of Peano numbers, the n + 1
operation is usually called succ
for successor. Here we call it PAdd1
for symmetry with what we do later. Also, the unit value for Peano numbers is often defined to be 0, but we use 1 here because 0 isn't a posiive integer.)
data Peano
= POne
 PAdd1 Peano
deriving (Show, Eq)
POne
represents 1, PAdd1 POne
represents 2, PAdd1 (PAdd1 POne)
represents 3, PAdd1 (PAdd1 (PAdd1 (PAdd1 POne)))
represents 5, etc. We can say this in code by creating a function that maps a Peano
to the natural number it represents. We'll call this function denote
since it is a sort of denotational semantics for our representations, and we'll make it generic so that we can implement it for every type of representation of positive integers we make:
class Denotable a where
denote :: a > Natural
We can now define the meaning of every Peano
value:
instance Denotable Peano where
denote POne = 1
denote (PAdd1 n_minus_1) = (denote n_minus_1) + 1
Let's construct the Peano representation of 42:
peano_42 :: Peano
peano_42 =
PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (
PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (
PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (
PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (PAdd1 (
PAdd1 POne))))))))))))))))))))))))))))))))))))))))
We can verify that peano_42
is the correct encoding of 42 by checking denote peano_42 == 42
.
It takes n  1
applications of PAdd1
to represent the number n
. For example, peano_42
has POne
nested inside 41 layers of PAdd1
. Representing even a tiny number like 42 is unwieldy with the Peano encoding. It is impractical for encoding large numbers. Let's define a new representation similar to Peano
, but with an additional doubling operation n + n
that augments the Peano n + 1
operation:
data DoubleAndAdd1
= DA1One
 DA1Double DoubleAndAdd1
 DA1DoubleAndAdd1 DoubleAndAdd1
deriving (Show, Eq)
instance Denotable DoubleAndAdd1 where
denote DA1One = 1
denote (DA1Double n) = denoteDouble n
denote (DA1DoubleAndAdd1 n) = (denoteDouble n) + 1
denoteDouble n = d + d where d = denote n
Let's represent 42 as a doubleandadd1 chain:
doubleAndAdd1_42 =
let
__1 = DA1One  given 1: 1
__2 = DA1Double __1  append 0: 10
__5 = DA1DoubleAndAdd1 __2  append 1: 101
_10 = DA1Double __5  append 0: 1010
_21 = DA1DoubleAndAdd1 _10  append 1: 10101
_42 = DA1Double _21  append 0: 101010
in
_42  42 == 0b101010
We can verify that doubleAndAdd1_42
is a representation of 42 by checking denote doubleAndAdd1_42 == 42
.
It is safe to assume doubling is not more expensive than adding one. (In many applications of addition chains, doubling is actually cheaper than other forms of addition.) Note that a DA1DoubleAndAdd1
represents two additions, combined only to prevent an addition of 1 without the doubling that must precede it. This doubleandaddone chain only requires 5 doublings + 2 other additions = 7 additions to represent 42, which is much more efficient than the Peano encoding, which required 41 additions.
class Measurable a where
 The number of doublings in a single component.
d' :: a > Count
 The number of nondoublings in a single component.
f' :: a > Count
 The number of additions of any sort in a single component.
r' :: Measurable a => a > Count
r' n = d' n + f' n
type Count = Int  Differentiate our metadata numbers.
instance Measurable Peano where
d' _ = 0  Peano doesn't have the concept of doubling.
f' POne = 0
f' (PAdd1 n_minus_1) = (f' n_minus_1) + 1
instance Measurable DoubleAndAdd1 where
d' DA1One = 0
d' (DA1Double _) = 1
d' (DA1DoubleAndAdd1 _) = 1
f' DA1One = 0
f' (DA1Double _) = 0
f' (DA1DoubleAndAdd1 _) = 1
It's useful to be able to see our representations of positive integers as bit strings so let's define some tools to facilitate that:
 A representation of a positive number in terms of 'Data.Bits'.
class ToBits a where
 Converts the representation to one that is easier to look at bitwise.
 Ideally the result type of 'bits' would be 'Bits b => b', but it is
 restricted to 'Natural' here for the reason mentioned below.)
bits :: a > Natural
 Construct a string of the binary representation of 'a'.
bitString :: ToBits a => a > String
bitString n = showBin (bits n) ""
where
showBin x s = showIntAtBase 2 intToDigit x s  Internet copypasta.
 Haskell doesn't provide a convenient way to see the bits of a 'Natural'.
 Make 'bitString' work for 'Natural' too, to rectify this. For example,
 bitString (42::Natural) == "101010".
instance ToBits Natural where
bits x = x
Every component in the doubleandaddone representation appends a single binary digit to the result; every DA1Double
appends a zero and every DA1DoubleAndAdd1
appends a one:
instance ToBits DoubleAndAdd1 where
bits d = bits' 0 d
where
bits' i DA1One = bit i  Set the most significant bit.
bits' i (DA1Double d) = (bits' (i + 1) d)
bits' i (DA1DoubleAndAdd1 d) = setBit (bits' (i + 1) d) i
Note that bits d
computes the same results as denote d
, i.e. bits d == denote d
for all d
. bits
does it with bitwise operations (directly setting bits) whereas DoubleAndAdd1
's denote
implementation does it arithmetically (using addition). When trying to find the most efficient addition chain to construct a number, it will often be useful to alternate between thinking in terms of bitwise operations and arithmetic operations.
A Peano representation of a number n has Θ(n) complexity, whereas the doubleandaddone representation has Θ(lg n) complexity. Why is the doubleandaddone representation so much more efficient? There are roughly λ(n) = ⌊lg n⌋ doublings in the doubleandaddone representation. That is, there will be one doubling for every bit in the number, except for the first bit. The ith doubling itself gets doubled λ(n)  i times, which means that such a doubling is equivalent to (roughly) 2^{λ(n)  i} Peano PAdd1
operations. Summing this series will result in a value that's very close to n
already, which means there is not much more work to do. In fact, no more than v(n)
additions are needed in addition to the doubles, where v(n)
is the number of set bits in n
, i.e. its binary Hamming weight.
 The length in bits of the given number; aliased as 'lambda'.
λ :: ToBits a => a > Count
λ n = floor (logBase 2 (fromIntegral (bits n)))  Internet copypasta.
 The length in bits of the given number; an easytotype alias for 'λ'.
lambda :: ToBits a => a > Count
lambda = λ
 The number of set bits in the given number; its binary Hamming weight.
v :: ToBits a => a > Count
v n = popCount (bits n)
Doubling is the most powerful possible operation. We always start with only the value 1 (DA1One
) given to us. The only way we can get to 2 from 1 is by adding 1 to itself, i.e. doubling it. Then we have 1 and 2 available. We can construct 3 by adding 1 + 2
and we can construct 4 by doubling 2. But there's no way to use a single addition, given just 1 and 2, that will result in a value larger than 4. Thus the introduction of doubling is the biggest efficiency improvement we can possibly make.
We can still make improvements, but they will be much smaller than the introduction of doubling. The two operations we've done so far are doubling and adding one. Doubling (n + n
) is the biggest step we can take, and adding one (n + 1
) is the smallest step we can take. Are there mediumsized steps? What if, instead of just adding n + n
or n + 1
, we could add any two previouslyconstructed values a + b
?
It turns out that for the number 42, the doubleandadd1 chain we developed is the best we can do. But it is not the best choice for every number. Let's consider 45:
doubleAndAdd1_45 =
let
__1 = DA1One  given 1: 1
__2 = DA1Double __1  append 0: 10
__5 = DA1DoubleAndAdd1 __2  append 1: 101
_11 = DA1DoubleAndAdd1 __5  append 1: 1011
_22 = DA1Double _11  append 0: 10110
_45 = DA1DoubleAndAdd1 _22  append 1: 101101
in
_45  45 == 0b101101
We can verify that this is really a representation of 45 by checking denote doubleAndAdd1_45 == 45
.
The doubleandadd1 chain for 45 requires 5 doublings and 3 additions of 1. Now let's try our generalized addition idea to see how we can construct 45 more efficiently:
data AdditionChain
= One
 Add AdditionChain AdditionChain
deriving (Eq, Show)
instance Denotable AdditionChain where
denote One = 1
denote (Add a b) = (denote a) + (denote b)
Although this new structure doesn't differentiate between doubles and adds, when constructing an addition chain it will be clearer if we indicate which additions are doubles, especially since we count doubles and adds separately.
double a = Add a a
add a b = Add a b
instance Measurable AdditionChain where
d' One = 0
d' (Add a b)  a == b = 1
 otherwise = 0
f' One = 0
f' (Add a b)  a == b = 0
 otherwise = 1
Now let's use it to create an efficient representation of 45:
_45 =
let
__1 = One  given 1: 1
__2 = double __1  append 0: 10
__4 = double __2  append 0: 100
__5 = add __4 __1  add 1: 101
_10 = double __5  append 0: 1010
_20 = double _10  append 0: 10100
_40 = double _20  append 0: 101000
_45 = add _40 __5  add 0b101: 101101
in
_45  45 == 0b101101
As we've done before, we can verify that _45
really represents 45 by checking denote _45 == 45
.
This new representation uses the same number of doublings (5) as the doubleandadd1 representation, but only uses 2 additions instead of 3, a savings of one addition. Looking at the addition chain arithmetically, we constructed the value 5 just like before and then reuse the value 5 later in the computation, after we construct 40, to compute 45 as 40 + 5
. Looking at it bitwise, we can think of the doubling operations as each appending one bit of empty (zerovalued) space, and addition as overwriting that space. In particular, the last three doublings reserve 3 bits of space 0b000
and the final addition of 5 (0b101
) overwrites that space with 0b101
_{2}. Since 0b101
has two bits set, adding it does the same amount of work as two additions of 1.
We can verify that _45
is one addition shorter than doubleAndAdd1_45
by verifying r _45 == (r doubleAndAdd1_45)  1
; we can verify they have the same number of doubles by checking d _45 == d doubleAndAdd1_45
, and we can verify that _45
has one fewer nondoubling addition than doubleAndAdd1_45
checking f _45 == (f doubleAndAdd1_45)  1
:
 The length of the representation; i.e. 'r n == d n + f n'.
r :: (Components a, Measurable a) => a > Count
r n = d n + f n
 The total number of doubles in a representation; 'd n == r n  f n'.
d :: (Components a, Measurable a) => a > Count
d n = sum [d' s  s < components n]
 The number of nondoubles in a representation; 'f n == r n  d n'.
f :: (Components a, Measurable a) => a > Count
f n = sum [f' s  s < components n]
 The set of unique components in a representation.
components :: Components a => a > [a]
components n = nub (components' n)
class Eq a => Components a where
 Maps a representation to a list of all its components. There may be
 duplicates in the result if a step is used multiple times in the
 representation.
components' :: a > [a]
instance Components Peano where
components' POne = [POne]
components' s@(PAdd1 n_minus_1) = s:(components' POne)
instance Components DoubleAndAdd1 where
components' DA1One = [DA1One]
components' s@(DA1Double d) = s:(components' d)
components' s@(DA1DoubleAndAdd1 d) = s:(components' d)
instance Components AdditionChain where
components' One = [One]
components' s@(Add a b) =
s:(components' a) ++ components' b
Saving one addition in this example is a tiny benefit compared to how much introducing doubling helped. However, for very large numbers such as those used in public key cryptography, these savings seem to scale up approximately proportionally with the increase in size of the numbers involved.
Doubleandadd1 chains have a convenient mapping to bit strings, but general addition chains do not. This matches the situation with arithmetic on positive integers. A double step is just a left shift by one bit, and a doubleandadd1 step is just a left shift by one bit followed by setting the least significant bit. We can do this in our heads without too much trouble. In contrast, adding two arbitrary positive integers is much more complicated because we have to carry bits. Although we can add 13 + 3
in our heads, it is not easy to visualize the bitwise effects because of carries:
1101 + 11  10000
Since it is nontrivial to implement addition in terms of setting bits, let's just (ab)use the previouslynoted equivalence between bits
and denote
to define the mapping from addition chains to bits:
instance ToBits AdditionChain where
 The return type of 'bits' was artificially constrained to 'Natural'
 above just to allow this to typecheck.
bits d = denote d
At this point the AdditionChainConstruction
can do three useful things: It can help us (manually) construct efficient addition chains, it can help us verify that an addition chain we construct for a particular value actually represents that value, and it can help us measure the complexity of our addition chains. This is all we need to start experimenting with creating efficient addition chains for whatever numbers we find interesting. From here you can read the resources recommended below and start solving these unsolved problems in the overlapping fields of computer science, additive number theory, algebra, and cryptography:

For a given number
n
, what is a practical algorithm for constructing an addition chain denotingn
that is more efficient than the addition chains generated forn
by any previously known algorithm for automatically constructing addition chains? 
For a given number
n
, what is a practical algorithm for verifying whether an addition chainc
is the most efficient addition chain possible forn
? 
For a given number
n
, what is a practical algorithm for constructing the most efficient addition chain possible forn
?
Recommended Reading
 Section 4.6.3 of The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd Edition) by Donald Knuth is the best introduction to addition chains.

Shortest Addition Chains by Achim Flammenkamp is the most comprehensive resource regarding addition chains, with an awesome bibliography and reports on recent research.