Rule Based Representation of Integer for a New Addition Chain Method
Mohamad Afendee Mohamed, Kamel Ariffin Mohd Atan · 2012
Starting from 1, by restricting the operations to only addition and doubling of two previous terms, finding the least number of terms required to build up a sequence towards an integer n has been a problem since a decade ago. This problem is known as an addition chain problem. Lately, many heuristics methods were developed, of which aims at achieving near optimal solution. Recently, decomposition method, which is based on prime factorization was introduced. Instead of representing number into binary form, this method uses rule to represents each prime from a decomposed n. In this paper, we propose a new method called composition method, based on the generalization of decomposition method, which works out addition chain directly from a single rule representing n. Analysis shows that the length of an addition chain generated by this method is bounded to the same boundary as that of an optimal chain. Empirical result shows a significant improvement over decomposition method. For selected n’s, it can achieve up to 11 percents, although this can vary from integer to another.