Bostan-Mori algorithm
ID: bostan-mori-algorithm
The Bostan-Mori algorithm computes without expanding all preceding coefficients. Work over a commutative ring with a unit; then the quotient defines a formal power series.
Set and . The polynomial contains only even powers. DefineBecause the denominator is even, selecting the numerator parity matching provesIterate until , then return . With bounded numerator/denominator polynomial degrees , the arithmetic complexity is , where is the cost of multiplying degree- polynomials.
For , the denominator update is . An odd index also multiplies the numerator by , recovering the familiar binary-powering pattern.[ref]
New to topics? Read the docs here!