Addition Chain - Chain Length

Chain Length

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

,

where is Hamming weight of binary expansion of n.

It is clear that l(2n) ≤ l(n)+1. Strict inequality is possible, as l(382) = l(191) = 11, observed by Knuth.

Read more about this topic:  Addition Chain

Famous quotes containing the words chain and/or length:

    “To avoid tripping on the chain of the past, you have to pick it up and wind it about you.”
    —Mason Cooley (b. 1927)

    “Your length in clay’s now competent,
    A long war disturbed your mind;”
    —John Webster (c. 1580–1638)