On Wed, 10 Nov 2004 07:13:13 +0900
Josef 'Jupp' Schugt <jupp / gmx.de> wrote:

> Simon Strandgaard wrote:
> > Any ideas how this [dealing with polynomials by degree] would look 
> > like in code?
> 
> This strongly depends on the way you represent polynomials. To give an 
> example:
> 
> x**3 + 2x**2 + 3x + 4 = 1 * x**3 + 2 * x**2 + 3 * x**1 + 4 * x**0
> 
> can be represented as:
> 
> [4, 3, 2, 1]
> 
> Similarly
> 
> 7 * x**3 + x + 42 = 7 * x**3 + 0 * x**2 + 1 * x**1 + 42 * x**0
> 
> can be represented as:
> 
> [42, 1, 0, 7]
> 
> Adding is then done by list member:
> 
> [4 + 46, 3 + 1, 2 + 0, 1 + 7] = [46, 4, 2, 8]
> 
> which represents
> 
> 8x**3 + 2x**2 + 4x + 46
> 
> Differentiation of polynomials then looks like this
> 
> 10x**5 + 9x**4 + 8x**3 + 7x**2 + 6 x + 5
> 
> or, using array representation:
> 
> [5,6,7,8,9,10]
> 
> Differentiation is overwriting the first element by the second element 
> times the position of the element being overwritten (one in this case) 
> then overwriting the second by the third times the position of the 
> element being overwritten (two in this case), and so on. The last 
> element of the array being differentiated becomes zero and can be removed.
> 
> [6*1,7*2,8*3,9*4,10*5] = [6,14,24,36,50]
> 
> which obviously is the representation of the correct result
> 
> 50x**4 + 36x**3 + 24x**2 + 14x + 6
> 
> Multiplication is also very easy:
> 
> (3x**2 + 2x + 1) * (6x**2 + 5x + 4) = ?
> 
> [1, 2, 3] * [4, 5, 6] =
> [1*4, 1*5 + 2*4, 1*6 + 2*5 + 3*4, 2*6 + 3*5, 3*6] =
> [4, 13, 28, 27, 18]
> 
> Here the product of the two highest degrees of the polynomials yields 
> the highest degree of the resulting polynomial.
> 
> The above looks confusing? It isn't if you write the computation in this 
> way:
> 
> [a0, a1, a2] * [b0, b1, b2] = [c0, c1, c2, c3, c4]
> 
> c0 = a0 * b0
> c1 = a0 * b1 + a1 * b0
> c2 = a0 * b2 + a1 * b1 + a2 * b0
> c3 = a1 * b2 + a2 * b1
> c4 = a2 * b2
> 
> If you take a close look at the indices you see that all ci are the sum 
> of all products of aj and bk where j+k=i. The implementation in Ruby is 
> straightforward.
> 
> Josef 'Jupp' Schugt <jupp(a)gmx(d)de>

Hey, I'm just now preparing for my CS exam and refreshing my algorithm-threorie stuff. There we learned, that polynom product should be done using fft to get (point, value) representations, multiply these, and use fft again to interpolate and get the original results back.

Don't know if this is of any practical relevance, and I always wondered why we took this example for usage of the fft. Does anybody know of any real world usage of polynom multiplication that has to be that fast? And is it numerically stable, or would you prefer the method above?

Regards,

Brian

-- 
Brian Schröäer
http://www.brian-schroeder.de/