Sie sind hier: Home :: Bereich NIMMT :: Mathematik

V. V. Kochergin

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

We study the generalisation of the problem on efficient computation of the power xⁿ for given x and n (or the equivalent problem on minimal addition chain for the number n), where n ∈ N.

Let l(x^a y^b , x^c y^d ) be the complexity of computation of a system of monomials {x^a y^b , x^c y^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} → ∞ is satisfied, then the relation

l(x^a y^b , x^c y^d ) ∼ log₂(|ad − bc| + a + b + c + d)

is true.

Discrete Mathematics and Applications, Walter de Gruyter

Print ISSN: 0924-9266
Volume: 15, 11/2005
Seiten: 547 - 572

Zum Artikel (extern)

Alle verfügbaren Artikel dieser Zeitschrift anzeigen

 

Bereich NIMMT