Improved generation of minimal addition chains
An addition chain for a natural number n is a sequence 1 = a(0) < a(1) <. . . a(r) = n of numbers such that for each 0 < i <= r, a(i) = a(j) + a(k) for some 0 <= k <= j < i. An improvement by a factor of 2 in the generation of all minimal (or one) addition chains is achieved by finding sufficient conditions for star steps, computing what we will call nonstar lower bound in a minimal addition chain and omitting the sorting step.
addition chain nonstar lower bound sorting branch and bound algorithm