Welcome, guest | Sign In | My Account | Store | Cart

Polynomial Factoring Using Rational Root Theorem (Python recipe) by Alexander James Wallar
ActiveState Code (http://code.activestate.com/recipes/577974/)

This algorithm factors a polynomial but will only factor it by giving the rational roots. For instance if one of the roots in the polynomial was irrational, the polynomial would not be factored correctly.

Python, 31 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from math import ceil
listOfFactors = lambda n: {i for i in range(1,ceil(abs(n)/2)+1) if n%i == 0}
def removeDuplicates(mylist):
    if mylist:
        mylist.sort()
        last = mylist[-1]
        for i in range(len(mylist)-2, -1, -1):
            if last == mylist[i]:
                del mylist[i]
            else:
                last = mylist[i]
    return mylist

def polyRoots(polyListCoeff):
    allFactors = set()
    allFactorsListOld = list(allFactors.union(listOfFactors(polyListCoeff[0]),{polyListCoeff[0]},listOfFactors(polyListCoeff[-1]),{polyListCoeff[-1]}))
    allFactorsListOld.extend([-1*i for i in allFactorsListOld])
    allFactorsList = list()
    for k in allFactorsListOld:
        for j in allFactorsListOld:
            allFactorsList.append(k/j)
    allFactorsList = removeDuplicates(allFactorsList)
    polyListCoeff.reverse()
    roots = [i for i in allFactorsList if sum([pow(i,j)*polyListCoeff[j] for j in range(0,len(polyListCoeff))]) == 0]
    factorList = list()
    for i in roots:
        if i<0:
            factorList.append("(x+{})".format(-i))
        else:
            factorList.append("(x-{})".format(i))
    return "".join(factorList)

Here is an example of the factoring of x^2 - 4

>>> polyRoots([1,0,-4])
'(x+2.0)(x-2.0)'
Tags: poly, polynomial, polyroots, poly_roots, rational, rational_root_theorem, root, roots, theorem