Addition Chain - Methods For Computing Addition Chains

Methods For Computing Addition Chains

Calculating an addition chain of minimal length is not easy; a generalized version of the problem, in which one must find a chain that simultaneously forms each of a sequence of values, is NP-complete. There is no known algorithm which can calculate a minimal addition chain for a given number with any guarantees of reasonable timing or small memory usage. However, several techniques to calculate relatively short chains exist. One very well known technique to calculate relatively short addition chains is the binary method, similar to exponentiation by squaring. Other well-known methods are the factor method and window method.

Read more about this topic:  Addition Chain

Famous quotes containing the words methods, addition and/or chains:

    A woman might claim to retain some of the child’s faculties, although very limited and defused, simply because she has not been encouraged to learn methods of thought and develop a disciplined mind. As long as education remains largely induction ignorance will retain these advantages over learning and it is time that women impudently put them to work.
    Germaine Greer (b. 1939)

    As easy mayst thou fall
    A drop of water in the breaking gulf,
    And take unmingled thence that drop again,
    Without addition or diminishing,
    As take from me thyself and not me too.
    William Shakespeare (1564–1616)

    While over Alabama earth
    These words are gently spoken:
    Serve—and hate will die unborn.
    Love—and chains are broken.
    Langston Hughes (20th century)