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:

    “Oft, in the stilly night, Ere Slumber’s chain has bound me, Fond Memory brings the light Of other days around me.”
    —Thomas Moore (1779–1852)

    “The light that was shadowed then
    Was seen to be our lives,
    Everything about us that love might wish to examine,
    Then put away for a certain length of time, until
    The whole is to be reviewed, and we turned
    Toward each other, to each other.”
    —John Ashbery (b. 1927)