Package InversionTest ::
Module 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
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
30 numCoeff = len(coeffs)
31 expanded.extend([0]*(numCoeff-1))
32
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
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
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