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:
“Man ... cannot learn to forget, but hangs on the past: however far or fast he runs, that chain runs with him.”
—Friedrich Nietzsche (1844–1900)
“What though the traveler tell us of the ruins of Egypt, are we so sick or idle that we must sacrifice our America and today to some man’s ill-remembered and indolent story? Carnac and Luxor are but names, or if their skeletons remain, still more desert sand and at length a wave of the Mediterranean Sea are needed to wash away the filth that attaches to their grandeur. Carnac! Carnac! here is Carnac for me. I behold the columns of a larger
and purer temple.”
—Henry David Thoreau (1817–1862)