Exact (LISP-ish) calculations in Ruby?

Discussion in 'Ruby' started by Aldric Giacomoni, Nov 18, 2009.

1. Aldric GiacomoniGuest

Has anyone written a gem for exact calculations? The kind one would find
on a LISP REPL, or when using your average HP scientific calculator?
I couldn't find anything on gemcutter or rubyforge, but maybe I missed
it..
I don't ask because I need it.. I ask because of an idealistic desire
for exact calculations

Aldric Giacomoni, Nov 18, 2009

2. Aaron PattersonGuest

How about the Rational class in stdlib?

http://ruby-doc.org/stdlib/libdoc/rational/rdoc/index.html

Aaron Patterson, Nov 18, 2009

3. Marnen Laibow-KoserGuest

Wiring Rational into Numeric#/ shouldn't be too hard. I'm not sure how
to deal with square roots without lots of special cases, however.

Best,

Marnen Laibow-Koser, Nov 18, 2009
4. David MasoverGuest

This much is available through the Rational object:

irb(main):001:0> Rational 3,4
=> (3/4)
irb(main):002:0> Rational(3) / 4
=> (3/4)
irb(main):003:0> Rational(3) / 4 / 12
=> (1/16)

I'm not sure about the rest of it, though it makes me wish I'd used Lisp for a
recent project. I pretty much had to invent a symbolic equation manipulation
class -- though, to be fair, I didn't look that hard for an existing one.

David Masover, Nov 18, 2009
5. Aldric GiacomoniGuest

In all fairness, I just fired up SLIME to check, and LISP's (sqrt 2)
does come out to be an approximation, so I guess I want something cool
like the HP-48 and HP-49's factoring power..

Aldric Giacomoni, Nov 18, 2009
6. Aldric GiacomoniGuest

And I just read up on the process of 'continuing fractions' which can be
used find fractions / estimates of irrational numbers down to the nth
decimal. I wonder how we can know that, for instance, 1.41421 (etc) is
sqrt(2) ... ?

Ah, mathematics.

Aldric Giacomoni, Nov 18, 2009
7. Ken BloomGuest

Umm, there's a standard library for wiring in Rational:

require 'mathn'

Ken Bloom, Nov 19, 2009
8. Marnen Laibow-KoserGuest

Ken Bloom wrote:
[...]
Great! I didn't know about that.

Best,

Marnen Laibow-Koser, Nov 19, 2009
9. Gavin SinclairGuest

You've gotta love this...

\$ irb=> 34

(It's just a printing "error".)
=> 0.75

That's Ruby 1.8.7.

Gavin Sinclair, Nov 19, 2009
10. Gavin SinclairGuest

There's an algorithm for calculating square roots, similar (in
appearance, not in process) to the algorithm for long division. One
or more generations ago, school students would have done it with pen
and paper, I think.

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.

Thirdly, you can estimate any root you like by trial multiplication!
(Exercise: write a Ruby program to do this; shouldn't take more than
10 lines.)

Gavin Sinclair, Nov 19, 2009
11. Gavin SinclairGuest

That "idealistic desire" would only be needed in very special cases in
real programming, so it's not surprising not to find a Ruby library
for it.

Essentially, you're looking for the capabilities provided by a
Computer Algebra System (CAS) like Mathematica, as mentioned, or
Maxima (open source, IIRC). You may be able to find an open source
CAS that has Ruby bindings, or for which (if you're sufficiently
motivated) you can write some bindings.

Or you can give it a go!
--> sqrt(6)
--> 2 * sqrt(2)
--> 7 * PI

Not my idea of fun, though. The beauty of Mathematics is best
appreciated in the mind, for it's only there that sqrt(2) exists.

Gavin Sinclair, Nov 19, 2009
12. Martin DeMelloGuest

I learnt it in school, and I'm in my 30s, so one generation ago.

martin

Martin DeMello, Nov 19, 2009
13. Florian FrankGuest

I had to implement them for my bullshit library (which has grown to
include half a math library by now, ugh):

http://github.com/flori/bullshit/blob/master/lib/bullshit.rb#L20

require 'bullshit' # pardon my french
include Bullshit
# => 1.4142135623731

They are rather fascinating. They can be used to implement functions as
well, here's the atan function:

atan = ContinuedFraction.for_a do |n, x|
n == 0 ? 0 : 2 * n - 1
end.for_b do |n, x|
n <= 1 ? x : ((n - 1) * x) ** 2
end
# => 0.785398163397448

Now, it's easy to approximate pi as well:

pi = lambda { 4 * atan[1] }
# => 3.14159265358979

As you can imagine I had a lot of fun playing with them.

Florian Frank, Nov 19, 2009
14. Aldric GiacomoniGuest

Gavin, I'll take a look at existing CAS This being said, I rather
think that the ability to use mental concepts without worrying that the
computer will change them is rather important (I -said- sqrt(2), not
1.414 !) .. And, well, if Ruby can do it, then it should be available
for those who do need it, don't you think?

Wow, massive amount of work you did there. Pretty cool coding, too. I
may just have to shamelessly steal some of these

Aldric Giacomoni, Nov 19, 2009
15. Marnen Laibow-KoserGuest

Yeah, I learned it as a kid as well, and I'm about the same age. I've
long since forgotten how to do it, though; I do remember that it
involves a bit of trial multiplication.

Best,

Marnen Laibow-Koser, Nov 19, 2009
16. Florian FrankGuest

Oh, thanks. I have considered pulling some of the math stuff out of the
library and putting it in an extra gem. There are some algorithms in
there, that could benefit from being being transformed into a c
extension as well. On the other hand I was pretty surprised how well
Ruby did on the numerical stuff and also how much better Ruby 1.9 was on
the algorithms that iterate a lot.

Florian Frank, Nov 19, 2009
17. David MasoverGuest

Newton's Method, according to at least one Calculus textbook, is a way of
finding roots (zeros) for any function for which you can calculate function
values and derivatives. The example given is taking the cube root of seven, by
rewriting the problem as:

x^3 - 7 = 0

The derivative of which is easy to calculate as 3x^2.

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.

But I guess if what you wanted was something that knows how to do algebraic
manipulation, without losing accuracy until you tell it to give you a float,
there's always Maxima.

David Masover, Nov 20, 2009
18. Gavin SinclairGuest

_estimating_ roots (to any desired accuracy)
Interesting. 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.

Gavin Sinclair, Nov 20, 2009
19. David MasoverGuest

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 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.

The following actually works:

irb(main):004:0> (Ex)**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.

David Masover, Nov 20, 2009
20. Aldric GiacomoniGuest

Everyone's talking about Maxima, which was written in LISP.. Interesting

I'd like to modify the earlier question then, and wonder if Ruby is the
right tool for the job, or if one should simply just go with LISP (in
which case, there's no reinventing the wheel, I'd just use Maxima). If
Ruby can be the right tool for the job.. Is it worth it?

I do think it would be pretty cool to have a CAS like Maxima in Ruby
(there is in fact a rubyforge project to develop one, but it hasn't
released any files at all yet).

Aldric Giacomoni, Nov 20, 2009