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:

    “Loyalty to petrified opinions never yet broke a chain or freed a human soul in this world—and never will.”
    —Mark Twain [Samuel Langhorne Clemens] (1835–1910)

    “Nor had I erred in my calculations—nor had I endured in vain. I at length felt that I was free.”
    —Edgar Allan Poe (1809–1849)