A Method for Reducing Iteration in Algorithms for Building Minimal Additive Chains

  • Aleksandr M. Kotochigov Saint-Petersburg Electrotechnical University, 5, building 3, st. Professora Popova, 197376, Saint Petersburg, Russia
  • Andrei I. Suchkov Saint-Petersburg Electrotechnical University, 5, building 3, st. Professora Popova, 197376, Saint Petersburg, Russia
Keywords: additive chain, equivalent chain, passive interval, essential randomisation.

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.

Author Biographies

Aleksandr M. Kotochigov, Saint-Petersburg Electrotechnical University, 5, building 3, st. Professora Popova, 197376, Saint Petersburg, Russia

PHd, professor, Head of Department of Algorithmic Mathematics, amkotochigov@gmail.com

Andrei I. Suchkov, Saint-Petersburg Electrotechnical University, 5, building 3, st. Professora Popova, 197376, Saint Petersburg, Russia

Post grad

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).

Published
2020-03-28
How to Cite
Kotochigov, A. M., & Suchkov, A. I. (2020). A Method for Reducing Iteration in Algorithms for Building Minimal Additive Chains. Computer Tools in Education, (1), 5-18. https://doi.org/10.32603/2071-2340-2020-1-5-18
Section
Algorithmic mathematics and mathematical modelling