• dsimcha (37/37) Oct 10 2009 I've written a prototype lib that does arithmetic on rational numbers
• bearophile (8/9) Oct 10 2009 That's a nice example where bigint literals are useful.
• language_fan (8/18) Oct 10 2009 FWIW, he could have just redefined the / operator in class bigint:
• dsimcha (9/27) Oct 10 2009 I guess I could have implemented some of these suggestions, but the idea...
• Rainer Deyke (5/13) Oct 10 2009 FWIW I use boost::rational quite a bit, and I've never felt the need to
• language_fan (4/13) Oct 10 2009 Now that's the most perfect way to test the modularity of the language -...
• dsimcha (16/29) Oct 10 2009 Save for a few small details, yes. Since there seems to be interest I'l...
• dsimcha (7/36) Oct 10 2009 Ok, I got it to work. I even found kludges around the issues I raised p...
• Don (7/51) Oct 12 2009 Yes, I will moving Tango BigInt to D2 Phobos. I've been delaying it for

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.

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

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.

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};

 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.

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

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.

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.

 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.

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.

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.

 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.

 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.

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 .

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.