Polynomial Long Division - Pseudo-code

Pseudo-code

The algorithm can be represented in pseudo-code as follows, where +, -, and × represent polynomial arithmetic, and / represents simple division of two terms:

function n / d: require d ≠ 0 (q, r) ← (0, n) # At each step n = d × q + r while r ≠ 0 AND degree(r) ≥ degree(d): t ← lead(r)/lead(d) # Divide the leading terms (q, r) ← (q + t, r - (t * d)) return (q, r)

Note that this works equally well when degree(n) < degree(d); in that case the result is just the trivial (0, n).

This algorithm describes exactly above paper and pencil method: d is written on the left of the ")"; q is written, term after term, above the horizontal line, the last term being the value of t; the region under the horizontal line is used to compute and write down the successive values of r.