[ann] symbol solver.. early experiments

[Simon Strandgaard]

Hi,

I have been writing some code that can differentiate expressions.
for instance: x^3 -> 3*x^2.


Here is the code:
http://rubyforge.org/cgi-bin/viewcv...ot=prime&content-type=text/vnd.viewcvs-markup


Still some unsolved issues:
1. reduce 2x+2x into 4x.. is not implemented.
2. sin/cos/tan is not implemented.
3. complex numbers is not used in this implementation.


However code is simple.. and somebody may find usage of it.
Im open for suggestions. Patches are welcome.

Open Questions:
1. What direction should this evolve?
2. Any ideas how to reduce 2x + 2x into 4x ?
3. Is this correct math?

 

[Brian Mitchell]

I have been writing some code that can differentiate expressions.

for instance: x^3 -> 3*x^2.

Here is the code:
http://rubyforge.org/cgi-bin/viewcv...ot=prime&content-type=text/vnd.viewcvs-markup

I like how short it is. Quite amazing what ruby can accomplish.

Still some unsolved issues:
1. reduce 2x+2x into 4x.. is not implemented.
2. sin/cos/tan is not implemented.
3. complex numbers is not used in this implementation.

You would need to be able to compair degree if you want to reduce 2x +
2x --> 4x. 2 + 2 --> 4 could be looked at like 2x^0 + 2x^0 --> 4x^0.
Like wise this would be usefull ffor this: 2xy^2 * 3y. 3y = 3 * x^0 *
y^1 in this case.

Brian Mitchell.

 

[Simon Strandgaard]

I like how short it is. Quite amazing what ruby can accomplish.

Thanks.. Yes.. Ruby is energy.

Im interested in further improvements.. write more code with less.

You would need to be able to compair degree if you want to reduce 2x +
2x --> 4x. 2 + 2 --> 4 could be looked at like 2x^0 + 2x^0 --> 4x^0.
Like wise this would be usefull ffor this: 2xy^2 * 3y. 3y = 3 * x^0 *
y^1 in this case.

Any ideas how this would look like in code?

 

[Josef 'Jupp' Schugt]

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>

 

[Brian Schröder]

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

 

[Mauricio Fernández]

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. (inverse)?

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?

If you look at it closely, you'll see that polynomial multiplication is
but a convolution... hence the standard FFT procedure. To the extent
that the polynomial multiplication is a convolution, most of the signal
processing done in the real world is a good example of the above

And is it numerically stable, or would you prefer the method above?

There are many ways to do the FFT *g*
I found the following in a quick google search:
http://www.math.uni-luebeck.de/workers/potts/paper/stabfinal.pdf

Note that the 'obvious' algo will be faster unless the degree of your
polynomials is high enough...

 

[Brian Schröder]

If you look at it closely, you'll see that polynomial multiplication is
but a convolution... hence the standard FFT procedure. To the extent
that the polynomial multiplication is a convolution, most of the signal
processing done in the real world is a good example of the above


There are many ways to do the FFT *g*
I found the following in a quick google search:
http://www.math.uni-luebeck.de/workers/potts/paper/stabfinal.pdf

Note that the 'obvious' algo will be faster unless the degree of your
polynomials is high enough...

Thanks for answering this. Now that you explain it, it becomes clear. They should have motivated it in class like that, because I'm shure 90% of my colleges have no idea for how many usefull things you need the FFT.

regards,

Brian

 

[Dave Baldwin]

The rb_create_new_instance function is described in Pickaxe 2, but when
I use it in an extension the linker cannot resolve it. Grepping
through the source code (1.8.1) doesn't find it either.

The extension is used to accelerate part of class written in ruby and I
am trying to return an instance of the same class.
Any ideas what I am doing wrong, or an alternative way of creating a
new instance of a ruby defined class from C?

Thanks,

Dave.

 

[ts]

D> The rb_create_new_instance function is described in Pickaxe 2,
^^^^^^^^^^^^^^^^^^^^^^
rb_class_new_instance


Guy Decoux

 

[Dave Thomas]

The rb_create_new_instance function is described in Pickaxe 2, but
when I use it in an extension the linker cannot resolve it. Grepping
through the source code (1.8.1) doesn't find it either.

Aarrgh - the example code uses rb_class_new_instance, but it looks like
I missed the update in the table of methods. I'll add it to the errata.


Cheers

Dave

 

[Simon Strandgaard]

On Tuesday 09 November 2004 23:13, Josef 'Jupp' Schugt wrote:
[snip]

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

[snip diff, mul]

An array per variable, maybe something ala

{
:x = [4, 3, 2],
:y = [9, 6]
}

That should deal with most polynomias.

At the moment I have represented polynomias.. as an ast.
x^4+x^3+x^2+y^9+y^6
would in ast form.. be:

add(add(add(add(
exp(mul(4, log(x))),
exp(mul(3, log(x)))),
exp(mul(2, log(x)))),
exp(mul(9, log(y)))),
exp(mul(6, log(y))))

maybe I should make a Polynomium class?
so it would become

add(poly(4,3,2), poly(9,6))

(I had not thought about a polynomium class)

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.

Thanks.