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)

    “Oft have I mused, but now at length I find,
    Why those that die, men say they do depart.”
    —Sir Philip Sidney (1554–1586)