Addition chains using continued fractions. (English) Zbl 0682.68025

Summary: This paper introduces a new algorithm for the evaluation of monomials in two variables \(x^ ay^ b\) based upon the continued fraction expansion of a/b. A method for fast explicit generation of addition chains of small length for a positive integer n is deduced from this Algorithm. As an illustration of the properties of the method, a Scholz-Brauer-like inequality \(p(N)\leq nb+k+p(n+1)\), is shown to be true whenever N is an integer of the form \(2^ k(1+2^ b+...+2^{nb})\). Computer experimentation has shown that the length of the chains constructed are of optimal length for all integers up to 1000, with 29 exceptions for which the length is equal to the optimal length plus one.


68W99 Algorithms in computer science
11A55 Continued fractions
11A63 Radix representation; digital problems
Full Text: DOI