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:

    “A chain is no stronger than its weakest link, and life is after all a chain.”
    —William James (1842–1910)

    “No doubt, the short distance to which you can see in the woods, and the general twilight, would at length react on the inhabitants, and make them savages. The lakes also reveal the mountains, and give ample scope and range to our thought.”
    —Henry David Thoreau (1817–1862)