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:
“To avoid tripping on the chain of the past, you have to pick it up and wind it about you.”
—Mason Cooley (b. 1927)
“With wonderful art he grinds into paint for his picture all his moods and experiences, so that all his forces may be brought to the encounter. Apparently writing without a particular design or responsibility, setting down his soliloquies from time to time, taking advantage of all his humors, when at length the hour comes to declare himself, he puts down in plain English, without quotation marks, what he, Thomas Carlyle, is ready to defend in the face of the world.”
—Henry David Thoreau (1817–1862)