From: Josef 'Jupp' Schugt Date: 2004-11-10T07:13:13+09:00 Subject: Re: [ann] symbol solver.. early experiments 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 -- Messages larger than 100 KiB will be discarded *without* notification! http://oss.erdfunkstelle.de/ruby/ German ed. of comp.lang.ruby FAQ ---------------------------------------------------------------------- Body bag: rucksack. Leichensack: Body bag. -- Bin D-Strich, translator