Arithmetic complexity of certain linear transformations
Sergey Borisovich Gashkov · Mathematical Notes · 2015
We obtain order-sharp quadratic and slightly higher estimates of the computational complexity of certain linear transformations (binomial, Stirling, Lah, Gauss, Serpiński, Sylvester) in the basis {x + y} ⋃ {ax : |a| ≤ C} consisting of the operations of addition and inner multiplication by a bounded constant as well as upper bounds O(n log n) for the computational complexity in the basis {ax + by : a, b ∈ ℝ} consisting of all linear functions. Lower bounds of the form Ω(n log n) are obtained for the basis consisting of all monotone linear functions {ax + by : a, b > 0}. For the finite arithmetic basis B +,*,/ = {x ± y, xy, 1/x, 1} and for the bases {x ± y} ⋃ {nx : n ∈ ℕ} ⋃ {x/n : n ∈ ℕ} and B +,* = {x + y, xy, −1}, estimates O(n log n log log n) are obtained in certain cases. In the case of a field of characteristic p, computations in the basis {x + y mod p} are also considered.