Skip to content

Commit 66eb36d

Browse files
Canderton74Canderton74
authored
Fixed polynomial division (#2130)
1 parent cad4754 commit 66eb36d

File tree

2 files changed

+109
-40
lines changed

2 files changed

+109
-40
lines changed

‎algorithms/maths/polynomial.py

Lines changed: 61 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -438,28 +438,19 @@ def __floordiv__(self, other: Union[int, float, Fraction, Monomial]):
438438
# def __truediv__(self, other: Union[int, float, Fraction, Monomial, Polynomial]) -> Polynomial:
439439
def __truediv__(self, other: Union[int, float, Fraction, Monomial]):
440440
"""
441-
For Polynomials, only division by a monomial
442-
is defined.
443-
444-
TODO: Implement polynomial / polynomial.
441+
For Polynomial division, no remainder is provided. Must use poly_long_division() to capture remainder
445442
"""
446443
if isinstance(other, int) or isinstance(other, float) or isinstance(other, Fraction):
447444
return self.__truediv__( Monomial({}, other) )
448445
elif isinstance(other, Monomial):
449446
poly_temp = reduce(lambda acc, val: acc + val, map(lambda x: x / other, [z for z in self.all_monomials()]), Polynomial([Monomial({}, 0)]))
450447
return poly_temp
451448
elif isinstance(other, Polynomial):
452-
if Monomial({}, 0) in other.all_monomials():
453-
if len(other.all_monomials()) == 2:
454-
temp_set = {x for x in other.all_monomials() if x != Monomial({}, 0)}
455-
only = temp_set.pop()
456-
return self.__truediv__(only)
457-
elif len(other.all_monomials()) == 1:
458-
temp_set = {x for x in other.all_monomials()}
459-
only = temp_set.pop()
460-
return self.__truediv__(only)
461-
462-
raise ValueError('Can only divide a polynomial by an int, float, Fraction, or a Monomial.')
449+
# Call long division
450+
quotient, remainder = self.poly_long_division(other)
451+
return quotient # Return just the quotient, remainder is ignored here
452+
453+
raise ValueError('Can only divide a polynomial by an int, float, Fraction, Monomial, or Polynomial.')
463454

464455
return
465456

@@ -526,7 +517,59 @@ def subs(self, substitutions: Union[int, float, Fraction, Dict[int, Union[int, f
526517

527518
def __str__(self) -> str:
528519
"""
529-
Get a string representation of
530-
the polynomial.
520+
Get a properly formatted string representation of the polynomial.
521+
"""
522+
sorted_monos = sorted(self.all_monomials(), key=lambda m: sorted(m.variables.items(), reverse=True),
523+
reverse=True)
524+
return ' + '.join(str(m) for m in sorted_monos if m.coeff != Fraction(0, 1))
525+
526+
def poly_long_division(self, other: 'Polynomial') -> tuple['Polynomial', 'Polynomial']:
531527
"""
532-
return ' + '.join(str(m) for m in self.all_monomials() if m.coeff != Fraction(0, 1))
528+
Perform polynomial long division
529+
Returns (quotient, remainder)
530+
"""
531+
if not isinstance(other, Polynomial):
532+
raise ValueError("Can only divide by another Polynomial.")
533+
534+
if len(other.all_monomials()) == 0:
535+
raise ValueError("Cannot divide by zero polynomial.")
536+
537+
quotient = Polynomial([])
538+
remainder = self.clone()
539+
540+
divisor_monos = sorted(other.all_monomials(), key=lambda m: sorted(m.variables.items(), reverse=True),
541+
reverse=True)
542+
divisor_lead = divisor_monos[0]
543+
544+
while remainder.all_monomials() and max(remainder.variables(), default=-1) >= max(other.variables(),
545+
default=-1):
546+
remainder_monos = sorted(remainder.all_monomials(), key=lambda m: sorted(m.variables.items(), reverse=True),
547+
reverse=True)
548+
remainder_lead = remainder_monos[0]
549+
550+
if not all(remainder_lead.variables.get(var, 0) >= divisor_lead.variables.get(var, 0) for var in
551+
divisor_lead.variables):
552+
break
553+
554+
lead_quotient = remainder_lead / divisor_lead
555+
quotient = quotient + Polynomial([lead_quotient]) # Convert Monomial to Polynomial
556+
557+
remainder = remainder - (
558+
Polynomial([lead_quotient]) * other) # Convert Monomial to Polynomial before multiplication
559+
560+
return quotient, remainder
561+
562+
dividend = Polynomial([
563+
Monomial({1: 3}, 4), # 4(a_1)^3
564+
Monomial({1: 2}, 3), # 3(a_1)^2
565+
Monomial({1: 1}, -2), # -2(a_1)
566+
Monomial({}, 5) # +5
567+
])
568+
569+
divisor = Polynomial([
570+
Monomial({1: 1}, 2), # 2(a_1)
571+
Monomial({}, -1) # -1
572+
])
573+
574+
quotient = dividend / divisor
575+
print("Quotient:", quotient)

‎tests/test_polynomial.py

Lines changed: 48 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -105,27 +105,6 @@ def test_polynomial_multiplication(self):
105105
]))
106106
return
107107

108-
def test_polynomial_division(self):
109-
110-
# Should raise a ValueError if the divisor is not a monomial
111-
# or a polynomial with only one term.
112-
self.assertRaises(ValueError, lambda x, y: x / y, self.p5, self.p3)
113-
self.assertRaises(ValueError, lambda x, y: x / y, self.p6, self.p4)
114-
115-
self.assertEqual(self.p3 / self.p2, Polynomial([
116-
Monomial({}, 1),
117-
Monomial({1: 1, 2: -1}, 0.75)
118-
]))
119-
self.assertEqual(self.p7 / self.m1, Polynomial([
120-
Monomial({1: -1, 2: -3}, 2),
121-
Monomial({1: 0, 2: -4}, 1.5)
122-
]))
123-
self.assertEqual(self.p7 / self.m1, Polynomial([
124-
Monomial({1: -1, 2: -3}, 2),
125-
Monomial({2: -4}, 1.5)
126-
]))
127-
return
128-
129108
def test_polynomial_variables(self):
130109
# The zero polynomial has no variables.
131110

@@ -172,4 +151,51 @@ def test_polynomial_clone(self):
172151
self.assertEqual(self.p5.clone(), Polynomial([
173152
Monomial({1: -1, 3: 2}, 1)
174153
]))
175-
return
154+
return
155+
156+
def test_polynomial_long_division(self):
157+
"""
158+
Test polynomial long division
159+
"""
160+
161+
# Dividend: 4a_1^3 + 3a_1^2 - 2a_1 + 5
162+
dividend = Polynomial([
163+
Monomial({1: 3}, 4), # 4(a_1)^3
164+
Monomial({1: 2}, 3), # 3(a_1)^2
165+
Monomial({1: 1}, -2), # -2(a_1)
166+
Monomial({}, 5) # +5
167+
])
168+
169+
# Divisor: 2a_1 - 1
170+
divisor = Polynomial([
171+
Monomial({1: 1}, 2), # 2(a_1)
172+
Monomial({}, -1) # -1
173+
])
174+
175+
# Expected Quotient: 2a_1^2 + (5/2)a_1 + 1/4
176+
expected_quotient = Polynomial([
177+
Monomial({1: 2}, 2), # 2(a_1)^2
178+
Monomial({1: 1}, Fraction(5, 2)), # (5/2)(a_1)
179+
Monomial({}, Fraction(1, 4)) # +1/4
180+
])
181+
182+
# Expected Remainder: 21/4
183+
expected_remainder = Polynomial([
184+
Monomial({}, Fraction(21, 4)) # 21/4
185+
])
186+
187+
quotient_long_div, remainder_long_div = dividend.poly_long_division(divisor)
188+
189+
quotient_truediv = dividend / divisor # Calls __truediv__, which returns only the quotient
190+
191+
# Check if quotient from poly_long_division matches expected
192+
self.assertEqual(quotient_long_div, expected_quotient)
193+
194+
# Check if remainder from poly_long_division matches expected
195+
self.assertEqual(remainder_long_div, expected_remainder)
196+
197+
# Check if quotient from __truediv__ matches quotient from poly_long_division
198+
self.assertEqual(quotient_truediv, quotient_long_div)
199+
200+
return
201+

0 commit comments

Comments
 (0)