Write a pseudocode algorithm for polynomial division. polynomials are represente
ID: 3585472 • Letter: W
Question
Write a pseudocode algorithm for polynomial division.
polynomials are represented with an array. e.g. 1 + 2x^2 - x^3 is represented by the array [1, 0, 2, -1]
Use the following definition of polynomial division:
Given two polynomials u and v, with v != "0", you can divide u by v to obtain a quotient polynomial q and a remainder polynomial r satisfying the condition u = "q * v + r", where the degree of r is strictly less than the degree of v, the degree of q is no greater than the degree of u, and r and q have no negative exponents.
For the purposes of this problem, the operation "u / v" returns q as defined above.
Some examples of how the algorithm should behave:
(x^3-2*x+3) / (3*x^2) = 1/3*x (with r = "-2*x+3").
(x^2+2*x+15) / (2*x^3) = 0 (with r = "x^2+2*x+15").
(x^3+x-1) / (x+1) = x^2-x+2 (with r = "-3").
Explanation / Answer
Algorithm
----------------------------------------------------------------------------------------------------------------------------------------
degree(P)
{
if all elements are 0
return -
else
return (index of the last non-zero element of P)
}
polynomial_division(u,v)
{
// u,v,q,r are vectors
if degree(v) < 0 "Error"
while degree(u) degree(v)
{
d v shifted right by (degree(u) - degree(v))
q(degree(u) - degree(v)) u(degree(u)) / d(degree(d))
d d * q(degree(u) - degree(v))
u u - d
}
r u
return (q,r)
}
-----------------------------------------------------------------------------------------------------------------------------------------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.