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:

    The reading public is intellectually adolescent at best, and it is obvious that what is called “significant literature” will only be sold to this public by exactly the same methods as are used to sell it toothpaste, cathartics and automobiles.
    Raymond Chandler (1888–1959)

    But the best read naturalist who lends an entire and devout attention to truth, will see that there remains much to learn of his relation to the world, and that it is not to be learned by any addition or subtraction or other comparison of known quantities, but is arrived at by untaught sallies of the spirit, by a continual self-recovery, and by entire humility.
    Ralph Waldo Emerson (1803–1882)

    Let the saints be joyful in glory: let them sing aloud upon their beds. Let the high praises of God be in their mouth, and a two-edged sword in their hand; to execute vengeance upon the heathen, and punishments upon the people; to bind their kings with chains and their nobles with fetters of iron; to execute upon them the judgment written.
    Bible: Hebrew Psalms 149:5-9.