While implementing yet another iterated squaring algorithm (yep, this one) and thinking on possible optimizations I've bounced into addition-substraction chains.
An addition-substraction chain for some positive integer N is a list of positive integers which
- begins with 1,
- all the other elements are either the sum or the difference of two earlier members (which can be same in the case of addition) of the list,
- ends with N.
For example, 1,2,4,8,16,32,64,60 is an addition-substraction chain of length 8 for 60.
The question is to determine the complexity of the following question: given an integer N, what is the length of the shortest addition-substraction chain for N?
(Of course it's somewhere around O(lgN).)
No comments:
Post a Comment