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:
“I conceive that the leading characteristic of the nineteenth century has been the rapid growth of the scientific spirit, the consequent application of scientific methods of investigation to all the problems with which the human mind is occupied, and the correlative rejection of traditional beliefs which have proved their incompetence to bear such investigation.”
—Thomas Henry Huxley (1825–95)
“The addition of a helpless, needy infant to a couple’s life limits freedom of movement, changes role expectancies, places physical demands on parents, and restricts spontaneity.”
—Jerrold Lee Shapiro (20th century)
“Habit is the ballast that chains a dog to his vomit.”
—Samuel Beckett (1906–1989)