An optimized polynomial multiplication
Overview
Polynomials in one variable are functions like x^3+16x^2-17 and
x^4+4x^3+16x^2+4x+2. One algorithm often carried out with polynomials
is to multiply them. This is done by taking the sum over all terms ax^i*bx^j
where ax^i occurs in the first and bx^j in the second polynomial.
For example, x^2+1 multiplied with x^3+x^2+8 is x^5+x^4+x^3+9x^2+8 where
the 9x^2 is the sum of two terms x^2*8 and 1*x^2.
Mathematicians have investigated how to multiply polynomials under certain
constraints. One of them is the assumption that multiplications of numbers
are expensive while additions are cheap. This would in particluar be true
for multidigit numbers, where the algorithm for multiplication is quadratic
while the addition algorithm is linear, although here better algorithms
than quadratic ones are known. For this reason, the following homework
has the goal to multiply polynomials p and q such that
- The number of multiplications and divisions is
O(deg(p)+deg(q));
- The overall number of operations is O((deg(p)+deg(q))^4).
The ideal algorithm assumes that all numerical operations are precise,
this is of course not true and therefore this program contains some
rounding at the end.
The implemented algorithm
The idea is the following:
- Let n be the sum of the degrees of the two polynomials p and q.
- Compute p(0),p(1),...,p(n) and q(0),q(1),...,q(n) without
multiplications. In order to achieve this, the following is done
for m=0,1,...,n: p(m) and q(m) are taken as the lowest order terms
of the polynomials and then the polynomials are brought from the
form p[k](x-m)^k+...+p[2](x-m)^2+p[1](x-m)+p[0] into the new form
p[k](x-m-1)^k+...+p[2](x-m-1)^2+p[1](x-m-1)+p[0] where p[l] is the
l-th coeffitient for the corresponding formula (before or after the
transformation). For example, (x-m)^3+2(x-m)+1 would be transformed
into (x-m-1)^3+3(x-m-1)^2+5(x-m-1)+3. As at the beginning the
polynomial is already in the corresponding form for m=0, this works.
All these computations do only need additions and substractions,
but no multiplications and divisions. The number of additions and
substractions is O(n^3).
- Compute r(i)=p(i)*q(i) for i=0,1,...,n. This are n+1 multiplications.
- Compute the coeffitients of r from r(0),r(1),...,r(n). This is done
by adding up terms of the form a*x*(x-1)*...*(x-m) for m=0,1,...,n
such that the sum of the terms for m=0,1,...,k coincides with r
on 0,1,...,k,k+1. The computation of the factor a needs to divide
the difference of the previous sum at k+1 and r(k+1) by 1*2*...*k*(k+1),
thus this loop uses up n divisions for computering the factors 1/1*2*...*m
iteratively and n multiplications for multiplying the above mentioned
differences with these factors. Furthermore, the whole construction
uses O(n^4) additions and substractions.
Task
The task is to complete the existing implementation such that the
above outlined algorithm runs. Tests are carried out automatically
on reloading the page.
- Implement the function xtoxplusone. This needs O(n^2) additions and
substractions but no multiplications. This function transforms
polynomials like x^2+1 to x^2+2x+1 and x^3-8x+1 and x^3+3x^2-5x-6.
The polynomial is in the variable "poly". You can and should change
the members poly[0], poly[1], ... and so on but you should not change
the number of elements. In the case of x^2+1, poly[0] and poly[2]
are 1 and all other values are 0. Search with the editor for the
words "WRITE THIS FUNCTION" to find the place where it is defined.
- Implement the function xtoxminusone. This needs O(n^2) additions and
substractions but no multiplications. This function does exactly
the opposite of the previous one, so it changes x^2+2x+2 to x^2+1
and x^3+3x^2-5x-6 to x^3-8x+1. The variable poly contains the polynomial
in the same way as above. Search with the editor for the words
"WRITE THIS FUNCTION" to find the place where it is defined.
- Adjust the value of the loop marked with "ADJUST HERE" until
it is correct. The current value 3 is incorrect.
- When all three steps done properly, the algorithm should pass all tests.
The algorithm contains two "Math.round" statements. If Java Script
would compute exactly, these would be completely superfluous, but
unfortunately such computations are not available. Test what happens
if the first Math.round statement would be replaced by the plain
statement in the comment below. At the corresponding line, there are
the words "FOR A TEST" in a comment. What does this say about the
quality of the algorithm with respect to tolerating rounding errors?