3

In Cormen's "Introduction to algorithms" is exercise:

"Explain what is wrong with the “obvious” approach to polynomial division using a point-value representation, i.e., dividing the corresponding y values. Discuss separately the case in which the division comes out exactly and the case in which it doesn’t."

Could anybody give me a solution to that exercise? I searched the web but I didn't find solutions/hints. Additionally, I have completely no idea why dividing the corresponding y values is wrong. So, could anybody explain me that? It interests me and it isn't my homework.

Kamil
  • 33

1 Answers1

0

If you are using a point-value representation of polynomials, then if you have something that isn't a polynomial (e.g. because it is a rational function with nonconstant denominator), then it can't possibly be represented correctly.


However, to go beyond the point your book is trying to make, you can do point-value representation of rational functions too. It's been a while since I've done it, but I think if you want to represent all rational functions whose numerator and denominator in lowest terms have degrees less than or equal to $c$ and $d$, then you need $c+d+1$ points.

Note that point value form doesn't give any way to tell the difference between "rational function whose numerator and denominator have degrees $c$ and $d$" and "polynomial of degree $c+d$": you have to decide ahead of time exactly which space of objects you wish to represent by point-value form.

More generally, if you are using a point-value representation with points $a_1, a_2, \ldots, a_n$, then define

$$ m(x) = \prod_{i=1}^n (x - a_i) $$

Then doing arithmetic in point-value representation is really the same thing as doing arithmetic modulo $m(x)$. So anything that can be exactly expressed in terms of arithmetic modulo $m(x)$ can be correctly computed using point-value representation.

There is a version of rational reconstruction that applies to rational functions and polynomials rather than rational numbers and integers.