Exact (LISP-ish) calculations in Ruby?

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

  1. 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
    #1
    1. Advertisements

  2. How about the Rational class in stdlib?

    http://ruby-doc.org/stdlib/libdoc/rational/rdoc/index.html
     
    Aaron Patterson, Nov 18, 2009
    #2
    1. Advertisements

  3. 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
    #3
  4. 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
    #4
  5. 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
    #5
  6. 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
    #6
  7. Aldric Giacomoni

    Ken Bloom Guest

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

    require 'mathn'
     
    Ken Bloom, Nov 19, 2009
    #7
  8. Ken Bloom wrote:
    [...]
    Great! I didn't know about that.


    Best,
     
    Marnen Laibow-Koser, Nov 19, 2009
    #8
  9. 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
    #9
  10. 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
    #10
  11. 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
    #11
  12. I learnt it in school, and I'm in my 30s, so one generation ago.

    martin
     
    Martin DeMello, Nov 19, 2009
    #12
  13. 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
    #13
  14. 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
    #14
  15. 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
    #15
  16. 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
    #16
  17. 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
    #17
  18. _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
    #18
  19. 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 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.
     
    David Masover, Nov 20, 2009
    #19
  20. 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
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.