Exact (LISP-ish) calculations in Ruby?
Aldric Giacomoni
on a LISP REPL, or when using your average HP scientific calculator?
>> 3 / 4
=> 3/4
>> 3 / 6
=> 1/2
>> sqrt(2)
=> sqrt(2)
>> sqrt(4)
>> 2
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 :)
--
Posted via http://www.ruby-forum.com/.
Aaron Patterson
How about the Rational class in stdlib?
http://ruby-doc.org/stdlib/libdoc/rational/rdoc/index.html
--
Aaron Patterson
http://tenderlovemaking.com/
Marnen Laibow-Koser
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
http://www.marnen.org
mar...@marnen.org
David Masover
> 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?
>
> >> 3 / 4
>
> => 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.
Aldric Giacomoni
>
> 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.
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
>
> 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..
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.
Ken Bloom
> Aldric Giacomoni wrote:
>> 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?
>>>> 3 / 4
>> => 3/4
>>>> 3 / 6
>> => 1/2
>>>> sqrt(2)
>> => sqrt(2)
>>>> sqrt(4)
>>>> 2
>>
>> 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 :)
>
> 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.
>
Umm, there's a standard library for wiring in Rational:
require 'mathn'
--
Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/
Marnen Laibow-Koser
[...]
>> 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.
>>
>
> Umm, there's a standard library for wiring in Rational:
>
> require 'mathn'
Great! I didn't know about that.
Gavin Sinclair
>
> Umm, there's a standard library for wiring in Rational:
>
> require 'mathn'
You've gotta love this...
$ irb
>> require 'mathn'
=> true
>> 3/4
=> 34
(It's just a printing "error".)
>> _.to_f
=> 0.75
That's Ruby 1.8.7.
--
Gavin Sinclair
Gavin Sinclair
> Aldric Giacomoni wrote:
>
> > 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..
>
> 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) ... ?
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
Gavin Sinclair
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(2) * sqrt(3)
--> sqrt(6)
> sqrt(8)
--> 2 * sqrt(2)
> 2 * PI * 3.5
--> 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
Martin DeMello
>
> 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.
I learnt it in school, and I'm in my 30s, so one generation ago.
martin
Florian Frank
> 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.
>
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
>> ContinuedFraction.for_a { |n| n == 0 ? 1 : 2 }[]
# => 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
>> atan[1]
# => 0.785398163397448
Now, it's easy to approximate pi as well:
pi = lambda { 4 * atan[1] }
>> pi[]
# => 3.14159265358979
As you can imagine I had a lot of fun playing with them. ;)
--
Florian Frank
Aldric Giacomoni
> 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, 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? :)
Florian Frank wrote:
>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
Wow, massive amount of work you did there. Pretty cool coding, too. I
may just have to shamelessly steal some of these :)
Marnen Laibow-Koser
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.
>
> martin
Best,
--
Marnen Laibow-Koser
http://www.marnen.org
mar...@marnen.org
Florian Frank
> Florian Frank wrote:
>
>> 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
>>
>
> Wow, massive amount of work you did there. Pretty cool coding, too. I
> may just have to shamelessly steal some of these :)
>
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
David Masover
> 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) 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.
Gavin Sinclair
>
> > 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)
> for any function for which you can calculate function
> values and derivatives.
> 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.
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
David Masover
> On Nov 20, 5:11 pm, David Masover <ni...@slaphack.com> 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.
Aldric Giacomoni
> 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))
> But really, I've done this as a learning exercise. As a tool, I'd still
> probably use Maxima.
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).
Martin DeMello
> 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).
A ruby bridge to an existing CAS project would probably be the best way to go.
martin
Gavin Sinclair
>
> If anyone actually wants this code, I'll throw it on github.
Yes please!
> The main reason I haven't is that I've got to be reinventing like
> five wheels here.
Er... seen the number of testing frameworks lately? ;)
> But really, I've done this as a learning exercise. As a tool, I'd still
> probably use Maxima.
Indeed. I'd only be interested in it as a learning exercise, so no
rush.
Cheers,
Gavin
David Masover
> On Nov 20, 7:11 pm, David Masover <ni...@slaphack.com> wrote:
> > If anyone actually wants this code, I'll throw it on github.
>
> Yes please!
Done:
http://github.com/masover/math
Unfortunately, github stopped doing gems, and I'm not up on this gemcutter
stuff. (Get off my lawn!) I'm also not nearly confident enough in my choice of a
name to publish anything. It's probably most useful if you look at HEAD^,
where I had everything set up with relative requires, instead of a gem.
> > The main reason I haven't is that I've got to be reinventing like
> > five wheels here.
>
> Er... seen the number of testing frameworks lately? ;)
Most of them at least have a legitimate reason for being -- something they
claim to do better than the existing frameworks.
I simply have no clue about any existing Ruby implementations of this.
I'm also somewhat ashamed at the quality of this code. Not a test to be found!
How can I call myself a Rubyist? My only excuse for this is that I've been
using it so much interactively that it's all probably pretty well tested. But
since I have no tests/specs and no documentation, good luck...
Gavin Sinclair
> > > If anyone actually wants this code, I'll throw it on github.
>
> > Yes please!
>
> Done:
>
> http://github.com/masover/math
Thank you!
Aldric Giacomoni
> On Friday 20 November 2009 05:10:45 pm Gavin Sinclair wrote:
>> On Nov 20, 7:11 pm, David Masover <ni...@slaphack.com> wrote:
>> > If anyone actually wants this code, I'll throw it on github.
>>
>> Yes please!
>
> Done:
>
> http://github.com/masover/math
>
I second that. Thanks :)