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:
“Commerce is unexpectedly confident and serene, alert, adventurous, and unwearied. It is very natural in its methods withal, far more so than many fantastic enterprises and sentimental experiments, and hence its singular success.”
—Henry David Thoreau (1817–1862)
“The most important American addition to the World Experience was the simple surprising fact of America. We have helped prepare mankind for all its later surprises.”
—Daniel J. Boorstin (b. 1914)
“He that has his chains knocked off, and the prison doors set open to him, is perfectly at liberty, because he may either go or stay, as he best likes; though his preference be determined to stay, by the darkness of the night, or illness of the weather, or want of other lodging. He ceases not to be free, though the desire of some convenience to be had there absolutely determines his preference, and makes him stay in his prison.”
—John Locke (1632–1704)