From: David Masover Date: 2009-11-20T17:11:18+09:00 Subject: Re: Exact (LISP-ish) calculations in Ruby? On Friday 20 November 2009 12:45:39 am Gavin Sinclair wrote: > On Nov 20, 5:11 pm, David Masover 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 :P > > 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.