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)
“At length they all to merry London came,
To merry London, my most kindly nurse,
That to me gave this life’s first native source;
Though from another place I take my name,
An house of ancient fame.”
—Edmund Spenser (1552?–1599)