Algorithm on Addition Chains with Restricted Memory

摘要

This paper considers addition chains, addition sequences and vector additionchains, introducing a new constraint--namely restricted memory--which is important in all of the applications on computers. We consider an algorithm for calculating addition chains, addition sequences and vector addition chains--namely a Generalized Continued Fraction Algorithm--which uses just a restricted number of memory locations on the computer. The average length of addition chains/sequences constructed by this algorithm will be calculated using a number of theoretical tools (from Ergodic Theory and Special Function Theory). Finally, this algorithm will be compared to some other known algorithms.