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:
“Generalization, especially risky generalization, is one of the chief methods by which knowledge proceeds... Safe generalizations are usually rather boring. Delete that “usually rather.” Safe generalizations are quite boring.”
—Joseph Epstein (b. 1937)
“Napoleon wanted to turn Paris into Rome under the Caesars, only with louder music and more marble. And it was done. His architects gave him the Arc de Triomphe and the Madeleine. His nephew Napoleon III wanted to turn Paris into Rome with Versailles piled on top, and it was done. His architects gave him the Paris Opera, an addition to the Louvre, and miles of new boulevards.”
—Tom Wolfe (b. 1931)
“While over Alabama earth
These words are gently spoken:
Serve—and hate will die unborn.
Love—and chains are broken.”
—Langston Hughes (20th century)