

 This page uses content from Wikipedia. The original article was at Polynomial long division. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree.
Let us suppose a polynomial is represented by a vector, 



x


{\displaystyle x}

 (i.e., an ordered collection of coefficients) so that the 



i


{\displaystyle i}

th element keeps the coefficient of 




x

i




{\displaystyle x^{i}}

, and the multiplication by a monomial is a shift of the vector's elements "towards right" (injecting ones from left) followed by a multiplication of each element by the coefficient of the monomial.

Then a pseudocode for the polynomial long division using the conventions described above could be:

degree(P):
  return the index of the last non-zero element of P;
         if all elements are 0, return -∞

polynomial_long_division(N, D) returns (q, r):
  // N, D, q, r are vectors
  if degree(D) < 0 then error
  q ← 0
  while degree(N) ≥ degree(D)
    d ← D shifted right by (degree(N) - degree(D))
    q(degree(N) - degree(D)) ← N(degree(N)) / d(degree(d))
    // by construction, degree(d) = degree(N) of course
    d ← d * q(degree(N) - degree(D))
    N ← N - d
  endwhile
  r ← N
  return (q, r)

Note: vector * scalar multiplies each element of the vector by the scalar; vectorA - vectorB subtracts each element of the vectorB from the element of the vectorA with "the same index". The vectors in the pseudocode are zero-based.

 Error handling (for allocations or for wrong inputs) is not mandatory.
 Conventions can be different; in particular, note that if the first coefficient in the vector is the highest power of x for the polynomial represented by the vector, then the algorithm becomes simpler.

Example for clarification


This example is from Wikipedia, but changed to show how the given pseudocode works.

      0    1    2    3
   ----------------------
N:  -42    0  -12    1        degree = 3
D:   -3    1    0    0        degree = 1

   d(N) - d(D) = 2, so let's shift D towards right by 2:

N:  -42    0  -12    1
d:    0    0   -3    1

   N(3)/d(3) = 1, so d is unchanged. Now remember that "shifting by 2"
   is like multiplying by x2, and the final multiplication
   (here by 1) is the coefficient of this monomial. Let's store this
   into q:
                               0     1     2
                              ---------------
                          q:   0     0     1

   now compute N - d, and let it be the "new" N, and let's loop

N:  -42    0   -9    0        degree = 2
D:   -3    1    0    0        degree = 1

   d(N) - d(D) = 1, right shift D by 1 and let it be d

N:  -42    0   -9    0
d:    0   -3    1    0        * -9/1 = -9

                          q:   0    -9     1

d:    0   27   -9    0        

   N ← N - d

N:  -42  -27    0    0        degree = 1
D:   -3    1    0    0        degree = 1

   looping again... d(N)-d(D)=0, so no shift is needed; we
   multiply D by -27 (= -27/1) storing the result in d, then

                          q:  -27   -9     1

   and

N:  -42  -27    0    0        -
d:   81  -27    0    0        =
N: -123    0    0    0        (last N)

    d(N) < d(D), so now r ← N, and the result is:

       0   1  2
   -------------
q:   -27  -9  1   →  x2 - 9x - 27
r:  -123   0  0   →          -123



Related task

   Polynomial derivative


Option Base 1
Function degree(p As Variant)
    For i = UBound(p) To 1 Step -1
        If p(i) <> 0 Then
            degree = i
            Exit Function
        End If
    Next i
    degree = -1
End Function
 
Function poly_div(ByVal n As Variant, ByVal d As Variant) As Variant
    If UBound(d) < UBound(n) Then
        ReDim Preserve d(UBound(n))
    End If
    Dim dn As Integer: dn = degree(n)
    Dim dd As Integer: dd = degree(d)
    If dd < 0 Then
        poly_div = CVErr(xlErrDiv0)
        Exit Function
    End If
    Dim quot() As Integer
    ReDim quot(dn)
    Do While dn >= dd
        Dim k As Integer: k = dn - dd
        Dim qk As Integer: qk = n(dn) / d(dd)
        quot(k + 1) = qk
        Dim d2() As Variant
        d2 = d
        ReDim Preserve d2(UBound(d) - k)
        For i = 1 To UBound(d2)
            n(UBound(n) + 1 - i) = n(UBound(n) + 1 - i) - d2(UBound(d2) + 1 - i) * qk
        Next i
        dn = degree(n)
    Loop
    poly_div = Array(quot, n) '-- (n is now the remainder)
End Function
 
Function poly(si As Variant) As String
'-- display helper
    Dim r As String
    For t = UBound(si) To 1 Step -1
        Dim sit As Integer: sit = si(t)
        If sit <> 0 Then
            If sit = 1 And t > 1 Then
                r = r & IIf(r = "", "", " + ")
            Else
                If sit = -1 And t > 1 Then
                    r = r & IIf(r = "", "-", " - ")
                Else
                    If r <> "" Then
                        r = r & IIf(sit < 0, " - ", " + ")
                        sit = Abs(sit)
                    End If
                    r = r & CStr(sit)
                End If
            End If
            r = r & IIf(t > 1, "x" & IIf(t > 2, t - 1, ""), "")
        End If
    Next t
    If r = "" Then r = "0"
    poly = r
End Function
 
Function polyn(s As Variant) As String
    Dim t() As String
    ReDim t(2 * UBound(s))
    For i = 1 To 2 * UBound(s) Step 2
        t(i) = poly(s((i + 1) / 2))
    Next i
    t(1) = String$(45 - Len(t(1)) - Len(t(3)), " ") & t(1)
    t(2) = "/"
    t(4) = "="
    t(6) = "rem"
    polyn = Join(t, " ")
End Function
 
Public Sub main()
    Dim tests(7) As Variant
    tests(1) = Array(Array(-42, 0, -12, 1), Array(-3, 1))
    tests(2) = Array(Array(-3, 1), Array(-42, 0, -12, 1))
    tests(3) = Array(Array(-42, 0, -12, 1), Array(-3, 1, 1))
    tests(4) = Array(Array(2, 3, 1), Array(1, 1))
    tests(5) = Array(Array(3, 5, 6, -4, 1), Array(1, 2, 1))
    tests(6) = Array(Array(3, 0, 7, 0, 0, 0, 0, 0, 3, 0, 0, 1), Array(1, 0, 0, 5, 0, 0, 0, 1))
    tests(7) = Array(Array(-56, 87, -94, -55, 22, -7), Array(2, 0, 1))
    Dim num As Variant, denom As Variant, quot As Variant, rmdr As Variant
    For i = 1 To 7
        num = tests(i)(1)
        denom = tests(i)(2)
        tmp = poly_div(num, denom)
        quot = tmp(1)
        rmdr = tmp(2)
        Debug.Print polyn(Array(num, denom, quot, rmdr))
    Next i
End Sub