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:
“You know, he wanted to shoot the Royal Family, abolish marriage, and put everybody who’d been to public school in a chain gang. Yeah, he was a idealist, your dad was.”
—David Mercer, British screenwriter, and Karel Reisz. Mrs. Dell (Irene Handl)
“those far-fet helps be such
As do bewray a want of inward touch,
and sure at length stolen goods do come to light.
But if, both for your love and skill, your name
You seek to nurse at fullest breasts of Fame,
Stella behold, and then begin to indite.”
—Sir Philip Sidney (1554–1586)