= Arithmetic complexity
<Arithmetic complexity> counts <arithmetic operation>[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_1x+\cdots+a_nx^n$, <Horner's method> sets $b_n=a_n$ and $b_i=a_i+xb_{i+1}$ for $i=n-1,\ldots,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 operation>[arithmetic operations].
<Bit complexity> asks an additional question: how much work is required to perform those operations on the encoded numbers? Multiplying two <integer>[large integers] is one arithmetic operation but requires processing their <bit>[bits]. Intermediate numerators and denominators can also grow. Conversely, a small <arithmetic operation>[arithmetic-operation] count does not bound <round-off error>; the <numerical stability> of an evaluation scheme is a separate property.
Back to article page
