On the complexity of the computation of a pair of monomials in two variables

V. V. Kochergin

Diskretnaya Matematika, Tome 17 (2005) no. 4, pp. 116-142

Résumé

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.