EFFICIENT GENERATION OF SHORTEST ADDITION-MULTIPLICATION CHAINS
Hatem M. Bahig, A. E. A. Mahran · Journal of the Egyptian Mathematical Society · 2018
The aim of this paper is to generalize some results on addition chains to addition-multiplication chains. The pa-per concerns with generating shortest addition-multiplication chains. It rst presents two methods for generating shortaddition-multiplication chains. Second, it presents an algorithm for generating a shortest addition-multiplication chain.Then it proposes three main improvements for generating a shortest addition-multiplication chain. The practical resultsshow that the proposed improvements reduce, on the average, the running time and storage of the algorithm by about95% and 35% respectively for data range 12 20 bits. Similar practical results are obtained for generating all shortestaddition-multiplication chains. Finally, the paper discusses how to apply the algorithm to obtain some results that havebeen uncovered previously.