On Friday 20 November 2009 12:45:39 am Gavin S. wrote:

On Nov 20, 5:11 pm, David M. [email protected] wrote:

Furthermore, there’s a Calculus-based algorithm (Newton’s method, it’s

called in my syllabus, but I think it’s properly called the Newton-

Raphson method) for calculating square/cube/fourth/… roots to any

desired accuracy.

Newton’s Method, according to at least one Calculus textbook, is a way of

finding roots (zeros)

*estimating* roots (to any desired accuracy)

Good point – though, technically, unless it fails utterly (which it

sometimes

does), you can find the *exact* root, given infinite time to calculate

it

I wrote a program to do Newton’s Method. It’s one of the few times I

wished I was using Lisp instead of Ruby, as I had no easy way of taking

apart a block as source code to find its derivative. Instead, whenever I

apply it, I have to take the derivative manually, or feed it through

Maxima.

I’d be curious to see Lisp and Ruby approaches to

representing and differentiating functions. Polynomials would be

trivial in Ruby if you build an appropriate representation, but

general functions? Leave that to the experts, I guess.

I don’t think I’d have problems differentiating most *mathematical*

expressions, given an appropriate description. I could pretty much just

copy

techniques out of the book – chain rule, product rule, etc. That said,

math

has been around for thousands of years, and I’m sure there’s something I

haven’t thought of, or even learned yet.

But yes, polynomials are definitely where it’s easy – I wrote something

to

integrate arbitrary polynomials. In order to do this, I had to write a

fairly

messy library for handling mathematical expressions. I’m thinking I

could

probably go back over it and clean up the object model, at least.

The main reason this would be easier in Lisp is that rather than

building said

messy object model to hold the expressions, I’d just work with sexps.

Macros

would let me actually do something like this:

(differentiate (- (expt x 3) 7))

If we could do the equivalent in Ruby, it’d look like this:

Math.differentiate {|x| x**3 - 7}

That’s kind of gross to implement, though. Pure does it by discarding

the

block, finding the original source, and re-parsing it, using whatever

parse

tool is available, to get the actual parse tree.

I decided to start with the object model, and try to add a DSL later.

The following actually works:

irb(main):004:0> (E(:x)**3 - 7).integrate :x

=> ((x^4/4)+((-7)*x))

Again, only with polynomials. The first big challenge here was to get it

into a

reasonable representation. The second was working with that

representation,

while retaining some sanity.

But you can see where I’m blatantly cheating above. It could be made

easier to

work with by messing with Symbol, but it still has the fatal flaw that

I’m

faking it – you’re still not actually typing in an expression, you’re

typing

a recipe for constructing an Expression object tree, whereas in Lisp,

your

sexp would already be the tree I’m looking for.

And the motivation? Numeric integration using a lagrange polynomial.

Only for

fun – this is too obvious an idea not to have been tried already. Once

I have

my algebraic-manipulation-and-integration library, it’s about 30 lines

of code

to integrate an arbitrary set of points with this method.

If anyone actually wants this code, I’ll throw it on github. The main

reason I

haven’t is that I’ve got to be reinventing like five wheels here. Plus,

it

could use some cleaning up – I haven’t really made an effort to unify

my

Function library (which does things like Newton’s method, Simpson’s

rule, etc)

with my Expression library (which does the above hackery).

But really, I’ve done this as a learning exercise. As a tool, I’d still

probably use Maxima.