velnias75 / rational

A C++ rational (fraction) template class

rational

A C++ rational (fraction) template class

Include rational.h to be able to do fraction calculations. By simply including rational.h and specifying the storage type (any integer variant) you can create and use a fractional data type. For example, Rational<long> foo(3, 4) would create a fraction named foo with a value of 3/4, and store the fraction using the long data type.

Simple to use, fast, and modifiable for your needs, because its all in the one header file rational.h at your access. It includes all basic mathematical operations as well as comparison operators, and is very flexible. If you would like to see a feature implemented, just ask here.

The storage type should represent all integers within some (possibly infinite) interval including 0 and 1. For example, the native signed or unsigned int and long types, or arbitrary-precision integers, may be used. Beyond ordinary integers, you should also be able to use any other Euclidean domain, perhaps not even an ordered ring, but support for such types is experimental and has not been thoroughly tested. In fact, you should be able to use any integral domain, but you may need to apply a more sophisticated GCD algorithm; you can fall back to GCD_null if overflow is not a concern in practice. Finally, using non-integral domains is very likely to fail.

Features

• exchangeable GCD algorithms [GCD_euclid_fast (default), GCD_euclidand GCD_stein, choose as second template parameter, i. e. Rational<long, GCD_stein> foo(3, 4) for Stein]

• optional signed overflow/unsigned wrap checking by throwing an std::domain_error exception (i.e. Rational<storage_type, GCD_algo, Commons::Math::ENABLE_OVERFLOW_CHECK>, default is no checking: Commons::Math::NO_OVERFLOW_CHECK)

• optimized for signed and unsigned types

• additional operators:

  • mod to split inproper fractions in integer and fraction part
  • abs to get the absolute value
  • % (modulo) for rational modulo
  • increment (++x & x++) and decrement (--x & x--)
  • unary plusand minus

• Construction of inproper (mixed) fractions, i.e. Rational<long> foo(2, 3, 4)for 2 3/4 resp. 2.75

• Construction of approximate fractions, i.e. Rational<long> foo(3.14159265358979323846)for π resp. 245850922/78256779 (approximation is dependent on compiler and chosen storage type)

• Support for

  • the GNU Multiple Precision Arithmetic Library (include gmp_rational.h)
  • CLN - Class Library for Numbers (include cln_rational.h)

  as underlying storage type

• Expression templates for domain specific programming (include expr_rational.h)

• Construction of fractions from expression strings (i.e. Rational<long> expr("(11/2) * +(4.25+3.75)"))

• Construction of fractions from continued fractions (from container of integer types)

• Extraction of continued fractions sequences from a fraction

• Construction of fractions from repeating decimals (i.e. 0.16666... => 1/6)

Notes for custom number types

rational.h depends on following specialized fields of std::numeric_limits<custom_type>

• std::numeric_limits<custom_type>::is_signed
• std::numeric_limits<custom_type>::is_integer
• std::numeric_limits<custom_type>::is_exact

(gmp_rational.h provides this specializations for GMP versions below 5.1)

How to use

See the test cases for examples on how to use rational.h with C++ built-in types as well as with the GNU Multiple Precision Arithmetic Library or the CLN - Class Library for Numbers as underlying storage type.

• The header gmp_rational.h contains specializations especially for the GNU Multiple Precision Arithmetic Library as underlying storage type.

  If you use the GMP extensions, you'll need to link your application with -lgmpxx -lgmp

• The header cln_rational.h contains specializations especially for the CLN - Class Library for Numbers as underlying storage type.

  If you use the CLN extensions, you'll need to link your application with -lcln

rational's Issues

support for Gaussian integers

By Melchoir via Reddit

A Gaussian integer is a complex number where the real and imaginary parts are both integers. In other words, a thing of the form a+bi where a and b are integers. I think it can even be implemented as std::complex. Some salient points are:

• The Euclidean algorithm works on Gaussian integers.
• There is a modulus operator and a norm function.
• There is no natural ordering! If one implements a Gaussian integer class in C++, one might define somewhat arbitrary operators <, >, etc. so that standard sorting-based algorithms work, but those operators shouldn't be used to implement the Euclidean algorithm.
  A ratio of two Gaussian integers is called a Gaussian rational. It has the form (a+bi)/(c+di). Mathematically, this is the same as ((a+bi)(c-di))(c2+d2), so you can also think of a Gaussian rational as a ratio of a Gaussian integer over an ordinary integer. For example, (1+0i)/(1+1i) is equal to (1-1i)/2. In that sense, it only takes three integers to specify a Gaussian rational. It might seem wasteful to use four integers. However, it will frequently happen that some (a+bi)/(c+di) is representable using a given storage type, while ((a+bi)(c-di))(c2+d2) overflows in the numerator and/or the denominator.

Gaussian integers and Gaussian rationals are both interesting types. It would be nice if one could define a Gaussian integer type and, with a little extra effort, get the rational type by applying your template to it. In the terminology of pure mathematics, your template implements a field of fractions, which is meaningful for any integral domain, including the ordinary integers.

I understand the point about designing the template for completeness. My point is that as a potential user of the library, I would be worried that, for example, the implementation of Rational::operator+= secretly performs some normalization that depends on the existence of T::operator<. This information is impossible to get just from reading the code, and I would dread having to test it out myself, only to pull my hair out deciphering the compiler's error messages. Even if it compiles, I would be worried that it makes some assumption about the behavior of the < operator that is violated by my storage type, and the compiler wouldn't even be able to detect that. This might very well be the case for the Gaussian integers, which I would count as an "exotic" storage type.

Eh... I would try adding support for Gaussian integers myself, but it feels like it might be a lot of work. :)

Remarks of Melchoir via Reddit

From Reddit:

Very cool!

For documentation: It would be good to describe more explicitly the range of storage types that are expected to work. Can I use polynomials and get rational functions? Can I use Gaussian integers and get Gaussian rationals? Ideally, T would not need to have comparison methods as long as I never reference Rational's comparison methods, but maybe they're needed internally for other purposes.

If the above are meant to be supported, it would be good to see a couple of test cases, too. Hopefully, the exotic storage types wouldn't have to be fully fleshed out if they're just for testing.

Also for test cases: Make sure you've handled the most negative value M of a signed binary integer type, since -M = M, which might cause trouble in lots of places.

Back to docs, it would be good to describe what it means to support GMP. What does one gain by using a Rational of GMP integers, rather than a native GMP rational?

On the implementation side, I don't think you need to declare your own [copy, move] [constructor, assignment operator]s or destructor. It looks like your implementations aren't doing anything special.