Volume 21, No 6, 2014, P. 51-72

UDC 519.7
V. V. Kochergin
Improvement of complexity bounds of monomials and sets of powers computations in Bellman’s and Knuth’s problems

Abstract:
Two generalizations of the classical problem of the fastest calculation of exponent are studied. Namely, Bellman’s problem on computational complexity (the minimal number of multiplication operations) based on a normalized monomial of m variables and Knuth’s problem on complexity of simultaneous calculation of a system of m powers of one variable. Some results for these problems are reviewed in the paper. Asymptotic complexity bounds for Bellman’s and Knuth’s problems are improved for the cases when m and complexity have similar rate of growth. Upper and lower complexity bounds for almost all sets of exponents for Bellman’s and Knuth’s problems that are established provide the complexity growth asymptotic for a wide range of parameters (number of variables or computed exponents, the maximal power, and the product of all powers) and their correlations. Moreover, they provide upper and lower bounds ratio no more than 5/3 for all correlations of the parameters.
Bibliogr. 25.

Keywords: addition chain, evaluation of powers, evaluation of monomials, Bellman’s problem, Knuth’s problem.

Kochergin Vadim Vasilievich ¹
1. Lomonosov Moscow State University,
1 Leninskie Gory, 119991 Moscow, Russia
e-mail: vvkoch@yandex.ru