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:
“Oh yes, that’s right. They chain up wild animals. That’s all I am, an animal.”
—John Elder [Anthony Hinds], British screenwriter, and Terence Fisher. Leon (Oliver Reed)
“When I had mapped the pond ... I laid a rule on the map lengthwise, and then breadthwise, and found, to my surprise, that the line of greatest length intersected the line of greatest breadth exactly at the point of greatest depth.”
—Henry David Thoreau (1817–1862)