Package InversionTest :: Module PolynomialOperations
[hide private]
[frames] | no frames]

Source Code for Module InversionTest.PolynomialOperations

 1  """ 
 2  Basic univariate polynomial multiplication and division 
 3  Polynomials are represented as sequences of coefficients, 
 4  where the highest coefficient of an expression is stored 
 5  at index=0.  So then, [1, 5, 3] = (x^2 + 5x + 3). 
 6   
 7  This implementation of expansion (multiplication) is 
 8  more robust than its division counterpart.  While 
 9  expansion should work for any set of expressions, 
10  the division will only work for monic polynomials. 
11   
12  Author: Benjamin D. Nye 
13  License: Apache License V2.0 
14  """ 
15   
16 -def polynomialExpansion(*coefficients):
17 """ 18 Expand lists of coefficients for univariate polynomials 19 into a single list of coefficients for the expanded polynomial 20 @param coefficients: Lists of integer coefficients 21 @type coefficients: list of list of int 22 @return: Single list of coefficients for the expanded polynomial 23 @rtype: list of int 24 """ 25 if len(coefficients) == 0 or any(len(coeffs)==0 for coeffs in coefficients): 26 return [] 27 expanded = coefficients[0][:] 28 for coeffs in coefficients[1:]: 29 # Expand to fit new higher-order terms 30 numCoeff = len(coeffs) 31 expanded.extend([0]*(numCoeff-1)) 32 # Multiply and collect 33 for i in xrange(len(expanded)-1,-1,-1): 34 expanded[i] = sum([expanded[i-j]*coeff for j, coeff in enumerate(coeffs[:i+1])]) 35 return expanded
36
37 -def syntheticDivision(numerator, divisor):
38 """ 39 Perform a polynomial division using syntethic division 40 Returns the new coefficients in two parts: quotient and remainder 41 WARNING: Only works for monic polynomials 42 @param numerator: Coefficients for the numerator 43 @type numerator: list of int 44 @param divisor: Coefficients of the divisor 45 @type divisor: list of int 46 @return: Quotient (whole part) and remainder of division. Note: remainder contains only the numberator part 47 @rtype: tuple of (list of int, list of int) 48 """ 49 numerator = removeEmptyTerms(numerator) 50 divisor = removeEmptyTerms(divisor) 51 numeratorLen = len(numerator) 52 divisorLen = len(divisor) 53 if (divisorLen > numeratorLen or len(numerator) == 0 or 54 (divisorLen==numeratorLen and divisor > numerator)): 55 return [], numerator 56 elif divisorLen == 0: 57 return numerator, [] 58 value = numerator[0] 59 quotient = [value] 60 for i in xrange(1, numeratorLen): 61 colStart = max(1, i-(numeratorLen-divisorLen)) 62 colEnd = min(i+1, divisorLen) 63 columnVal = sum([-quotient[i-j]*divisor[j] for j in xrange(colStart, colEnd)]) 64 quotient.append(numerator[i] + columnVal) 65 if divisorLen == 1: 66 return quotient, [] 67 else: 68 return quotient[:-divisorLen+1], quotient[-divisorLen+1:]
69
70 -def removeEmptyTerms(series, removeFromHead=True):
71 """ 72 Remove leading (head) or trailing (tail) zeros 73 from an expression. This is needed to properly 74 evaluate the actual terms in the expression. 75 @param series: Series of coefficients 76 @type series: list of int or float 77 @param removeFromHead: If True, remove zeroes from start of series; else, remove from tail. 78 @type removeFromHead: bool 79 @return: Series with zero-padding removed 80 @rtype: list of int or float 81 """ 82 if removeFromHead: 83 i=0 84 for i, x in enumerate(series): 85 if x != 0: 86 break 87 if i != 0: 88 series = series[i:] 89 else: 90 i=len(series) 91 for i in xrange(len(series)-1,-1,-1): 92 if series[i] != 0: 93 break 94 if i != 0: 95 series = series[:i+1] 96 return series
97