Geodesic
On the complexity of the computation of a pair of monomials in two variables
Diskretnaya Matematika, Tome 17 (2005) no. 4, pp. 116-142.

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

We study the generalisation of the problem on efficient computation of the power $x^n$ for given $x$ and $n$ (or the equivalent problem on minimal addition chain for the number $n$), where $n\in\mathbf N$. Let $l(x^ay^b,x^cy^d)$ be the complexity of computation of a system of monomials $\{x^ay^b,x^cy^d\}$, that is, the minimum number of multiplication operations needed to compute this system of monomials in variables $x$ and $y$ for given $a$, $b$, $c$, and $d$ (the intermediate results are allowed to be used repeatedly). We prove that if the condition $\max\{a,b,c,d\}\to\infty$ is satisfied, then the relation $$ l(x^{a}y^{b}, x^{c}y^{d})\sim\log_2(|ad-bc|+a+b+c+d) $$ is true. This research was supported by the Russian Foundation for Basic Research, grant 05–01–00994, by the Program of the President of the Russian Federation for support of leading scientific schools, grant 1807.2003.1, and by the program ‘Universities of Russia,’ grant 04.02.528. 
@article{DM_2005_17_4_a11,
     author = {V. V. Kochergin},
     title = {On the complexity of the computation of a pair of monomials in two variables},
     journal = {Diskretnaya Matematika},
     pages = {116--142},
     publisher = {mathdoc},
     volume = {17},
     number = {4},
     year = {2005},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2005_17_4_a11/}
}
TY  - JOUR
AU  - V. V. Kochergin
TI  - On the complexity of the computation of a pair of monomials in two variables
JO  - Diskretnaya Matematika
PY  - 2005
SP  - 116
EP  - 142
VL  - 17
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2005_17_4_a11/
LA  - ru
ID  - DM_2005_17_4_a11
ER  - 
%0 Journal Article
%A V. V. Kochergin
%T On the complexity of the computation of a pair of monomials in two variables
%J Diskretnaya Matematika
%D 2005
%P 116-142
%V 17
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2005_17_4_a11/
%G ru
%F DM_2005_17_4_a11
V. V. Kochergin. On the complexity of the computation of a pair of monomials in two variables. Diskretnaya Matematika, Tome 17 (2005) no. 4, pp. 116-142. http://geodesic.mathdoc.fr/item/DM_2005_17_4_a11/

[1] Knut D. E., Iskusstvo programmirovaniya dlya EVM, t. 2, Mir, Moskva, 1977 | Zbl

[2] Brauer A., “On addition chains”, Bull. Amer. Math. Soc., 45 (1939), 736–739 | DOI | MR | Zbl

[3] Bellman R. E., “Addition chains of vectors”, Amer. Math. Monthly, 70 (1963), 765

[4] Straus E. G., “Addition chains of vectors”, Amer. Math. Monthly, 71 (1964), 806–808 | DOI | MR

[5] Yao A. C.-C., “On the evaluation of powers”, SIAM J. Comput., 5 (1976), 100–103 | DOI | MR | Zbl

[6] Gashkov S. B., Kochergin V. V., “Ob additivnykh tsepochkakh vektorov, ventilnykh skhemakh i slozhnosti vychisleniya stepenei”, Metody diskretnogo analiza v teorii grafov i slozhnosti, 52 (1992), 22–40 | MR | Zbl

[7] Kochergin V. V., “O slozhnosti vychislenii odnochlenov i naborov stepenei”, Diskretnyi analiz, 27, 1994, 94–107 | MR | Zbl

[8] Kochergin V. V., “O dvukh obobscheniyakh zadachi ob additivnykh tsepochkakh”, Trudy IV Mezhdunarodnoi konferentsii «Diskretnye modeli v teorii upravlyayuschikh sistem», MAKS, Moskva, 2000, 55–59

[9] Pippenger N., “On evaluation of powers and monomials”, SIAM J. Comput., 9:2 (1980), 230–250 | DOI | MR | Zbl

[10] Kochergin V. V., “O slozhnosti vychisleniya sistem odnochlenov s ogranicheniyami na stepeni peremennykh”, Diskretnaya matematika, 10:3 (1998), 27–34 | MR | Zbl

[11] Kochergin V. V., “O poryadke rosta slozhnosti vychisleniya sistem odnochlenov ot mnogikh peremennykh”, Materialy Sibirskoi konferentsii po issledovaniyu operatsii SCOR'98, Novosibirsk, 1998, 129

[12] Kochergin V. V., Materialy X Mezhgosudarstvennoi shkoly-seminara «Sintez i slozhnost upravlyayuschikh sistem», Izd-vo tsentra prikladnykh issledovanii pri mekhaniko-matematicheskom fakultete MGU, 2000, 12–14

[13] Kochergin V. V., “O nekotorykh obobscheniyakh zadachi ob additivnykh tsepochkakh”, Diskretnaya matematika i ee prilozheniya, Sbornik lektsii, Izd-vo Tsentra prikladnykh issledovanii pri mekhaniko-matematicheskom fakultete MGU, Moskva, 2001, 59–83

[14] Sevidzh D. E., Slozhnost vychislenii, Faktorial, Moskva, 1998

[15] Lupanov O. B., “Ob odnom podkhode k sintezu upravlyayuschikh sistem — printsipe lokalnogo kodirovaniya”, Problemy kibernetiki, 14 (1965), 31–110 | MR | Zbl