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:
“It would be some advantage to live a primitive and frontier life, though in the midst of an outward civilization, if only to learn what are the gross necessaries of life and what methods have been taken to obtain them.”
—Henry David Thoreau (1817–1862)
“The force of truth that a statement imparts, then, its prominence among the hordes of recorded observations that I may optionally apply to my own life, depends, in addition to the sense that it is argumentatively defensible, on the sense that someone like me, and someone I like, whose voice is audible and who is at least notionally in the same room with me, does or can possibly hold it to be compellingly true.”
—Nicholson Baker (b. 1957)
“While over Alabama earth
These words are gently spoken:
Serve—and hate will die unborn.
Love—and chains are broken.”
—Langston Hughes (20th century)