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. Define
Because the denominator is even, selecting the numerator parity matching proves
Iterate 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]

Articles by others on the same topic (0)

There are currently no matching articles.