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:
“The years seemed to stretch before her like the land: spring, summer, autumn, winter, spring; always the same patient fields, the patient little trees, the patient lives; always the same yearning; the same pulling at the chain—until the instinct to live had torn itself and bled and weakened for the last time, until the chain secured a dead woman, who might cautiously be released.”
—Willa Cather (1873–1947)
“The grace of novelty and the length of habit, though so very opposite to one another, yet agree in this, that they both alike keep us from discovering the faults of our friends.”
—François, Duc De La Rochefoucauld (1613–1680)