Арифметическая сложность некоторых линейных преобразований

Получены точные по порядку квадратичные и чуть более высокие оценки сложности вычисления некоторых линейных преобразований (биномиального, Стирлинга, Лаха, Гаусса, Серпинского, Сильвестра) в базисе $\{x+y \}\cup \{ax: \vert a \vert \leq C \}$, состоящем из операции сложения и скалярных умножений на ограниченные константы, а также верхние оценки $O(n\log n)$ для сложности вычисления в базисе, состоящем из всех линейных функций $\{ax+by: a,b \in {\mathbb R}\}$. Нижние оценки вида $\Omega(n\log n)$ получены для базиса из всех монотонных линейных функций $\{ax+by: a, b > 0\}$.
Для конечного арифметического базиса $B_{+,*,/} = \{x\pm y,xy,1/x,1\}$ и для базисов $\{x\pm y\} \cup \{nx: n \in {\mathbb N}\}\cup \{x/n: n \in {\mathbb N}\}$, $B_{+,*}=\{x+y,xy,-1\}$ в некоторых случаях получены оценки вида $O(n \log n \log \log n)$. В случае полей характеристики $p$ рассматривались также вычисления в базисе $\{x+y \operatorname{mod} p\}$.
Библиография: 21 название.