Anonymous user
Polynomial long division: Difference between revisions
m
tighten up some formatting
(→{{header|Python}}: can't index when deg < 0, and unnecessary) |
m (tighten up some formatting) |
||
Line 2:
<cite>In algebra, [[wp:Polynomial long division|polynomial long division]] is an algorithm for dividing a polynomial by another polynomial of the same or lower degree.</cite>
Let us suppose a polynomial is represented by a vector (e.g. see [[wp:Coefficient|here]]), then the <math>i
from left) followed by a multiplication of each element by the coefficient of the monomial.
Then a pseudocode for the polynomial long division could be:
degree(
'''return''' the index of the last non-zero element of
if all elements are 0, return -∞
polynomial_long_division('''N''', '''D''') ''returns'' ('''q''', '''r'''):
<span class="co1">// '''N''', '''D''', '''q''', '''r''' are vectors</span>
'''if''' degree('''D''') < 0 '''then''' ''error''
'''if''' degree('''N''') ≥ degree('''D''') '''then'''
Line 19:
'''d''' ← '''D''' ''shifted right'' ''by'' (degree('''N''') - degree('''D'''))
'''q'''(degree('''N''') - degree('''D''')) ← '''N'''(degree('''N''')) / '''d'''(degree('''d'''))
<span
'''d''' ← '''d''' * '''q'''(degree('''N''') - degree('''D'''))
'''N''' ← '''N''' - '''d'''
Line 385:
proc poldiv {a b} {
# Toss out leading zero coefficients efficiently▼
▲ # Toss out leading zero coefficients
while {[lindex $a end] == 0} {set a [lrange $a[set a {}] 0 end-1]}
while {[lindex $b end] == 0} {set b [lrange $b[set b {}] 0 end-1]}
Line 396 ⟶ 393:
# Rearrange the terms to put highest powers first
set n [lreverse $a]
set d [lreverse $b]
Line 402 ⟶ 398:
# Carry out classical long division, accumulating quotient coefficients
# in q, and replacing n with the remainder.
set q {}
while {[llength $n] >= [llength $d]} {
Line 416 ⟶ 411:
# Return quotient and remainder, constant term first
return [list [lreverse $q] [lreverse $n]]
}
# Demonstration
lassign [poldiv {-42. 0. -12. 1.} {-3. 1. 0. 0.}] Q R
puts [list Q = $Q]
| |||