Addition chains using continued fractions. (English) Zbl 0682.68025

Bergeron, F.; Berstel, J.; Brlek, S.; Duboc, C.

J. Algorithms 10, No. 3, 403-412 (1989).

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.

MSC:

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

Keywords:

evaluation of monomials in two variables