(a) Rewrite P4.2 write-up and (b) briefly explain changes/non-changes. ] below, subscripts are indicated using $_$, ] and the character at the start of each line has the following meanings: ] $>$ = unchanged original text ] $!$ = new or modified original text ] $]$ = asides and explanations of changes and non-changes > Topics: Functions, array manipulations, error-checking. ] rename first part of "Setup" to "Background" since it is not directly ] related to the programming assignment. ! Setup: > Many computational problems are ultimately solved using > polynomials, even if the theoretical (i.e. purely mathematical) > solutions don't even refer to them. One reason for this is that very > often it is impossible, or impractical, to directly handle the very > complex functions that theoretical methods involve. Because almost all > functions important in practice can be approximated with any desired > precision by using polynomials, they are very often used to simplify > the original problem and make the finding of an approximate solution ! feasible. ! Setup: > Although Matlab does provide support for polynomials, most programming > languages do not. This provides us with an opportunity. In case you > need to manipulate polynomials in a programming language that does not > support them, your role in this part is to implement a set of > functions that manipulate polynomials. The skills you learn will apply > to just about any programming language you are likely to > encounter. Since Matlab already provides support, this is a means for > you to compare your answers with Matlab's. ] the following paragraph implies that, unless otherwise specified, you are to ] assume that a polynomial is represented as an array of coefficients in ] ascending order of degree. > We will represent polynomials by using arrays. Polynomial > $a_n*x^n+a_(n-1)*x^(n-1)+...+a_2*x^2+a_1*x+a_0$ will be represented > by the array $[a0, a1, a2, ..., an-1, an]$. ] the following paragraph defines *canonical*. the definition should ] perhaps be indented to make it stand out. > Note that the array stores the coefficients in right-to-left > order. Matlab, however, stores coefficients in left-to-right order; > therefore, to convert between our representation and Matlab's, you > should use the $fliplr$ function. To make the polynomial representation > unique, we will impose the condition that the representation be in > *canonical* form: the leading coefficient an (last number in the vector) > must be non-zero for all polynomials except the constant polynomial $0$. > > We will consider the following operations for/on polynomials: > creation, addition, subtraction, multiplication, division, and > evaluation. Remember that polynomial divisions typically generate a > remainder. (See Examples below.) > > Since part of programming is debugging and testing, we will ask you to > write a Matlab script file that performs some tests to check that your > implementation works. > > Task: > > Implement Matlab functions for all the operations mentioned > above and ! a function that tests your other functions. ] make testing be a function, too. ] this sentence reinforces the assumption that polynomials are ] represented as an array of coefficients: > Except for $makepoly$, your functions may assume their arguments are > in canonical form. > The respective functions and script should have the arguments > and behavior specified below: > > Function Name Required Functionality > > $makepoly (p)$ Compute canonical form for polynomial $p$ (provided > already as a vector of coefficients): strip off > "leading" $0$s (trailing $0$s in the vector). > > $addpoly(p1,p2)$ Compute and return $p2+p1$. > ! $subpoly(p1,p2)$ Compute and return $p1-p2 ] $p1-p2$ instead of $p2-p1$ matches examples below & order of parameeters ! $mulpoly(p1,p2)$ Compute and return the product of polynomial $p1$ and $p2$. ] change "multiplication" to "product". > Note: do not type the strings $conv$ or $deconv$ anywhere > in your function file. ] rewrite this specification to be simpler and automatically take care of ] returning one or two values: ! $divpoly(p1,p2)$ Compute and return the quotient $q$ and remainder $r$ of ! dividing $p1$ by $p2$, e.g. $[q,r]=divpoly(p1,p2)$. > Note: do not type the strings $conv$ or $deconv$ > anywhere in your function file. ] rewrite this specification to use "evaluate" instead of "compute" and ] indicate we want $x=x0$. ! $evalpoly(p,x0) Evaluate and return the value of polynomial $p$ at the ! point $x=x0$. ] rewrite specification in bullet form to make points easier to follow ] and include the requirements that code be written that checks ] answers when possible and to check that inverse operations undo each ] other. ! $testpoly$ Run various tests and checks on your functions. ! + Give enough examples to be convincing, but not too many. ! + Think of how to choose relevant examples only. ! + Include degenerate cases, but otherwise avoid trivial ! examples. ! + Include comparisons with Matlab's polynomial functions: ! $polyval$, $conv$, $deconv$. Write code that verifies ! that your code and Matlab's code gives the same answer. ! + Check that addition and subtraction are inverses ! (e.g. $p1+p2-p2 = p1$ and $p1-p2+p2 = p1$) ! and that multiplication and division are inverses. ] delete references to scripts since now they are all functions and rewrite to ] stress what is allowed rather than what is not allowed and reflect the ] inclusion of material from the newsgroup in the write-up itself: ! Turn in the functions listed above. You may define other functions only as ! follows: > If you find testpoly using repetitive code to display values, you may > --but are not required to-- define subfunctions to reduce redundancy. ] delete this, which is wrong anyway: subfunctions are not allowed ] within *scripts* -- they *are* allowed within functions. ! Since subfunctions are not allowed within functions, to allow you do ! do this, we will also allow you to make testpoly a function with no ! input variables and either no output variable or one output variable ! bad that is 0 is all tests are passed and non-zero if some tests are ! flunked: ! ! function [] = testpoly or function bad = testpoly ! ! ! where [] means "no output variables" and the lack of ! parenthesized variables after testpoly means "no input variables". ] delete stuff about $nargout$ since it was not needed. ] original examples are good, but some more are needed. the original examples ] are good because they show examples of leading and/or non-leading ] coefficients of 0 -- non-leading coefficients of 0 must not be omitted! > Examples: > > * Polynomial $x$ is represented as $[0 1]$. > * Polynomial $2*x is represented as $[0 2]$. > * Polynomial $3$ is represented as $[3]$. > * Polynomial $0$ is represented as $[0]$. > * Polynomial $7*x^3$ is represented as $[0 0 0 7]$. > * Polynomial $7*x^3+2*x+3$ is represented as $[3 2 0 7]$. > * Polynomial $23*x+17$ is represented as $[17 23]$. > * Polynomial $x^2+2*x+1$ is represented as $[1 2 1]$. > * The sum of $23*x+17$ and $7*x^3-21*x-14$ is $7*x^3+2*x+3$. > * The difference (second subtracted from the first) of $7*x^3+2*x+3$ and > $7*x^3-21*x-14$ is $23*x+17$. > * The product of $x^2+2*x+1$ and $7*x-14$ is $7*x^3-21*x-14$. > * Dividing $7*x^3+2*x+3$ by $x^2+2*x+1$ yields quotient $7*x-14$ and > remainder $23*x+17$. ] include E5.1 question and answer as a self-exercises to provide ] further examples and insight into canonical form. ! Self-exercise ! The code below for $addpoly$ has good style but isn't quite right. ! Can you spot the problems? ] this is from the E5.1 write-up, not the original P4.2 write-up: > ___________________________________________________________________________ > | function p = addpoly(p1,p2) | > | % addpoly. add two polynomials. | > | % p = addpoly(p1,p2): given polynomials $p1$, $p2$, not necessarily | > | % canonical, return their canonical sum $p$ | > | p = p1 + p2; | > |_________________________________________________________________________| > > a) On some valid values of of $p1$ and $p2$, using $addpoly$ would > produce an incorrect answer. > > Give a concrete example and explain why the answer is wrong. > > b) On some valid values of $p1$ and $p2$, using $addpoly$ would cause > Matlab to report an error. > > Give a concrete example and explain why there is an error. > > HINT: consider the polynomials $x$, $-x$, $5$. ! Answers: ] this is from the E5.1 solutions, not the original P4.2 write-up: > a) $addpoly([0 1], [0 -1])$ produces $[0 0]$ instead of $[0]$. > (sum of $x$ and $-x$ is $0x+0$, which we want simplified to $0$.) > > or > $addpoly([5], [0 1]$ produces $[5 6]$ instead $[5 1]$ > because $[5]$=$5$ is a scalar added to a vector $[0 1]$. > > note: the sum of a non-canonical poly with a canonical poly can be canonical, > e.g. $[0 1] + [0 0] = [0 1]$, i.e. $x + 0 = x$. > > b) $addpoly([0 1], [0 0 1])$ tries to add two vectors of different > sizes, which is an error in Matlab. (the answer should be $[0 1 1]$.) ] include hints for division and $deconv$ from website/newsgroup. ! HINT: how to do division and use $deconv$ ] this is from the website: > let's look at an example computed by hand: > > $6 x^4 - 3 x^3 + 17 x^2 - 7x + 9$ divided by $3 x^2 + 1$ > > let's write $3 x^2 + 1$ as $3 x^2 + 0 x + 1$. > >$ 2 x^2 - 1 x + 5, with remainder -6 x + 4 $ >$ +--------------------------------- $ >$3 x^2 + 0 x + 1 | 6 x^4 - 3 x^3 + 17 x^2 - 7 x + 9 $ >$ 6 x^4 + 0 x^3 + 2 x^2 2 x^2 = 6 x^4 / 3 x^2 $ >$ -------------------------------- $ >$ - 3 x^3 + 15 x^2 - 7 x + 9 $ >$ - 3 x^3 + 0 x^2 - 1 x -1 x = - 3 x^3 / 3 x^2$ >$ -------------------------- $ >$ 15 x^2 - 6 x + 9 $ >$ 15 x^2 + 0 x + 5 5 = 15 x^2 / 3 x^2 $ >$ ---------------- $ >$ - 6 x + 4 $ > > conceptually, what is going on? > > 1. shift divisor $3 x^2 + 0 x + 1$ until it's lead term $3 x^2$ is lined up > with the lead term $6 x^4$ of dividend $6 x^4 - 3 x^3 + 17 x^2 - 7x + 9 $ > > 2. divide dividend's remaining lead term (e.g. $6 x^4$) by divisor's lead > term ($3 x^2$) to get next term (e.g. $6 x^4 / 3 x^2 = 2 x^2$) in quotient > > 3. subtract off corresponding multiple (e.g. $2 x^2 * (3 x^2 + 0 x + 1)$) > of divisor from dividend > > 4. repeat until left with remainder > > let's check our answer using $deconv$: > >$ p1 = [9 -7 17 -3 6]; % canonical rep. of 6 x^4 - 3 x^3 + 17 x^2 - 7x + 9 $ >$ p2 = [1 0 3]; % canonical rep. of 3 x^2 + 1 $ >$ [q,r] = deconv(fliplr(p1), fliplr(p2)); % compute quotient and remainder $ >$ q = fliplr(q); r = fliplr(r); % fliplr here and above is because matlab's $ >$ % poly rep is left-to-right instead of $ >$ % left-to-right $ >$ q % should be [5 -1 2], the canonical rep. of 2 x^2 - 1 x + 5 $ >$ r % should be (something like) [4 -6], the canonical rep. of -6 x + 4 $ (c) Briefly explain why E5.1 and E8.1 and their solutions did or did not help. E5.1 and its solution should have helped by: + teaching you how to use the online submission system if you didn't do E4 + reinforcing the definition of *canonical* + showing you some good test cases with which to test your functions + giving an example of how to write a Matlab function, including style + showing you the basic idea of how to do $addpoly$ + pointing out two things you need to worry about: + polynomials of different degrees (coefficient vectors of different length) + making the answer canonical (delete trailing zeros from the vector) E8.1 and its solution should have helped by: + making sure you had already started at that late date + showing you correct solutions for $makepoly$ and $addpoly$: + show you what the input to $makepoly$ looks like (a vector of coefficients, not something like $'2*x^2-3'$) + allowing you to compare answers from your code to the solution -- mistakes uncovered that way might point to mistakes in your other functions