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)
“A playwright ... is ... the litmus paper of the arts. He’s got to be, because if he isn’t working on the same wave length as the audience, no one would know what in hell he was talking about. He is a kind of psychic journalist, even when he’s great.”
—Arthur Miller (b. 1915)