Geodesic
Improvement of complexity bounds of monomials and sets of powers computations in Bellman's and Knuth's problems
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 6, pp. 51-72

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2014_21_6_a4,
     author = {V. V. Kochergin},
     title = {Improvement of complexity bounds of monomials and sets of powers computations in {Bellman's} and {Knuth's} problems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {51--72},
     publisher = {mathdoc},
     volume = {21},
     number = {6},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_6_a4/}
}
TY  - JOUR
AU  - V. V. Kochergin
TI  - Improvement of complexity bounds of monomials and sets of powers computations in Bellman's and Knuth's problems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 51
EP  - 72
VL  - 21
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_6_a4/
LA  - ru
ID  - DA_2014_21_6_a4
ER  - 
%0 Journal Article
%A V. V. Kochergin
%T Improvement of complexity bounds of monomials and sets of powers computations in Bellman's and Knuth's problems
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 51-72
%V 21
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_6_a4/
%G ru
%F DA_2014_21_6_a4
V. V. Kochergin. Improvement of complexity bounds of monomials and sets of powers computations in Bellman's and Knuth's problems. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 6, pp. 51-72. http://geodesic.mathdoc.fr/item/DA_2014_21_6_a4/