www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Rationals Lib?

reply dsimcha <dsimcha yahoo.com> writes:
I've written a prototype lib that does arithmetic on rational numbers
(fractions).  I got the idea from the Maxima computer algebra system.  (
http://maxima.sourceforge.net ). It's templated to work on any integer type
where operators are properly overloaded, though in practice you'd probably
want to use something arbitrary precision, since adding/subtracting fractions
can yield some really really big numbers for numerators and denominators, and
if you don't care that much about accuracy, floats are faster anyhow.

I'm still cleaning things up, etc, but usage is something like this:

import std.bigint, fractions;

void main() {
    auto f1 = fraction( BigInt("314159265"), BigInt("27182818"));
    auto f2 = fraction( BigInt("8675309"), BigInt("362436"));
    f1 += f2;
    assert(f1 == fraction( BigInt("174840986505151"),
        BigInt("4926015912324")));

    // Print result.  Prints:
    // "174840986505151 / 4926015912324"
    writeln(f1);

    // Print result in decimal form.  Prints:
    // "35.4934"
    writeln(cast(real) result);
}

Some questions for the community:

1.  Does this look useful to anyone?
2.  What might be some non-obvious key features for a lib like this?
3.  What is the status of arbitrary precision integer arithmetic in D2?  Will
we be getting something better than std.bigint in the foreseeable future?
This lib isn't very useful without a fast BigInt underneath it.
4.  There is one small part (conversion to float) where I had to assume that
the BigInt implementation was the one in std.bigint, to cast certain division
results back to native types.  Will there eventually be a de facto standard
way to cast BigInts to native types so I can get rid of this dependency?
5.  Is there any use for approximate rational arithmetic built on
machine-sized integers?  For example, if adding two fractions would generate
an overflow, try to find the closest answer that wouldn't?  I would guess that
if you want to do something like this, you're better off just using floats,
but I could be wrong.
Oct 10 2009
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
dsimcha:

     auto f1 = fraction( BigInt("314159265"), BigInt("27182818"));

That's a nice example where bigint literals are useful. Missing bigint literals, this looks shorter than your way to define f1: auto f1 = fraction("314159265 / 27182818"); Or a little better, if/when structs can be assigned statically: fraction f1 = q{314159265 / 27182818}; Bye, bearophile
Oct 10 2009
next sibling parent reply language_fan <foo bar.com.invalid> writes:
Sat, 10 Oct 2009 14:25:28 -0400, bearophile thusly wrote:

 dsimcha:
 
     auto f1 = fraction( BigInt("314159265"), BigInt("27182818"));

That's a nice example where bigint literals are useful. Missing bigint literals, this looks shorter than your way to define f1: auto f1 = fraction("314159265 / 27182818"); Or a little better, if/when structs can be assigned statically: fraction f1 = q{314159265 / 27182818};

FWIW, he could have just redefined the / operator in class bigint: bigint(1) / 3 Or bigint f; f = 1 f /= 3; Can't really remember how overloading the assignment works in D.
Oct 10 2009
parent reply dsimcha <dsimcha yahoo.com> writes:
I guess I could have implemented some of these suggestions, but the idea was for
this lib to be very simple (it's only about 300 lines of code so far) and
agnostic
to the implementation of the integers it's working on top of, with the caveat
that, if you use something that's not arbitrary precision, the onus is on you to
make sure nothing overflows.  If anyone, for example, made a wrapper to the GNU
multiprecision lib that looked like a D struct w/ operator overloading, it would
be able to plug right into this library.  If std.bigint improves, this library
will automatically benefit.

== Quote from language_fan (foo bar.com.invalid)'s article
 Sat, 10 Oct 2009 14:25:28 -0400, bearophile thusly wrote:
 dsimcha:

     auto f1 = fraction( BigInt("314159265"), BigInt("27182818"));

That's a nice example where bigint literals are useful. Missing bigint literals, this looks shorter than your way to define f1: auto f1 = fraction("314159265 / 27182818"); Or a little better, if/when structs can be assigned statically: fraction f1 = q{314159265 / 27182818};

bigint(1) / 3 Or bigint f; f = 1 f /= 3; Can't really remember how overloading the assignment works in D.

Oct 10 2009
next sibling parent Rainer Deyke <rainerd eldwood.com> writes:
dsimcha wrote:
 I guess I could have implemented some of these suggestions, but the idea was
for
 this lib to be very simple (it's only about 300 lines of code so far) and
agnostic
 to the implementation of the integers it's working on top of, with the caveat
 that, if you use something that's not arbitrary precision, the onus is on you
to
 make sure nothing overflows.  If anyone, for example, made a wrapper to the GNU
 multiprecision lib that looked like a D struct w/ operator overloading, it
would
 be able to plug right into this library.  If std.bigint improves, this library
 will automatically benefit.

FWIW I use boost::rational quite a bit, and I've never felt the need to use bigints. -- Rainer Deyke - rainerd eldwood.com
Oct 10 2009
prev sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from language_fan (foo bar.com.invalid)'s article
 Sat, 10 Oct 2009 21:29:41 +0000, dsimcha thusly wrote:
 I guess I could have implemented some of these suggestions, but the idea
 was for this lib to be very simple (it's only about 300 lines of code so
 far) and agnostic to the implementation of the integers it's working on
 top of, with the caveat that, if you use something that's not arbitrary
 precision, the onus is on you to make sure nothing overflows.  If
 anyone, for example, made a wrapper to the GNU multiprecision lib that
 looked like a D struct w/ operator overloading, it would be able to plug
 right into this library.  If std.bigint improves, this library will
 automatically benefit.

does it allow implementing a rational library on top of any (arbitrary precision) number type, assuming we have a sane interface to work with.

Save for a few small details, yes. Since there seems to be interest I'll clean up the code and post it somewhere in the next few days. Here are the "few details": 1. To convert to floating-point form, I need to be able to cast the underlying arbitrary precision integers to machine-native types. There's no standard way to do this. 2. I need a standard way of constructing any type of integer, whether machine-native or arbitrary precision, to implement some syntactic sugar features. Let's say you wanted the number 314 as a rational, with a std.bigint.BigInt as the underlying integer. Right now you'd have to do: auto foo = fraction( BigInt(314), BigInt(1)); There's no shortcut yet for when you want a whole number to be represented internally as a fraction because there's no standard way to construct any arbitrary integer type with the value 1. The same problem applies to conversion from floating-point to rational and comparison between rational and integer.
Oct 10 2009
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from dsimcha (dsimcha yahoo.com)'s article
 == Quote from language_fan (foo bar.com.invalid)'s article
 Sat, 10 Oct 2009 21:29:41 +0000, dsimcha thusly wrote:
 I guess I could have implemented some of these suggestions, but the idea
 was for this lib to be very simple (it's only about 300 lines of code so
 far) and agnostic to the implementation of the integers it's working on
 top of, with the caveat that, if you use something that's not arbitrary
 precision, the onus is on you to make sure nothing overflows.  If
 anyone, for example, made a wrapper to the GNU multiprecision lib that
 looked like a D struct w/ operator overloading, it would be able to plug
 right into this library.  If std.bigint improves, this library will
 automatically benefit.

does it allow implementing a rational library on top of any (arbitrary precision) number type, assuming we have a sane interface to work with.

the code and post it somewhere in the next few days. Here are the "few details": 1. To convert to floating-point form, I need to be able to cast the underlying arbitrary precision integers to machine-native types. There's no standard way to do this. 2. I need a standard way of constructing any type of integer, whether machine-native or arbitrary precision, to implement some syntactic sugar features. Let's say you wanted the number 314 as a rational, with a std.bigint.BigInt as the underlying integer. Right now you'd have to do: auto foo = fraction( BigInt(314), BigInt(1)); There's no shortcut yet for when you want a whole number to be represented internally as a fraction because there's no standard way to construct any arbitrary integer type with the value 1. The same problem applies to conversion from floating-point to rational and comparison between rational and integer.

Ok, I got it to work. I even found kludges around the issues I raised previously: 1. To convert an arbitrary BigInt to a long, use binary search and equality testing. It's slow, but converting a BigInt fraction to a float is slow anyhow. 2. Just implement completely separate overloads for when one of the operands is an int. See http://dsource.org/projects/scrapple/browser/trunk/rational/rational.d .
Oct 10 2009
prev sibling parent language_fan <foo bar.com.invalid> writes:
Sat, 10 Oct 2009 21:29:41 +0000, dsimcha thusly wrote:

 I guess I could have implemented some of these suggestions, but the idea
 was for this lib to be very simple (it's only about 300 lines of code so
 far) and agnostic to the implementation of the integers it's working on
 top of, with the caveat that, if you use something that's not arbitrary
 precision, the onus is on you to make sure nothing overflows.  If
 anyone, for example, made a wrapper to the GNU multiprecision lib that
 looked like a D struct w/ operator overloading, it would be able to plug
 right into this library.  If std.bigint improves, this library will
 automatically benefit.

Now that's the most perfect way to test the modularity of the language -- does it allow implementing a rational library on top of any (arbitrary precision) number type, assuming we have a sane interface to work with.
Oct 10 2009
prev sibling parent Don <nospam nospam.com> writes:
dsimcha wrote:
 I've written a prototype lib that does arithmetic on rational numbers
 (fractions).  I got the idea from the Maxima computer algebra system.  (
 http://maxima.sourceforge.net ). It's templated to work on any integer type
 where operators are properly overloaded, though in practice you'd probably
 want to use something arbitrary precision, since adding/subtracting fractions
 can yield some really really big numbers for numerators and denominators, and
 if you don't care that much about accuracy, floats are faster anyhow.
 
 I'm still cleaning things up, etc, but usage is something like this:
 
 import std.bigint, fractions;
 
 void main() {
     auto f1 = fraction( BigInt("314159265"), BigInt("27182818"));
     auto f2 = fraction( BigInt("8675309"), BigInt("362436"));
     f1 += f2;
     assert(f1 == fraction( BigInt("174840986505151"),
         BigInt("4926015912324")));
 
     // Print result.  Prints:
     // "174840986505151 / 4926015912324"
     writeln(f1);
 
     // Print result in decimal form.  Prints:
     // "35.4934"
     writeln(cast(real) result);
 }
 
 Some questions for the community:
 
 1.  Does this look useful to anyone?
 2.  What might be some non-obvious key features for a lib like this?

 3.  What is the status of arbitrary precision integer arithmetic in D2?  Will
 we be getting something better than std.bigint in the foreseeable future?
 This lib isn't very useful without a fast BigInt underneath it.

Yes, I will moving Tango BigInt to D2 Phobos. I've been delaying it for ages, hoping there would be a progress on the Phobos/Tango merger. But the Tango folks just don't seem interested in a merger, or even in closing the rift. :-(
 4.  There is one small part (conversion to float) where I had to assume that
 the BigInt implementation was the one in std.bigint, to cast certain division
 results back to native types.  Will there eventually be a de facto standard
 way to cast BigInts to native types so I can get rid of this dependency?

Yes.
 5.  Is there any use for approximate rational arithmetic built on
 machine-sized integers?  For example, if adding two fractions would generate
 an overflow, try to find the closest answer that wouldn't?  I would guess that
 if you want to do something like this, you're better off just using floats,
 but I could be wrong.

I can't think of a use for it.
Oct 12 2009