Open AccessA Method for Reducing Iteration in Algorithms for Building Minimal Additive Chains
Author(s) -
Aleksandr M. Kotochigov,
Andrei I. Suchkov
Publication year - 2020
Publication title -
kompʹûternye instrumenty v obrazovanii
Language(s) - English
Resource type - Journals
eISSN - 2071-2359
pISSN - 2071-2340
DOI - 10.32603/2071-2340-2020-1-5-18
Subject(s) - monomial , brute force , equivalence (formal languages) , mathematics , algorithm , chain (unit) , computer science , mathematical optimization , discrete mathematics , physics , computer security , astronomy
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.