A Method for Reducing Iteration in Algorithms for Building Minimal Additive Chains
Abstract
Optimization of algorithms for computing the values of polynomials, more precisely, of monomials, is equivalent to the problem of constructing for a given number a minimal additive chain. To search for such chains, no algorithms are known except brute force. The increase in the complexity of the brute force algorithm is very large. Among chains of the same length there are a lot of equivalent ones, that is, those ending with the same number. The article provides a sufficient criterion for the equivalence of chains and shows how the use of the criterion reduces the procedure for the formation of all additive chains of a fixed length.
References
D. Knuth, Iskusstvo programmirovaniya [The Art of Computer Programming], K. I. Babenko and Yu. M. Bayakovskii, eds., vol. 1, Moscow: Iz-vo Mir, 1974 (in Russian).
N. Pippenger, “On the evaluation of powers and monomials,” SIAM J. Comput., vol. 9, no. 2, pp. 230–250, 1980; doi:10.1137/0209022
N. N. Vassiliev, “Evaluations of sparse polynomials and the synthesis of evaluating programs,” in Proc. Internat. Conf. on Comp. Algebra and Appl. Thtor. Phys., Dubna, 1984, pp. 154–159.
V. V. Kochergin, “Utochnenie otsenok slozhnosti vychisleniya odnochlenov i naborov stepenei v zadachakh Bellmana i Knuta” [Improvement of the estimates of the computational complexity for monomials and sets of powers in Bellman’s and Knuth’s problems], J. Appl. Industr. Math., vol. 9, no. 1, pp. 68–82, 2015 (in Russian); doi: 10.1134/S1990478915010081
A. M. Kotochigov, “Algoritmy fraktal’nogo analiza izobrazhenii” [Fractal Image Analysis Algorithms], Computer tools in education, no. 2, pp. 34–39, 2012 (in Russian).
This work is licensed under a Creative Commons Attribution 4.0 International License.
