## digitalmars.D - Rationals Lib?

- dsimcha <dsimcha yahoo.com> Oct 10 2009
- bearophile <bearophileHUGS lycos.com> Oct 10 2009
- language_fan <foo bar.com.invalid> Oct 10 2009
- dsimcha <dsimcha yahoo.com> Oct 10 2009
- Rainer Deyke <rainerd eldwood.com> Oct 10 2009
- dsimcha <dsimcha yahoo.com> Oct 10 2009
- dsimcha <dsimcha yahoo.com> Oct 10 2009
- language_fan <foo bar.com.invalid> Oct 10 2009
- Don <nospam nospam.com> Oct 12 2009

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

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

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

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 articleSat, 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

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

== Quote from language_fan (foo bar.com.invalid)'s articleSat, 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

== Quote from dsimcha (dsimcha yahoo.com)'s article== Quote from language_fan (foo bar.com.invalid)'s articleSat, 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

Sat, 10 Oct 2009 21:29:41 +0000, dsimcha thusly wrote:

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

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