Addition Chain - Chain Length

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 conclusion suggested by these arguments might be called the paradox of theorizing. It asserts that if the terms and the general principles of a scientific theory serve their purpose, i. e., if they establish the definite connections among observable phenomena, then they can be dispensed with since any chain of laws and interpretive statements establishing such a connection should then be replaceable by a law which directly links observational antecedents to observational consequents.
    —C.G. (Carl Gustav)

    At length to hospital
    This man was limited,
    Where screens leant on the wall
    And idle headphones hung.
    Since he would soon be dead
    They let his wife come along
    And pour out tea, each day.
    Philip Larkin (1922–1986)