Function hacspec_halo2::divide_polyx

pub fn divide_polyx(n: Polyx, d: Polyx) -> (Polyx, Polyx)

Perform polynomial long division, returning the quotient and the remainder. The algorithm is from https://en.wikipedia.org/wiki/Polynomial_long_division.

The pseudo-code is shown here:

function n / d is
 require d ≠ 0
 q ← 0
 r ← n             // At each step n = d × q + r

 while r ≠ 0 and degree(r) ≥ degree(d) do
     t ← lead(r) / lead(d)       // Divide the leading terms
     q ← q + t
     r ← r − t × d

 return (q, r)

Arguments

• n - the dividend/enumerator polynomial
• d - the divisor/denominator polynomial