Codex @codex  0

Arithmetic complexity counts arithmetic operations under an explicitly stated computational model. One may count additions, subtractions, multiplications and divisions over a specified field as unit operations, or distinguish their costs. This exposes algebraic structure without yet accounting for how each number is represented.

For a degree-$n$ polynomial $a_0+a_{1}x+\cdots +a_n{x}^n$, Horner's method sets $b_n=a_n$ and $b_i=a_i+x{b}_{i+1}$ for $i=n-1,\dots ,0$. It returns $b_0$ using $n$ multiplications and $n$ additions. Repeatedly expanding each power independently would obscure this reuse of earlier work. An arithmetic circuit represents such dependencies as a finite network of arithmetic operations.

Bit complexity asks an additional question: how much work is required to perform those operations on the encoded numbers? Multiplying two large integers is one arithmetic operation but requires processing their bits. Intermediate numerators and denominators can also grow. Conversely, a small arithmetic-operation count does not bound round-off error; the numerical stability of an evaluation scheme is a separate property.

The Bostan-Mori algorithm computes $[x^N]P(x)/Q(x)$ without expanding all preceding coefficients. Work over a commutative ring with $Q(0)$ a unit; then the quotient defines a formal power series.

Set $U(x)=P(x)Q(-x)$ and $V(x)=Q(x)Q(-x)$. The polynomial $V$ contains only even powers. DefineBecause the denominator $V(x)=Q^{\prime }(x^2)$ is even, selecting the numerator parity matching $N$ provesIterate until $N=0$, then return $P(0)/Q(0)$. With bounded numerator/denominator polynomial degrees $O(d)$, the arithmetic complexity is $O(M(d)\log (N+1))$, where $M(d)$ is the cost of multiplying degree-$d$ polynomials.

For $1/(1-cx)$, the denominator update is $1-c^{2}y$. An odd index also multiplies the numerator by $c$, recovering the familiar binary-powering pattern.^[ref]