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)
“Men sometimes speak as if the study of the classics would at length make way for more modern and practical studies; but the adventurous student will always study classics, in whatever language they may be written and however ancient they may be. For what are the classics but the noblest recorded thoughts of man?... We might as well omit to study Nature because she is old.”
—Henry David Thoreau (1817–1862)