diff options
| author | Anas Nashif <anas.nashif@intel.com> | 2012-10-30 12:57:26 -0700 |
|---|---|---|
| committer | Anas Nashif <anas.nashif@intel.com> | 2012-10-30 12:57:26 -0700 |
| commit | 1a78a62555be32868418fe52f8e330c9d0f95d5a (patch) | |
| tree | d3765a80e7d3b9640ec2e930743630cd6b9fce2b /libs/rational | |
| download | boost-1a78a62555be32868418fe52f8e330c9d0f95d5a.tar.gz boost-1a78a62555be32868418fe52f8e330c9d0f95d5a.tar.bz2 boost-1a78a62555be32868418fe52f8e330c9d0f95d5a.zip | |
Imported Upstream version 1.49.0upstream/1.49.0
Diffstat (limited to 'libs/rational')
| -rw-r--r-- | libs/rational/index.html | 46 | ||||
| -rw-r--r-- | libs/rational/rational.html | 680 | ||||
| -rw-r--r-- | libs/rational/test/Jamfile.v2 | 11 | ||||
| -rw-r--r-- | libs/rational/test/rational_example.cpp | 104 | ||||
| -rw-r--r-- | libs/rational/test/rational_test.cpp | 969 |
5 files changed, 1810 insertions, 0 deletions
diff --git a/libs/rational/index.html b/libs/rational/index.html new file mode 100644 index 0000000000..bec1cba03d --- /dev/null +++ b/libs/rational/index.html @@ -0,0 +1,46 @@ +<html> + +<head> +<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> +<title>Boost Rational Number Library</title> +</head> + +<body bgcolor="#FFFFFF" text="#000000"> + +<table border="1" bgcolor="#007F7F" cellpadding="2"> + <tr> + <td bgcolor="#FFFFFF"><img src="../../boost.png" alt="boost.png (6897 bytes)" WIDTH="277" HEIGHT="86"></td> + <td><a href="../../index.htm"><font face="Arial" color="#FFFFFF"><big>Home </big></font></a></td> + <td><a href="../libraries.htm"><font face="Arial" color="#FFFFFF"><big>Libraries </big></font></a></td> + <td><a href="http://www.boost.org/people/people.htm"><font face="Arial" color="#FFFFFF"><big>People </big></font></a></td> + <td><a href="http://www.boost.org/more/faq.htm"><font face="Arial" color="#FFFFFF"><big>FAQ </big></font></a></td> + <td><a href="../../more/index.htm"><font face="Arial" color="#FFFFFF"><big>More </big></font></a></td> + </tr> +</table> + +<h1>Rational Number library</h1> + +<p>The header rational.hpp provides an implementation of rational numbers. +The implementation is template-based, in a similar manner to the standard +complex number class.</p> + +<p>This implementation is intended for general use. If you are a number +theorist, or otherwise have very stringent requirements, you would be advised +to use one of the more specialist packages available.</p> + +<ul> + <li><a href="rational.html">Documentation</a> (HTML).</li> + <li>Header <a href="../../boost/rational.hpp">rational.hpp</a>.</li> + <li>See the <a href="rational.html">documentation</a> for links to sample programs.</li> + <li>Submitted by <a href="http://www.boost.org/people/paul_moore.htm"> Paul Moore</a>.</li> +</ul> + +<p>Revised December 14, 1999</p> + +<p>© Copyright Paul Moore 1999. Permission to copy, use, modify, sell +and distribute this document is granted provided this copyright notice +appears in all copies. This document is provided "as is" without +express or implied warranty, and with no claim as to its suitability for +any purpose.</p> +</body> +</html> diff --git a/libs/rational/rational.html b/libs/rational/rational.html new file mode 100644 index 0000000000..32653c8767 --- /dev/null +++ b/libs/rational/rational.html @@ -0,0 +1,680 @@ +<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> +<html> +<head> +<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> +<title>Rational Number Library</title> +</head> +<body> +<h1><img src="../../boost.png" alt="boost.png (6897 bytes)" + align="middle" width="277" height="86"> +Rational Numbers</h1> + +<h2><a name="Contents">Contents</a></h2> + +<ol> + <li><a href="#Class%20rational%20synopsis">Class rational synopsis</a></li> + <li><a href="#Rationale">Rationale</a></li> + <li><a href="#Background">Background</a></li> + <li><a href="#Integer%20Type%20Requirements">Integer Type Requirements</a></li> + <li><a href="#Interface">Interface</a> + <ul> + <li><a href="#Utility%20functions">Utility functions</a></li> + <li><a href="#Constructors">Constructors</a></li> + <li><a href="#Arithmetic%20operations">Arithmetic operations</a></li> + <li><a href="#Input%20and%20Output">Input and Output</a></li> + <li><a href="#In-place%20assignment">In-place assignment</a></li> + <li><a href="#Conversions">Conversions</a></li> + <li><a href="#Numerator%20and%20Denominator">Numerator and Denominator</a></li> + </ul></li> + <li><a href="#Performance">Performance</a></li> + <li><a href="#Exceptions">Exceptions</a></li> + <li><a href="#Internal%20representation">Internal representation</a></li> + <li><a href="#Design%20notes">Design notes</a> + <ul> + <li><a href="#Minimal%20Implementation">Minimal Implementation</a></li> + <li><a href="#Limited-range%20integer%20types">Limited-range integer types</a></li> + <li><a href="#Conversion%20from%20floating%20point">Conversion from floating point</a></li> + <li><a href="#Absolute%20Value">Absolute Value</a></li> + </ul></li> + <li><a href="#References">References</a></li> + <li><a href="#History%20and%20Acknowledgements">History and Acknowledgements</a></li> +</ol> + +<h2><a name="Class rational synopsis">Class rational synopsis</a></h2> +<pre> +#include <boost/rational.hpp> + +namespace boost { + +class bad_rational; + +template<typename I> class rational { + typedef <em>implementation-defined</em> bool_type; + +public: + typedef I int_type; + + // Constructors + rational(); // Zero + rational(I n); // Equal to n/1 + rational(I n, I d); // General case (n/d) + + // Normal copy constructors and assignment operators + + // Assignment from I + rational& operator=(I n); + + // Assign in place + rational& assign(I n, I d); + + // Representation + I numerator() const; + I denominator() const; + + // In addition to the following operators, all of the "obvious" derived + // operators are available - see <a href="../utility/operators.htm">operators.hpp</a> + + // Arithmetic operators + rational& operator+= (const rational& r); + rational& operator-= (const rational& r); + rational& operator*= (const rational& r); + rational& operator/= (const rational& r); + + // Arithmetic with integers + rational& operator+= (I i); + rational& operator-= (I i); + rational& operator*= (I i); + rational& operator/= (I i); + + // Increment and decrement + const rational& operator++(); + const rational& operator--(); + + // Operator not + bool operator!() const; + + // Boolean conversion + operator bool_type() const; + + // Comparison operators + bool operator< (const rational& r) const; + bool operator== (const rational& r) const; + + // Comparison with integers + bool operator< (I i) const; + bool operator> (I i) const; + bool operator== (I i) const; +}; + +// Unary operators +template <typename I> rational<I> operator+ (const rational<I>& r); +template <typename I> rational<I> operator- (const rational<I>& r); + +// Reversed order operators for - and / between (types convertible to) I and rational +template <typename I, typename II> inline rational<I> operator- (II i, const rational<I>& r); +template <typename I, typename II> inline rational<I> operator/ (II i, const rational<I>& r); + +// Absolute value +template <typename I> rational<I> abs (const rational<I>& r); + +// Input and output +template <typename I> std::istream& operator>> (std::istream& is, rational<I>& r); +template <typename I> std::ostream& operator<< (std::ostream& os, const rational<I>& r); + +// Type conversion +template <typename T, typename I> T rational_cast (const rational<I>& r); +</pre> + +<h2><a name="Rationale">Rationale</a></h2> + +Numbers come in many different forms. The most basic forms are natural numbers +(non-negative "whole" numbers), integers and real numbers. These types are +approximated by the C++ built-in types <b>unsigned int</b>, <b>int</b>, and +<b>float</b> (and their various equivalents in different sizes). + +<p>The C++ Standard Library extends the range of numeric types available by +providing the <b>complex</b> type. + +<p>This library provides a further numeric type, the <b>rational</b> numbers. + +<p>The <b>rational</b> class is actually a implemented as a template, in a +similar manner to the standard <b>complex</b> class. + +<h2><a name="Background">Background</a></h2> + +The mathematical concept of a rational number is what is commonly thought of +as a fraction - that is, a number which can be represented as the ratio of two +integers. This concept is distinct from that of a real number, which can take +on many more values (for example, the square root of 2, which cannot be +represented as a fraction). + +<p> +Computers cannot represent mathematical concepts exactly - there are always +compromises to be made. Machine integers have a limited range of values (often +32 bits), and machine approximations to reals are limited in precision. The +compromises have differing motivations - machine integers allow exact +calculation, but with a limited range, whereas machine reals allow a much +greater range, but at the expense of exactness. + +<p> +The rational number class provides an alternative compromise. Calculations +with rationals are exact, but there are limitations on the available range. To +be precise, rational numbers are exact as long as the numerator and +denominator (which are always held in normalized form, with no common factors) +are within the range of the underlying integer type. When values go outside +these bounds, overflow occurs and the results are undefined. + +<p> +The rational number class is a template to allow the programmer to control the +overflow behaviour somewhat. If an unlimited precision integer type is +available, rational numbers based on it will never overflow and will provide +exact calculations in all circumstances. + +<h2><a name="Integer Type Requirements">Integer Type Requirements</a></h2> + +<p> The rational type takes a single template type parameter I. This is the +<em>underlying integer type</em> for the rational type. Any of the built-in +integer types provided by the C++ implementation are supported as values for +I. User-defined types may also be used, but users should be aware that the +performance characteristics of the rational class are highly dependent upon +the performance characteristics of the underlying integer type (often in +complex ways - for specific notes, see the <a href="#Performance">Performance</a> +section below). Note: Should the boost library support an unlimited-precision +integer type in the future, this type will be fully supported as the underlying +integer type for the rational class. +</p> + +<p> +A user-defined integer type which is to be used as the underlying integer type +for the rational type must be a model of the following concepts. +</p> + +<ul> +<li>Assignable +<li>Default Constructible +<li>Equality Comparable +<li>LessThan Comparable +</ul> + +<p> +Furthermore, I must be an <em>integer-like</em> type, that is the following +expressions must be valid for any two values n and m of type I, with the +"expected" semantics. + +<ul> +<li><code>n + m</code> +<li><code>n - m</code> +<li><code>n * m</code> +<li><code>n / m</code> (must truncate; must be nonnegative if <var>n</var> and + <var>m</var> are positive) +<li><code>n % m</code> (must be nonnegative if <var>n</var> and <var>m</var> + are positive) +<li>Assignment versions of the above +<li><code>+n</code>, <code>-n</code> +<li><code>!n</code> (must be <code>true</code> iff <var>n</var> is zero) +</ul> + +<p> +There must be <em>zero</em> and <em>one</em> values available for I. It should +be possible to generate these as <tt>I(0)</tt> and <tt>I(1)</tt>, +respectively. <em>Note:</em> This does not imply that I needs to have an +implicit conversion from integer - an <tt>explicit</tt> constructor is +adequate. + +<p> +It is valid for I to be an unsigned type. In that case, the derived rational +class will also be unsigned. Underflow behaviour of subtraction, where results +would otherwise be negative, is unpredictable in this case. + +<ul> +<li> +The implementation of rational_cast<T>(rational<I>) relies on the +ability to static_cast from type I to type T, and on the expression x/y being +valid for any two values of type T. +<li> +The input and output operators rely on the existence of corresponding input +and output operators for type I. +</ul> + +<p> +The <code>std::numeric_limits<I></code> specialization must exist (and be +visible before <code>boost::rational<I></code> needs to be specified). +The value of its <code>is_specialized</code> static data member must be +<var>true</var> and the value of its <code>is_signed</code> static data member +must be accurate. + +<h2><a name="Interface">Interface</a></h2> + +<h3><a name="Utility functions">Utility functions</a></h3> + +<p>Two utility function templates may be provided, that should work with <a +href="#Integer%20Type%20Requirements">any type that can be used</a> with the +<code>boost::rational<></code> class template.</p> + +<table summary="Common-factor utility functions"> +<tr> +<td width=5%></td> +<td><tt>gcd(n, m)</tt></td> +<td width=5%></td> +<td>The greatest common divisor of n and m</td> +</tr> +<tr> +<td width=5%></td> +<td><tt>lcm(n, m)</tt></td> +<td width=5%></td> +<td>The least common multiple of n and m</td> +</tr> +</table> + +<p>These function templates now forward calls to their equivalents in the <a +href="../math/">Boost.Math library</a>. Their presence can be controlled at +compile time with the <code>BOOST_CONTROL_RATIONAL_HAS_GCD</code> preprocessor +constant. + +<h3><a name="Constructors">Constructors</a></h3> +<p>Rationals can be constructed from zero, one, or two integer arguments; +representing default construction as zero, conversion from an integer posing as +the numerator with an implicit denominator of one, or a numerator and +denominator pair in that order, respectively. An integer argument should be of +the rational's integer type, or implicitly convertible to that type. (For the +two-argument constructor, any needed conversions are evaluated independently, +of course.) The components are stored in normalized form. + +<p>This implies that the following statements are valid: + +<pre> + I n, d; + rational<I> zero; + rational<I> r1(n); + rational<I> r2(n, d); +</pre> + +<p>The single-argument constructor is <em>not</em> declared as explicit, so +there is an implicit conversion from the underlying integer type to the +rational type. + +<h3><a name="Arithmetic operations">Arithmetic operations</a></h3> +All of the standard numeric operators are defined for the <b>rational</b> +class. These include: +<br> + +<pre> + + += + - -= + * *= + / /= + ++ -- (both prefix and postfix) + == != + < > + <= >= +</pre> + +<h3><a name="Input and Output">Input and Output</a></h3> +Input and output operators <tt><<</tt> and <tt>>></tt> +are provided. The external representation of a rational is +two integers, separated by a slash (<tt>/</tt>). On input, the format must be +exactly an integer, followed with no intervening whitespace by a slash, +followed (again with no intervening whitespace) by a second integer. The +external representation of an integer is defined by the undelying integer +type. + +<h3><a name="In-place assignment">In-place assignment</a></h3> +For any <tt>rational<I> r</tt>, <tt>r.assign(n, m)</tt> provides a +fast equivalent of <tt>r = rational<I>(n, m);</tt>, without the +construction of a temporary. While this is probably unnecessary for rationals +based on machine integer types, it could offer a saving for rationals based on +unlimited-precision integers, for example. + +<h3><a name="Conversions">Conversions</a></h3> +<p>There is a conversion operator to an unspecified Boolean type (most likely a +member pointer). This operator converts a rational to <code>false</code> if it +represents zero, and <code>true</code> otherwise. This conversion allows a +rational for use as the first argument of operator <code>?:</code>; as either +argument of operators <code>&&</code> or <code>||</code> without +forfeiting short-circuit evaluation; as a condition for a <code>do</code>, +<code>if</code>, <code>while</code>, or <code>for</code> statement; and as a +conditional declaration for <code>if</code>, <code>while</code>, or +<code>for</code> statements. The nature of the type used, and that any names +for that nature are kept private, should prevent any inappropriate non-Boolean +use like numeric or pointer operations or as a <code>switch</code> condition. + +<p>There are <em>no other</em> implicit conversions from a rational +type. However, there is an explicit type-conversion function, +<tt>rational_cast<T>(r)</tt>. This can be used as follows: + +<pre> + rational r(22,7); + double nearly_pi = boost::rational_cast<double>(r); +</pre> + +<p>The <tt>rational_cast<T></tt> function's behaviour is undefined if the +source rational's numerator or denominator cannot be safely cast to the +appropriate floating point type, or if the division of the numerator and +denominator (in the target floating point type) does not evaluate correctly. + +<p>In essence, all required conversions should be value-preserving, and all +operations should behave "sensibly". If these constraints cannot be met, a +separate user-defined conversion will be more appropriate. + +<p><em>Implementation note:</em> + +<p>The implementation of the rational_cast function was + +<pre> + template <typename Float, typename Int> + Float rational_cast(const rational<Int>& src) + { + return static_cast<Float>(src.numerator()) / src.denominator(); + } +</pre> + +Programs should not be written to depend upon this implementation, however, +especially since this implementation is now obsolete. (It required a mixed-mode +division between types <var>Float</var> and <var>Int</var>, contrary to the <a +href="#Integer%20Type%20Requirements">Integer Type Requirements</a>.) + +<h3><a name="Numerator and Denominator">Numerator and Denominator</a></h3> +Finally, access to the internal representation of rationals is provided by +the two member functions <tt>numerator()</tt> and <tt>denominator()</tt>. + +<p>These functions allow user code to implement any additional required +functionality. In particular, it should be noted that there may be cases where +the above rational_cast operation is inappropriate - particularly in cases +where the rational type is based on an unlimited-precision integer type. In +this case, a specially-written user-defined conversion to floating point will +be more appropriate. + +<h2><a name="Performance">Performance</a></h2> +The rational class has been designed with the implicit assumption that the +underlying integer type will act "like" the built in integer types. The +behavioural aspects of this assumption have been explicitly described above, +in the <a href="#Integer%20Type%20Requirements">Integer Type Requirements</a> +section. However, in addition to behavioural assumptions, there are implicit +performance assumptions. + +<p> No attempt will be made to provide detailed performance guarantees for the +operations available on the rational class. While it is possible for such +guarantees to be provided (in a similar manner to the performance +specifications of many of the standard library classes) it is by no means +clear that such guarantees will be of significant value to users of the +rational class. Instead, this section will provide a general discussion of the +performance characteristics of the rational class. + +<p>There now follows a list of the fundamental operations defined in the +<a href="../../boost/rational.hpp"> <boost/rational.hpp></a> header +and an informal description of their performance characteristics. Note that +these descriptions are based on the current implementation, and as such should +be considered subject to change. + +<ul> +<li>Construction of a rational is essentially just two constructions of the +underlying integer type, plus a normalization. + +<li>Increment and decrement operations are essentially as cheap as addition and +subtraction on the underlying integer type. + +<li>(In)equality comparison is essentially as cheap as two equality operations +on the underlying integer type. + +<li>I/O operations are not cheap, but their performance is essentially +dominated by the I/O time itself. + +<li>An (implicit) GCD routine call is essentially a repeated modulus operation. +Its other significant operations are construction, assignment, and comparison +against zero of IntType values. These latter operations are assumed to be +trivial in comparison with the modulus operation. + +<li>The (implicit) LCM operation is essentially a GCD plus a multiplication, +division, and comparison. + +<li>The addition and subtraction operations are complex. They will require +approximately two gcd operations, 3 divisions, 3 multiplications and an +addition on the underlying integer type. + +<li>The multiplication and division operations require two gcd operations, two +multiplications, and four divisions. + +<li>The compare-with-integer operation does a single integer division & +modulus pair, at most one extra integer addition and decrement, and at most +three integer comparisons. + +<li>The compare-with-rational operation does two double-sized GCD operations, +two extra additions and decrements, and three comparisons in the worst case. +(The GCD operations are double-sized because they are done in piecemeal and the +interim quotients are retained and compared, whereas a direct GCD function only +retains and compares the remainders.) + +<li>The final fundamental operation is normalizing a rational. This operation +is performed whenever a rational is constructed (and assigned in place). All +other operations are careful to maintain rationals in a normalized state. +Normalization costs the equivalent of one gcd and two divisions. +</ul> + +<p>Note that it is implicitly assumed that operations on IntType have the +"usual" performance characteristics - specifically, that the expensive +operations are multiplication, division, and modulo, with addition and +subtraction being significantly cheaper. It is assumed that construction (from +integer literals 0 and 1, and copy construction) and assignment are relatively +cheap, although some effort is taken to reduce unnecessary construction and +copying. It is also assumed that comparison (particularly against zero) is +cheap. + +<p>Integer types which do not conform to these assumptions will not be +particularly effective as the underlying integer type for the rational class. +Specifically, it is likely that performance will be severely sub-optimal. + +<h2><a name="Exceptions">Exceptions</a></h2> +Rationals can never have a denominator of zero. (This library does not support +representations for infinity or NaN). Should a rational result ever generate a +denominator of zero, the exception <tt>boost::bad_rational</tt> (a subclass of +<tt>std::domain_error</tt>) is thrown. This should only occur if the user +attempts to explicitly construct a rational with a denominator of zero, or to +divide a rational by a zero value. + +<p>In addition, if operations on the underlying integer type can generate +exceptions, these will be propogated out of the operations on the rational +class. No particular assumptions should be made - it is only safe to assume +that any exceptions which can be thrown by the integer class could be thrown +by any rational operation. In particular, the rational constructor may throw +exceptions from the underlying integer type as a result of the normalization +step. The only exception to this rule is that the rational destructor will +only throw exceptions which can be thrown by the destructor of the underlying +integer type (usually none). + +<h2><a name="Internal representation">Internal representation</a></h2> +<em>Note:</em> This information is for information only. Programs should not +be written in such a way as to rely on these implementation details. + +<p>Internally, rational numbers are stored as a pair (numerator, denominator) +of integers (whose type is specified as the template parameter for the +rational type). Rationals are always stored in fully normalized form (ie, +gcd(numerator,denominator) = 1, and the denominator is always positive). + +<h2><a name="Design notes">Design notes</a></h2> +<h3><a name="Minimal Implementation">Minimal Implementation</a></h3> +The rational number class is designed to keep to the basics. The minimal +operations required of a numeric class are provided, along with access to the +underlying representation in the form of the numerator() and denominator() +member functions. With these building-blocks, it is possible to implement any +additional functionality required. + +<p>Areas where this minimality consideration has been relaxed are in providing +input/output operators, and rational_cast. The former is generally +uncontroversial. However, there are a number of cases where rational_cast is +not the best possible method for converting a rational to a floating point +value (notably where user-defined types are involved). In those cases, a +user-defined conversion can and should be implemented. There is no need +for such an operation to be named rational_cast, and so the rational_cast +function does <em>not</em> provide the necessary infrastructure to allow for +specialisation/overloading. + +<h3><a name="Limited-range integer types">Limited-range integer types</a></h3> +The rational number class is designed for use in conjunction with an +unlimited precision integer class. With such a class, rationals are always +exact, and no problems arise with precision loss, overflow or underflow. + +<p>Unfortunately, the C++ standard does not offer such a class (and neither +does boost, at the present time). It is therefore likely that the rational +number class will in many cases be used with limited-precision integer types, +such as the built-in <tt>int</tt> type. + +<p>When used with a limited precision integer type, the rational class suffers +from many of the precision issues which cause difficulty with floating point +types. While it is likely that precision issues will not affect simple uses of +the rational class, users should be aware that such issues exist. + +<p>As a simple illustration of the issues associated with limited precision +integers, consider a case where the C++ <tt>int</tt> type is a 32-bit signed +representation. In this case, the smallest possible positive +rational<int> is <tt>1/0x7FFFFFFF</tt>. In other words, the +"granularity" of the rational<int> representation around zero is +approximately 4.66e-10. At the other end of the representable range, the +largest representable rational<int> is <tt>0x7FFFFFFF/1</tt>, and the +next lower representable rational<int> is <tt>0x7FFFFFFE/1</tt>. Thus, +at this end of the representable range, the granularity ia 1. This type of +magnitude-dependent granularity is typical of floating point representations. +However, it does not "feel" natural when using a rational number class. + +<p>It is up to the user of a rational type based on a limited-precision integer +type to be aware of, and code in anticipation of, such issues. + +<h3><a name="Conversion from floating point">Conversion from floating point</a></h3> +The library does not offer a conversion function from floating point to +rational. A number of requests were received for such a conversion, but +extensive discussions on the boost list reached the conclusion that there was +no "best solution" to the problem. As there is no reason why a user of the +library cannot write their own conversion function which suits their +particular requirements, the decision was taken not to pick any one algorithm +as "standard". + +<p>The key issue with any conversion function from a floating point value is +how to handle the loss of precision which is involved in floating point +operations. To provide a concrete example, consider the following code: + +<pre> + // These two values could in practice be obtained from user input, + // or from some form of measuring instrument. + double x = 1.0; + double y = 3.0; + + double z = x/y; + + rational<I> r = rational_from_double(z); +</pre> + +<p>The fundamental question is, precisely what rational should r be? A naive +answer is that r should be equal to 1/3. However, this ignores a multitude of +issues. + +<p>In the first instance, z is not exactly 1/3. Because of the limitations of +floating point representation, 1/3 is not exactly representable in any of the +common representations for the double type. Should r therefore not contain an +(exact) representation of the actual value represented by z? But will the user +be happy with a value of 33333333333333331/100000000000000000 for r? + +<p>Before even considering the above issue, we have to consider the accuracy +of the original values, x and y. If they came from an analog measuring +instrument, for example, they are not infinitely accurate in any case. In such +a case, a rational representation like the above promises far more accuracy +than there is any justification for. + +<p>All of this implies that we should be looking for some form of "nearest +simple fraction". Algorithms to determine this sort of value do exist. +However, not all applications want to work like this. In other cases, the +whole point of converting to rational is to obtain an exact representation, in +order to prevent accuracy loss during a series of calculations. In this case, +a completely precise representation is required, regardless of how "unnatural" +the fractions look. + +<p>With these conflicting requirements, there is clearly no single solution +which will satisfy all users. Furthermore, the algorithms involved are +relatively complex and specialised, and are best implemented with a good +understanding of the application requirements. All of these factors make such +a function unsuitable for a general-purpose library such as this. + +<h3><a name="Absolute Value">Absolute Value</a></h3> +In the first instance, it seems logical to implement +abs(rational<IntType>) in terms of abs(IntType). +However, there are a number of issues which arise with doing so. + +<p>The first issue is that, in order to locate the appropriate implementation +of abs(IntType) in the case where IntType is a user-defined type in a user +namespace, Koenig lookup is required. Not all compilers support Koenig lookup +for functions at the current time. For such compilers, clumsy workarounds, +which require cooperation from the user of the rational class, are required to +make things work. + +<p>The second, and potentially more serious, issue is that for non-standard +built-in integer types (for example, 64-bit integer types such as +<em>long long</em> or <em>__int64</em>), there is no guarantee that the vendor +has supplied a built in abs() function operating on such types. This is a +quality-of-implementation issue, but in practical terms, vendor support for +types such as <em>long long</em> is still very patchy. + +<p>As a consequence of these issues, it does not seem worth implementing +abs(rational<IntType>) in terms of abs(IntType). Instead, a simple +implementation with an inline implementation of abs() is used: + +<pre> + template <typename IntType> + inline rational<IntType> abs(const rational<IntType>& r) + { + if (r.numerator() >= IntType(0)) + return r; + + return rational<IntType>(-r.numerator(), r.denominator()); + } +</pre> + +<p>The same arguments imply that where the absolute value of an IntType is +required elsewhere, the calculation is performed inline. + +<h2><a name="References">References</a></h2> +<ul> +<li>The rational number header itself: <a href="../../boost/rational.hpp">rational.hpp</a> +<li>Some example code: <a href="rational_example.cpp">rational_example.cpp</a> +<li>The regression test: <a href="rational_test.cpp">rational_test.cpp</a> +</ul> + +<h2><a name="History and Acknowledgements">History and Acknowledgements</a></h2> + +In December, 1999, I implemented the initial version of the rational number +class, and submitted it to the <A HREF="http://www.boost.org/">boost.org</A> +mailing list. Some discussion of the implementation took place on the mailing +list. In particular, Andrew D. Jewell pointed out the importance of ensuring +that the risk of overflow was minimised, and provided overflow-free +implementations of most of the basic operations. The name rational_cast was +suggested by Kevlin Henney. Ed Brey provided invaluable comments - not least +in pointing out some fairly stupid typing errors in the original code! + +<p>David Abrahams contributed helpful feedback on the documentation. + +<p>A long discussion of the merits of providing a conversion from floating +point to rational took place on the boost list in November 2000. Key +contributors included Reggie Seagraves, Lutz Kettner and Daniel Frey (although +most of the boost list seemed to get involved at one point or another!). Even +though the end result was a decision <em>not</em> to implement anything, the +discussion was very valuable in understanding the issues. + +<p>Stephen Silver contributed useful experience on using the rational class +with a user-defined integer type. + +<p>Nickolay Mladenov provided the current implementation of operator+= and +operator-=. + +<p>Discussion of the issues surrounding Koenig lookup and std::swap took place +on the boost list in January 2001. + +<p>Daryle Walker provided a Boolean conversion operator, so that a rational can +be used in the same Boolean contexts as the built-in numeric types, in December +2005. + +<p>Revised November 5, 2006</p> + +<p>© Copyright Paul Moore 1999-2001; © Daryle Walker 2005. Permission to +copy, use, modify, sell and distribute this document is granted provided this +copyright notice appears in all copies. This document is provided "as +is" without express or implied warranty, and with no claim as to its +suitability for any purpose.</p> +</body> +</html> diff --git a/libs/rational/test/Jamfile.v2 b/libs/rational/test/Jamfile.v2 new file mode 100644 index 0000000000..ae354f5d98 --- /dev/null +++ b/libs/rational/test/Jamfile.v2 @@ -0,0 +1,11 @@ +#~ Copyright Rene Rivera 2008 +#~ Distributed under the Boost Software License, Version 1.0. +#~ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) + +import testing ; + +test-suite rational + : [ run rational_example.cpp ] + [ run rational_test.cpp + /boost/test//boost_unit_test_framework/<link>static ] + ; diff --git a/libs/rational/test/rational_example.cpp b/libs/rational/test/rational_example.cpp new file mode 100644 index 0000000000..1438d30bf9 --- /dev/null +++ b/libs/rational/test/rational_example.cpp @@ -0,0 +1,104 @@ +// rational number example program ----------------------------------------// + +// (C) Copyright Paul Moore 1999. Permission to copy, use, modify, sell +// and distribute this software is granted provided this copyright notice +// appears in all copies. This software is provided "as is" without express or +// implied warranty, and with no claim as to its suitability for any purpose. + +// Revision History +// 14 Dec 99 Initial version + +#include <iostream> +#include <cassert> +#include <cstdlib> +#include <boost/config.hpp> +#ifndef BOOST_NO_LIMITS +#include <limits> +#else +#include <limits.h> +#endif +#include <exception> +#include <boost/rational.hpp> + +using std::cout; +using std::endl; +using boost::rational; + +#ifdef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP +// This is a nasty hack, required because MSVC does not implement "Koenig +// Lookup". Basically, if I call abs(r), the C++ standard says that the +// compiler should look for a definition of abs in the namespace which +// contains r's class (in this case boost) - among other places. + +// Koenig Lookup is a relatively recent feature, and other compilers may not +// implement it yet. If so, try including this line. + +using boost::abs; +#endif + +int main () +{ + rational<int> half(1,2); + rational<int> one(1); + rational<int> two(2); + + // Some basic checks + assert(half.numerator() == 1); + assert(half.denominator() == 2); + assert(boost::rational_cast<double>(half) == 0.5); + + // Arithmetic + assert(half + half == one); + assert(one - half == half); + assert(two * half == one); + assert(one / half == two); + + // With conversions to integer + assert(half+half == 1); + assert(2 * half == one); + assert(2 * half == 1); + assert(one / half == 2); + assert(1 / half == 2); + + // Sign handling + rational<int> minus_half(-1,2); + assert(-half == minus_half); + assert(abs(minus_half) == half); + + // Do we avoid overflow? +#ifndef BOOST_NO_LIMITS + int maxint = (std::numeric_limits<int>::max)(); +#else + int maxint = INT_MAX; +#endif + rational<int> big(maxint, 2); + assert(2 * big == maxint); + + // Print some of the above results + cout << half << "+" << half << "=" << one << endl; + cout << one << "-" << half << "=" << half << endl; + cout << two << "*" << half << "=" << one << endl; + cout << one << "/" << half << "=" << two << endl; + cout << "abs(" << minus_half << ")=" << half << endl; + cout << "2 * " << big << "=" << maxint + << " (rational: " << rational<int>(maxint) << ")" << endl; + + // Some extras + rational<int> pi(22,7); + cout << "pi = " << boost::rational_cast<double>(pi) << " (nearly)" << endl; + + // Exception handling + try { + rational<int> r; // Forgot to initialise - set to 0 + r = 1/r; // Boom! + } + catch (const boost::bad_rational &e) { + cout << "Bad rational, as expected: " << e.what() << endl; + } + catch (...) { + cout << "Wrong exception raised!" << endl; + } + + return 0; +} + diff --git a/libs/rational/test/rational_test.cpp b/libs/rational/test/rational_test.cpp new file mode 100644 index 0000000000..847c9daf7c --- /dev/null +++ b/libs/rational/test/rational_test.cpp @@ -0,0 +1,969 @@ +/* + * A test program for boost/rational.hpp. + * Change the typedef at the beginning of run_tests() to try out different + * integer types. (These tests are designed only for signed integer + * types. They should work for short, int and long.) + * + * (C) Copyright Stephen Silver, 2001. Permission to copy, use, modify, sell + * and distribute this software is granted provided this copyright notice + * appears in all copies. This software is provided "as is" without express or + * implied warranty, and with no claim as to its suitability for any purpose. + * + * Incorporated into the boost rational number library, and modified and + * extended, by Paul Moore, with permission. + */ + +// Revision History +// 05 Nov 06 Add testing of zero-valued denominators & divisors; casting with +// types that are not implicitly convertible (Daryle Walker) +// 04 Nov 06 Resolve GCD issue with depreciation (Daryle Walker) +// 02 Nov 06 Add testing for operator<(int_type) w/ unsigneds (Daryle Walker) +// 31 Oct 06 Add testing for operator<(rational) overflow (Daryle Walker) +// 18 Oct 06 Various fixes for old compilers (Joaquín M López Muñoz) +// 27 Dec 05 Add testing for Boolean conversion operator (Daryle Walker) +// 24 Dec 05 Change code to use Boost.Test (Daryle Walker) +// 04 Mar 01 Patches for Intel C++ and GCC (David Abrahams) + +#define BOOST_TEST_MAIN "Boost::Rational unit tests" + +#include <boost/config.hpp> +#include <boost/mpl/list.hpp> +#include <boost/operators.hpp> +#include <boost/preprocessor/stringize.hpp> +#include <boost/math/common_factor_rt.hpp> + +#include <boost/rational.hpp> + +#include <boost/test/unit_test.hpp> +#include <boost/test/floating_point_comparison.hpp> +#include <boost/test/test_case_template.hpp> + +#include <climits> +#include <iostream> +#include <istream> +#include <limits> +#include <ostream> +#include <sstream> +#include <stdexcept> +#include <string> + +// We can override this on the compile, as -DINT_TYPE=short or whatever. +// The default test is against rational<long>. +#ifndef INT_TYPE +#define INT_TYPE long +#endif + +namespace { + +class MyOverflowingUnsigned; + +// This is a trivial user-defined wrapper around the built in int type. +// It can be used as a test type for rational<> +class MyInt : boost::operators<MyInt> +{ + friend class MyOverflowingUnsigned; + int val; +public: + MyInt(int n = 0) : val(n) {} + friend MyInt operator+ (const MyInt&); + friend MyInt operator- (const MyInt&); + MyInt& operator+= (const MyInt& rhs) { val += rhs.val; return *this; } + MyInt& operator-= (const MyInt& rhs) { val -= rhs.val; return *this; } + MyInt& operator*= (const MyInt& rhs) { val *= rhs.val; return *this; } + MyInt& operator/= (const MyInt& rhs) { val /= rhs.val; return *this; } + MyInt& operator%= (const MyInt& rhs) { val %= rhs.val; return *this; } + MyInt& operator|= (const MyInt& rhs) { val |= rhs.val; return *this; } + MyInt& operator&= (const MyInt& rhs) { val &= rhs.val; return *this; } + MyInt& operator^= (const MyInt& rhs) { val ^= rhs.val; return *this; } + const MyInt& operator++() { ++val; return *this; } + const MyInt& operator--() { --val; return *this; } + bool operator< (const MyInt& rhs) const { return val < rhs.val; } + bool operator== (const MyInt& rhs) const { return val == rhs.val; } + bool operator! () const { return !val; } + friend std::istream& operator>>(std::istream&, MyInt&); + friend std::ostream& operator<<(std::ostream&, const MyInt&); +}; + +inline MyInt operator+(const MyInt& rhs) { return rhs; } +inline MyInt operator-(const MyInt& rhs) { return MyInt(-rhs.val); } +inline std::istream& operator>>(std::istream& is, MyInt& i) { is >> i.val; return is; } +inline std::ostream& operator<<(std::ostream& os, const MyInt& i) { os << i.val; return os; } +inline MyInt abs(MyInt rhs) { if (rhs < MyInt()) rhs = -rhs; return rhs; } + +// This is an "unsigned" wrapper, that throws on overflow. It can be used to +// test rational<> when an operation goes out of bounds. +class MyOverflowingUnsigned + : private boost::unit_steppable<MyOverflowingUnsigned> + , private boost::ordered_euclidian_ring_operators1<MyOverflowingUnsigned> +{ + // Helper type-aliases + typedef MyOverflowingUnsigned self_type; + typedef unsigned self_type::* bool_type; + + // Member data + unsigned v_; + +public: + // Exception base class + class exception_base { protected: virtual ~exception_base() throw() {} }; + + // Divide-by-zero exception class + class divide_by_0_error + : public virtual exception_base + , public std::domain_error + { + public: + explicit divide_by_0_error( std::string const &w ) + : std::domain_error( w ) {} + + virtual ~divide_by_0_error() throw() {} + }; + + // Overflow exception class + class overflowing_error + : public virtual exception_base + , public std::overflow_error + { + public: + explicit overflowing_error( std::string const &w ) + : std::overflow_error( w ) {} + + virtual ~overflowing_error() throw() {} + }; + + // Lifetime management (use automatic dtr & copy-ctr) + MyOverflowingUnsigned( unsigned v = 0 ) : v_( v ) {} + explicit MyOverflowingUnsigned( MyInt const &m ) : v_( m.val ) {} + + // Operators (use automatic copy-assignment); arithmetic & comparison only + self_type & operator ++() + { + if ( this->v_ == UINT_MAX ) throw overflowing_error( "increment" ); + else ++this->v_; + return *this; + } + self_type & operator --() + { + if ( !this->v_ ) throw overflowing_error( "decrement" ); + else --this->v_; + return *this; + } + + operator bool_type() const { return this->v_ ? &self_type::v_ : 0; } + + bool operator !() const { return !this->v_; } + self_type operator +() const { return self_type( +this->v_ ); } + self_type operator -() const { return self_type( -this->v_ ); } + + bool operator <(self_type const &r) const { return this->v_ < r.v_; } + bool operator ==(self_type const &r) const { return this->v_ == r.v_; } + + self_type & operator *=( self_type const &r ) + { + if ( r.v_ && this->v_ > UINT_MAX / r.v_ ) + { + throw overflowing_error( "oversized factors" ); + } + this->v_ *= r.v_; + return *this; + } + self_type & operator /=( self_type const &r ) + { + if ( !r.v_ ) throw divide_by_0_error( "division" ); + this->v_ /= r.v_; + return *this; + } + self_type & operator %=( self_type const &r ) + { + if ( !r.v_ ) throw divide_by_0_error( "modulus" ); + this->v_ %= r.v_; + return *this; + } + self_type & operator +=( self_type const &r ) + { + if ( this->v_ > UINT_MAX - r.v_ ) + { + throw overflowing_error( "oversized addends" ); + } + this->v_ += r.v_; + return *this; + } + self_type & operator -=( self_type const &r ) + { + if ( this->v_ < r.v_ ) + { + throw overflowing_error( "oversized subtrahend" ); + } + this->v_ -= r.v_; + return *this; + } + + // Input & output + template < typename Ch, class Tr > + friend std::basic_istream<Ch, Tr> & + operator >>( std::basic_istream<Ch, Tr> &i, self_type &x ) + { return i >> x.v_; } + + template < typename Ch, class Tr > + friend std::basic_ostream<Ch, Tr> & + operator <<( std::basic_ostream<Ch, Tr> &o, self_type const &x ) + { return o << x.v_; } + +}; // MyOverflowingUnsigned + +inline MyOverflowingUnsigned abs( MyOverflowingUnsigned const &x ) { return x; } + +} // namespace + + +// Specialize numeric_limits for the custom types +namespace std +{ + +template < > +class numeric_limits< MyInt > +{ + typedef numeric_limits<int> limits_type; + +public: + static const bool is_specialized = limits_type::is_specialized; + + static MyInt min BOOST_PREVENT_MACRO_SUBSTITUTION () throw() { return (limits_type::min)(); } + static MyInt max BOOST_PREVENT_MACRO_SUBSTITUTION () throw() { return (limits_type::max)(); } + + static const int digits = limits_type::digits; + static const int digits10 = limits_type::digits10; + static const bool is_signed = limits_type::is_signed; + static const bool is_integer = limits_type::is_integer; + static const bool is_exact = limits_type::is_exact; + static const int radix = limits_type::radix; + static MyInt epsilon() throw() { return limits_type::epsilon(); } + static MyInt round_error() throw() { return limits_type::round_error(); } + + static const int min_exponent = limits_type::min_exponent; + static const int min_exponent10 = limits_type::min_exponent10; + static const int max_exponent = limits_type::max_exponent; + static const int max_exponent10 = limits_type::max_exponent10; + + static const bool has_infinity = limits_type::has_infinity; + static const bool has_quiet_NaN = limits_type::has_quiet_NaN; + static const bool has_signaling_NaN = limits_type::has_signaling_NaN; + static const float_denorm_style has_denorm = limits_type::has_denorm; + static const bool has_denorm_loss = limits_type::has_denorm_loss; + + static MyInt infinity() throw() { return limits_type::infinity(); } + static MyInt quiet_NaN() throw() { return limits_type::quiet_NaN(); } + static MyInt signaling_NaN() throw() {return limits_type::signaling_NaN();} + static MyInt denorm_min() throw() { return limits_type::denorm_min(); } + + static const bool is_iec559 = limits_type::is_iec559; + static const bool is_bounded = limits_type::is_bounded; + static const bool is_modulo = limits_type::is_modulo; + + static const bool traps = limits_type::traps; + static const bool tinyness_before = limits_type::tinyness_before; + static const float_round_style round_style = limits_type::round_style; + +}; // std::numeric_limits<MyInt> + +template < > +class numeric_limits< MyOverflowingUnsigned > +{ + typedef numeric_limits<unsigned> limits_type; + +public: + static const bool is_specialized = limits_type::is_specialized; + + static MyOverflowingUnsigned min BOOST_PREVENT_MACRO_SUBSTITUTION () throw() { return (limits_type::min)(); } + static MyOverflowingUnsigned max BOOST_PREVENT_MACRO_SUBSTITUTION () throw() { return (limits_type::max)(); } + + static const int digits = limits_type::digits; + static const int digits10 = limits_type::digits10; + static const bool is_signed = limits_type::is_signed; + static const bool is_integer = limits_type::is_integer; + static const bool is_exact = limits_type::is_exact; + static const int radix = limits_type::radix; + static MyOverflowingUnsigned epsilon() throw() + { return limits_type::epsilon(); } + static MyOverflowingUnsigned round_error() throw() + {return limits_type::round_error();} + + static const int min_exponent = limits_type::min_exponent; + static const int min_exponent10 = limits_type::min_exponent10; + static const int max_exponent = limits_type::max_exponent; + static const int max_exponent10 = limits_type::max_exponent10; + + static const bool has_infinity = limits_type::has_infinity; + static const bool has_quiet_NaN = limits_type::has_quiet_NaN; + static const bool has_signaling_NaN = limits_type::has_signaling_NaN; + static const float_denorm_style has_denorm = limits_type::has_denorm; + static const bool has_denorm_loss = limits_type::has_denorm_loss; + + static MyOverflowingUnsigned infinity() throw() + { return limits_type::infinity(); } + static MyOverflowingUnsigned quiet_NaN() throw() + { return limits_type::quiet_NaN(); } + static MyOverflowingUnsigned signaling_NaN() throw() + { return limits_type::signaling_NaN(); } + static MyOverflowingUnsigned denorm_min() throw() + { return limits_type::denorm_min(); } + + static const bool is_iec559 = limits_type::is_iec559; + static const bool is_bounded = limits_type::is_bounded; + static const bool is_modulo = limits_type::is_modulo; + + static const bool traps = limits_type::traps; + static const bool tinyness_before = limits_type::tinyness_before; + static const float_round_style round_style = limits_type::round_style; + +}; // std::numeric_limits<MyOverflowingUnsigned> + +} // namespace std + + +namespace { + +// This fixture replaces the check of rational's packing at the start of main. +class rational_size_check +{ + typedef INT_TYPE int_type; + typedef ::boost::rational<int_type> rational_type; + +public: + rational_size_check() + { + using ::std::cout; + + char const * const int_name = BOOST_PP_STRINGIZE( INT_TYPE ); + + cout << "Running tests for boost::rational<" << int_name << ">\n\n"; + + cout << "Implementation issue: the minimal size for a rational\n" + << "is twice the size of the underlying integer type.\n\n"; + + cout << "Checking to see if space is being wasted.\n" + << "\tsizeof(" << int_name << ") == " << sizeof( int_type ) + << "\n"; + cout << "\tsizeof(boost::rational<" << int_name << ">) == " + << sizeof( rational_type ) << "\n\n"; + + cout << "Implementation has " + << ( + (sizeof( rational_type ) > 2u * sizeof( int_type )) + ? "included padding bytes" + : "minimal size" + ) + << "\n\n"; + } +}; + +// This fixture groups all the common settings. +class my_configuration +{ +public: + template < typename T > + class hook + { + public: + typedef ::boost::rational<T> rational_type; + + private: + struct parts { rational_type parts_[ 9 ]; }; + + static parts generate_rationals() + { + rational_type r1, r2( 0 ), r3( 1 ), r4( -3 ), r5( 7, 2 ), + r6( 5, 15 ), r7( 14, -21 ), r8( -4, 6 ), + r9( -14, -70 ); + parts result; + result.parts_[0] = r1; + result.parts_[1] = r2; + result.parts_[2] = r3; + result.parts_[3] = r4; + result.parts_[4] = r5; + result.parts_[5] = r6; + result.parts_[6] = r7; + result.parts_[7] = r8; + result.parts_[8] = r9; + + return result; + } + + parts p_; // Order Dependency + + public: + rational_type ( &r_ )[ 9 ]; // Order Dependency + + hook() : p_( generate_rationals() ), r_( p_.parts_ ) {} + }; +}; + +// Instead of controlling the integer type needed with a #define, use a list of +// all available types. Since the headers #included don't change because of the +// integer #define, only the built-in types and MyInt are available. (Any other +// arbitrary integer type introduced by the #define would get compiler errors +// because its header can't be #included.) +typedef ::boost::mpl::list<short, int, long> builtin_signed_test_types; +typedef ::boost::mpl::list<short, int, long, MyInt> all_signed_test_types; + +// Without these explicit instantiations, MSVC++ 6.5/7.0 does not find +// some friend operators in certain contexts. +::boost::rational<short> dummy1; +::boost::rational<int> dummy2; +::boost::rational<long> dummy3; +::boost::rational<MyInt> dummy4; +::boost::rational<MyOverflowingUnsigned> dummy5; + +// Should there be regular tests with unsigned integer types? + +} // namespace + + +// Check if rational is the smallest size possible +BOOST_GLOBAL_FIXTURE( rational_size_check ) + + +#if BOOST_CONTROL_RATIONAL_HAS_GCD +// The factoring function template suite +BOOST_AUTO_TEST_SUITE( factoring_suite ) + +// GCD tests +BOOST_AUTO_TEST_CASE_TEMPLATE( gcd_test, T, all_signed_test_types ) +{ + BOOST_CHECK_EQUAL( boost::gcd<T>( 1, -1), static_cast<T>( 1) ); + BOOST_CHECK_EQUAL( boost::gcd<T>( -1, 1), static_cast<T>( 1) ); + BOOST_CHECK_EQUAL( boost::gcd<T>( 1, 1), static_cast<T>( 1) ); + BOOST_CHECK_EQUAL( boost::gcd<T>( -1, -1), static_cast<T>( 1) ); + BOOST_CHECK_EQUAL( boost::gcd<T>( 0, 0), static_cast<T>( 0) ); + BOOST_CHECK_EQUAL( boost::gcd<T>( 7, 0), static_cast<T>( 7) ); + BOOST_CHECK_EQUAL( boost::gcd<T>( 0, 9), static_cast<T>( 9) ); + BOOST_CHECK_EQUAL( boost::gcd<T>( -7, 0), static_cast<T>( 7) ); + BOOST_CHECK_EQUAL( boost::gcd<T>( 0, -9), static_cast<T>( 9) ); + BOOST_CHECK_EQUAL( boost::gcd<T>( 42, 30), static_cast<T>( 6) ); + BOOST_CHECK_EQUAL( boost::gcd<T>( 6, -9), static_cast<T>( 3) ); + BOOST_CHECK_EQUAL( boost::gcd<T>(-10, -10), static_cast<T>(10) ); + BOOST_CHECK_EQUAL( boost::gcd<T>(-25, -10), static_cast<T>( 5) ); +} + +// LCM tests +BOOST_AUTO_TEST_CASE_TEMPLATE( lcm_test, T, all_signed_test_types ) +{ + BOOST_CHECK_EQUAL( boost::lcm<T>( 1, -1), static_cast<T>( 1) ); + BOOST_CHECK_EQUAL( boost::lcm<T>( -1, 1), static_cast<T>( 1) ); + BOOST_CHECK_EQUAL( boost::lcm<T>( 1, 1), static_cast<T>( 1) ); + BOOST_CHECK_EQUAL( boost::lcm<T>( -1, -1), static_cast<T>( 1) ); + BOOST_CHECK_EQUAL( boost::lcm<T>( 0, 0), static_cast<T>( 0) ); + BOOST_CHECK_EQUAL( boost::lcm<T>( 6, 0), static_cast<T>( 0) ); + BOOST_CHECK_EQUAL( boost::lcm<T>( 0, 7), static_cast<T>( 0) ); + BOOST_CHECK_EQUAL( boost::lcm<T>( -5, 0), static_cast<T>( 0) ); + BOOST_CHECK_EQUAL( boost::lcm<T>( 0, -4), static_cast<T>( 0) ); + BOOST_CHECK_EQUAL( boost::lcm<T>( 18, 30), static_cast<T>(90) ); + BOOST_CHECK_EQUAL( boost::lcm<T>( -6, 9), static_cast<T>(18) ); + BOOST_CHECK_EQUAL( boost::lcm<T>(-10, -10), static_cast<T>(10) ); + BOOST_CHECK_EQUAL( boost::lcm<T>( 25, -10), static_cast<T>(50) ); +} + +BOOST_AUTO_TEST_SUITE_END() +#endif // BOOST_CONTROL_RATIONAL_HAS_GCD + + +// The basic test suite +BOOST_FIXTURE_TEST_SUITE( basic_rational_suite, my_configuration ) + +// Initialization tests +BOOST_AUTO_TEST_CASE_TEMPLATE( rational_initialization_test, T, + all_signed_test_types ) +{ + my_configuration::hook<T> h; + boost::rational<T> &r1 = h.r_[ 0 ], &r2 = h.r_[ 1 ], &r3 = h.r_[ 2 ], + &r4 = h.r_[ 3 ], &r5 = h.r_[ 4 ], &r6 = h.r_[ 5 ], + &r7 = h.r_[ 6 ], &r8 = h.r_[ 7 ], &r9 = h.r_[ 8 ]; + + BOOST_CHECK_EQUAL( r1.numerator(), static_cast<T>( 0) ); + BOOST_CHECK_EQUAL( r2.numerator(), static_cast<T>( 0) ); + BOOST_CHECK_EQUAL( r3.numerator(), static_cast<T>( 1) ); + BOOST_CHECK_EQUAL( r4.numerator(), static_cast<T>(-3) ); + BOOST_CHECK_EQUAL( r5.numerator(), static_cast<T>( 7) ); + BOOST_CHECK_EQUAL( r6.numerator(), static_cast<T>( 1) ); + BOOST_CHECK_EQUAL( r7.numerator(), static_cast<T>(-2) ); + BOOST_CHECK_EQUAL( r8.numerator(), static_cast<T>(-2) ); + BOOST_CHECK_EQUAL( r9.numerator(), static_cast<T>( 1) ); + + BOOST_CHECK_EQUAL( r1.denominator(), static_cast<T>(1) ); + BOOST_CHECK_EQUAL( r2.denominator(), static_cast<T>(1) ); + BOOST_CHECK_EQUAL( r3.denominator(), static_cast<T>(1) ); + BOOST_CHECK_EQUAL( r4.denominator(), static_cast<T>(1) ); + BOOST_CHECK_EQUAL( r5.denominator(), static_cast<T>(2) ); + BOOST_CHECK_EQUAL( r6.denominator(), static_cast<T>(3) ); + BOOST_CHECK_EQUAL( r7.denominator(), static_cast<T>(3) ); + BOOST_CHECK_EQUAL( r8.denominator(), static_cast<T>(3) ); + BOOST_CHECK_EQUAL( r9.denominator(), static_cast<T>(5) ); + + BOOST_CHECK_THROW( boost::rational<T>( 3, 0), boost::bad_rational ); + BOOST_CHECK_THROW( boost::rational<T>(-2, 0), boost::bad_rational ); + BOOST_CHECK_THROW( boost::rational<T>( 0, 0), boost::bad_rational ); +} + +// Assignment (non-operator) tests +BOOST_AUTO_TEST_CASE_TEMPLATE( rational_assign_test, T, all_signed_test_types ) +{ + my_configuration::hook<T> h; + boost::rational<T> & r = h.r_[ 0 ]; + + r.assign( 6, 8 ); + BOOST_CHECK_EQUAL( r.numerator(), static_cast<T>(3) ); + BOOST_CHECK_EQUAL( r.denominator(), static_cast<T>(4) ); + + r.assign( 0, -7 ); + BOOST_CHECK_EQUAL( r.numerator(), static_cast<T>(0) ); + BOOST_CHECK_EQUAL( r.denominator(), static_cast<T>(1) ); + + BOOST_CHECK_THROW( r.assign( 4, 0), boost::bad_rational ); + BOOST_CHECK_THROW( r.assign( 0, 0), boost::bad_rational ); + BOOST_CHECK_THROW( r.assign(-7, 0), boost::bad_rational ); +} + +// Comparison tests +BOOST_AUTO_TEST_CASE_TEMPLATE( rational_comparison_test, T, + all_signed_test_types ) +{ + my_configuration::hook<T> h; + boost::rational<T> &r1 = h.r_[ 0 ], &r2 = h.r_[ 1 ], &r3 = h.r_[ 2 ], + &r4 = h.r_[ 3 ], &r5 = h.r_[ 4 ], &r6 = h.r_[ 5 ], + &r7 = h.r_[ 6 ], &r8 = h.r_[ 7 ], &r9 = h.r_[ 8 ]; + + BOOST_CHECK( r1 == r2 ); + BOOST_CHECK( r2 != r3 ); + BOOST_CHECK( r4 < r3 ); + BOOST_CHECK( r4 <= r5 ); + BOOST_CHECK( r1 <= r2 ); + BOOST_CHECK( r5 > r6 ); + BOOST_CHECK( r5 >= r6 ); + BOOST_CHECK( r7 >= r8 ); + + BOOST_CHECK( !(r3 == r2) ); + BOOST_CHECK( !(r1 != r2) ); + BOOST_CHECK( !(r1 < r2) ); + BOOST_CHECK( !(r5 < r6) ); + BOOST_CHECK( !(r9 <= r2) ); + BOOST_CHECK( !(r8 > r7) ); + BOOST_CHECK( !(r8 > r2) ); + BOOST_CHECK( !(r4 >= r6) ); + + BOOST_CHECK( r1 == static_cast<T>( 0) ); + BOOST_CHECK( r2 != static_cast<T>(-1) ); + BOOST_CHECK( r3 < static_cast<T>( 2) ); + BOOST_CHECK( r4 <= static_cast<T>(-3) ); + BOOST_CHECK( r5 > static_cast<T>( 3) ); + BOOST_CHECK( r6 >= static_cast<T>( 0) ); + + BOOST_CHECK( static_cast<T>( 0) == r2 ); + BOOST_CHECK( static_cast<T>( 0) != r7 ); + BOOST_CHECK( static_cast<T>(-1) < r8 ); + BOOST_CHECK( static_cast<T>(-2) <= r9 ); + BOOST_CHECK( static_cast<T>( 1) > r1 ); + BOOST_CHECK( static_cast<T>( 1) >= r3 ); + + // Extra tests with values close in continued-fraction notation + boost::rational<T> const x1( static_cast<T>(9), static_cast<T>(4) ); + boost::rational<T> const x2( static_cast<T>(61), static_cast<T>(27) ); + boost::rational<T> const x3( static_cast<T>(52), static_cast<T>(23) ); + boost::rational<T> const x4( static_cast<T>(70), static_cast<T>(31) ); + + BOOST_CHECK( x1 < x2 ); + BOOST_CHECK( !(x1 < x1) ); + BOOST_CHECK( !(x2 < x2) ); + BOOST_CHECK( !(x2 < x1) ); + BOOST_CHECK( x2 < x3 ); + BOOST_CHECK( x4 < x2 ); + BOOST_CHECK( !(x3 < x4) ); + BOOST_CHECK( r7 < x1 ); // not actually close; wanted -ve v. +ve instead + BOOST_CHECK( !(x2 < r7) ); +} + +// Increment & decrement tests +BOOST_AUTO_TEST_CASE_TEMPLATE( rational_1step_test, T, all_signed_test_types ) +{ + my_configuration::hook<T> h; + boost::rational<T> &r1 = h.r_[ 0 ], &r2 = h.r_[ 1 ], &r3 = h.r_[ 2 ], + &r7 = h.r_[ 6 ], &r8 = h.r_[ 7 ]; + + BOOST_CHECK( r1++ == r2 ); + BOOST_CHECK( r1 != r2 ); + BOOST_CHECK( r1 == r3 ); + BOOST_CHECK( --r1 == r2 ); + BOOST_CHECK( r8-- == r7 ); + BOOST_CHECK( r8 != r7 ); + BOOST_CHECK( ++r8 == r7 ); +} + +// Absolute value tests +BOOST_AUTO_TEST_CASE_TEMPLATE( rational_abs_test, T, all_signed_test_types ) +{ + typedef my_configuration::hook<T> hook_type; + typedef typename hook_type::rational_type rational_type; + + hook_type h; + rational_type &r2 = h.r_[ 1 ], &r5 = h.r_[ 4 ], &r8 = h.r_[ 7 ]; + +#ifdef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP + // This is a nasty hack, required because some compilers do not implement + // "Koenig Lookup." Basically, if I call abs(r), the C++ standard says that + // the compiler should look for a definition of abs in the namespace which + // contains r's class (in this case boost)--among other places. + + using boost::abs; +#endif + + BOOST_CHECK_EQUAL( abs(r2), r2 ); + BOOST_CHECK_EQUAL( abs(r5), r5 ); + BOOST_CHECK_EQUAL( abs(r8), rational_type(2, 3) ); +} + +// Unary operator tests +BOOST_AUTO_TEST_CASE_TEMPLATE( rational_unary_test, T, all_signed_test_types ) +{ + my_configuration::hook<T> h; + boost::rational<T> &r2 = h.r_[ 1 ], &r3 = h.r_[ 2 ], + &r4 = h.r_[ 3 ], &r5 = h.r_[ 4 ]; + + BOOST_CHECK_EQUAL( +r5, r5 ); + + BOOST_CHECK( -r3 != r3 ); + BOOST_CHECK_EQUAL( -(-r3), r3 ); + BOOST_CHECK_EQUAL( -r4, static_cast<T>(3) ); + + BOOST_CHECK( !r2 ); + BOOST_CHECK( !!r3 ); + + BOOST_CHECK( ! static_cast<bool>(r2) ); + BOOST_CHECK( r3 ); +} + +BOOST_AUTO_TEST_SUITE_END() + + +// The rational arithmetic operations suite +BOOST_AUTO_TEST_SUITE( rational_arithmetic_suite ) + +// Addition & subtraction tests +BOOST_AUTO_TEST_CASE_TEMPLATE( rational_additive_test, T, + all_signed_test_types ) +{ + typedef boost::rational<T> rational_type; + + BOOST_CHECK_EQUAL( rational_type( 1, 2) + rational_type(1, 2), + static_cast<T>(1) ); + BOOST_CHECK_EQUAL( rational_type(11, 3) + rational_type(1, 2), + rational_type( 25, 6) ); + BOOST_CHECK_EQUAL( rational_type(-8, 3) + rational_type(1, 5), + rational_type(-37, 15) ); + BOOST_CHECK_EQUAL( rational_type(-7, 6) + rational_type(1, 7), + rational_type( 1, 7) - rational_type(7, 6) ); + BOOST_CHECK_EQUAL( rational_type(13, 5) - rational_type(1, 2), + rational_type( 21, 10) ); + BOOST_CHECK_EQUAL( rational_type(22, 3) + static_cast<T>(1), + rational_type( 25, 3) ); + BOOST_CHECK_EQUAL( rational_type(12, 7) - static_cast<T>(2), + rational_type( -2, 7) ); + BOOST_CHECK_EQUAL( static_cast<T>(3) + rational_type(4, 5), + rational_type( 19, 5) ); + BOOST_CHECK_EQUAL( static_cast<T>(4) - rational_type(9, 2), + rational_type( -1, 2) ); + + rational_type r( 11 ); + + r -= rational_type( 20, 3 ); + BOOST_CHECK_EQUAL( r, rational_type(13, 3) ); + + r += rational_type( 1, 2 ); + BOOST_CHECK_EQUAL( r, rational_type(29, 6) ); + + r -= static_cast<T>( 5 ); + BOOST_CHECK_EQUAL( r, rational_type( 1, -6) ); + + r += rational_type( 1, 5 ); + BOOST_CHECK_EQUAL( r, rational_type( 1, 30) ); + + r += static_cast<T>( 2 ); + BOOST_CHECK_EQUAL( r, rational_type(61, 30) ); +} + +// Assignment tests +BOOST_AUTO_TEST_CASE_TEMPLATE( rational_assignment_test, T, + all_signed_test_types ) +{ + typedef boost::rational<T> rational_type; + + rational_type r; + + r = rational_type( 1, 10 ); + BOOST_CHECK_EQUAL( r, rational_type( 1, 10) ); + + r = static_cast<T>( -9 ); + BOOST_CHECK_EQUAL( r, rational_type(-9, 1) ); +} + +// Multiplication tests +BOOST_AUTO_TEST_CASE_TEMPLATE( rational_multiplication_test, T, + all_signed_test_types ) +{ + typedef boost::rational<T> rational_type; + + BOOST_CHECK_EQUAL( rational_type(1, 3) * rational_type(-3, 4), + rational_type(-1, 4) ); + BOOST_CHECK_EQUAL( rational_type(2, 5) * static_cast<T>(7), + rational_type(14, 5) ); + BOOST_CHECK_EQUAL( static_cast<T>(-2) * rational_type(1, 6), + rational_type(-1, 3) ); + + rational_type r = rational_type( 3, 7 ); + + r *= static_cast<T>( 14 ); + BOOST_CHECK_EQUAL( r, static_cast<T>(6) ); + + r *= rational_type( 3, 8 ); + BOOST_CHECK_EQUAL( r, rational_type(9, 4) ); +} + +// Division tests +BOOST_AUTO_TEST_CASE_TEMPLATE( rational_division_test, T, + all_signed_test_types ) +{ + typedef boost::rational<T> rational_type; + + BOOST_CHECK_EQUAL( rational_type(-1, 20) / rational_type(4, 5), + rational_type(-1, 16) ); + BOOST_CHECK_EQUAL( rational_type( 5, 6) / static_cast<T>(7), + rational_type( 5, 42) ); + BOOST_CHECK_EQUAL( static_cast<T>(8) / rational_type(2, 7), + static_cast<T>(28) ); + + BOOST_CHECK_THROW( rational_type(23, 17) / rational_type(), + boost::bad_rational ); + BOOST_CHECK_THROW( rational_type( 4, 15) / static_cast<T>(0), + boost::bad_rational ); + + rational_type r = rational_type( 4, 3 ); + + r /= rational_type( 5, 4 ); + BOOST_CHECK_EQUAL( r, rational_type(16, 15) ); + + r /= static_cast<T>( 4 ); + BOOST_CHECK_EQUAL( r, rational_type( 4, 15) ); + + BOOST_CHECK_THROW( r /= rational_type(), boost::bad_rational ); + BOOST_CHECK_THROW( r /= static_cast<T>(0), boost::bad_rational ); + + BOOST_CHECK_EQUAL( rational_type(-1) / rational_type(-3), + rational_type(1, 3) ); +} + +// Tests for operations on self +BOOST_AUTO_TEST_CASE_TEMPLATE( rational_self_operations_test, T, + all_signed_test_types ) +{ + typedef boost::rational<T> rational_type; + + rational_type r = rational_type( 4, 3 ); + + r += r; + BOOST_CHECK_EQUAL( r, rational_type( 8, 3) ); + + r *= r; + BOOST_CHECK_EQUAL( r, rational_type(64, 9) ); + + r /= r; + BOOST_CHECK_EQUAL( r, rational_type( 1, 1) ); + + r -= r; + BOOST_CHECK_EQUAL( r, rational_type( 0, 1) ); + + BOOST_CHECK_THROW( r /= r, boost::bad_rational ); +} + +BOOST_AUTO_TEST_SUITE_END() + + +// The non-basic rational operations suite +BOOST_AUTO_TEST_SUITE( rational_extras_suite ) + +// Output test +BOOST_AUTO_TEST_CASE_TEMPLATE( rational_output_test, T, all_signed_test_types ) +{ + std::ostringstream oss; + + oss << boost::rational<T>( 44, 14 ); + BOOST_CHECK_EQUAL( oss.str(), "22/7" ); +} + +// Input test, failing +BOOST_AUTO_TEST_CASE_TEMPLATE( rational_input_failing_test, T, + all_signed_test_types ) +{ + std::istringstream iss( "" ); + boost::rational<T> r; + + iss >> r; + BOOST_CHECK( !iss ); + + iss.clear(); + iss.str( "42" ); + iss >> r; + BOOST_CHECK( !iss ); + + iss.clear(); + iss.str( "57A" ); + iss >> r; + BOOST_CHECK( !iss ); + + iss.clear(); + iss.str( "20-20" ); + iss >> r; + BOOST_CHECK( !iss ); + + iss.clear(); + iss.str( "1/" ); + iss >> r; + BOOST_CHECK( !iss ); + + iss.clear(); + iss.str( "1/ 2" ); + iss >> r; + BOOST_CHECK( !iss ); + + iss.clear(); + iss.str( "1 /2" ); + iss >> r; + BOOST_CHECK( !iss ); +} + +// Input test, passing +BOOST_AUTO_TEST_CASE_TEMPLATE( rational_input_passing_test, T, + all_signed_test_types ) +{ + typedef boost::rational<T> rational_type; + + std::istringstream iss( "1/2 12" ); + rational_type r; + int n = 0; + + BOOST_CHECK( iss >> r >> n ); + BOOST_CHECK_EQUAL( r, rational_type(1, 2) ); + BOOST_CHECK_EQUAL( n, 12 ); + + iss.clear(); + iss.str( "34/67" ); + BOOST_CHECK( iss >> r ); + BOOST_CHECK_EQUAL( r, rational_type(34, 67) ); + + iss.clear(); + iss.str( "-3/-6" ); + BOOST_CHECK( iss >> r ); + BOOST_CHECK_EQUAL( r, rational_type(1, 2) ); +} + +// Conversion test +BOOST_AUTO_TEST_CASE( rational_cast_test ) +{ + // Note that these are not generic. The problem is that rational_cast<T> + // requires a conversion from IntType to T. However, for a user-defined + // IntType, it is not possible to define such a conversion except as an + // "operator T()". This causes problems with overloading resolution. + boost::rational<int> const half( 1, 2 ); + + BOOST_CHECK_CLOSE( boost::rational_cast<double>(half), 0.5, 0.01 ); + BOOST_CHECK_EQUAL( boost::rational_cast<int>(half), 0 ); + BOOST_CHECK_EQUAL( boost::rational_cast<MyInt>(half), MyInt() ); + BOOST_CHECK_EQUAL( boost::rational_cast<boost::rational<MyInt> >(half), + boost::rational<MyInt>(1, 2) ); + + // Conversions via explicit-marked constructors + // (Note that the "explicit" mark prevents conversion to + // boost::rational<MyOverflowingUnsigned>.) + boost::rational<MyInt> const threehalves( 3, 2 ); + + BOOST_CHECK_EQUAL( boost::rational_cast<MyOverflowingUnsigned>(threehalves), + MyOverflowingUnsigned(1u) ); +} + +// Dice tests (a non-main test) +BOOST_AUTO_TEST_CASE_TEMPLATE( dice_roll_test, T, all_signed_test_types ) +{ + typedef boost::rational<T> rational_type; + + // Determine the mean number of times a fair six-sided die + // must be thrown until each side has appeared at least once. + rational_type r = T( 0 ); + + for ( int i = 1 ; i <= 6 ; ++i ) + { + r += rational_type( 1, i ); + } + r *= static_cast<T>( 6 ); + + BOOST_CHECK_EQUAL( r, rational_type(147, 10) ); +} + +BOOST_AUTO_TEST_SUITE_END() + + +// The bugs, patches, and requests checking suite +BOOST_AUTO_TEST_SUITE( bug_patch_request_suite ) + +// "rational operator< can overflow" +BOOST_AUTO_TEST_CASE( bug_798357_test ) +{ + // Choose values such that rational-number comparisons will overflow if + // the multiplication method (n1/d1 ? n2/d2 == n1*d2 ? n2*d1) is used. + // (And make sure that the large components are relatively prime, so they + // won't partially cancel to make smaller, more reasonable, values.) + unsigned const n1 = UINT_MAX - 2u, d1 = UINT_MAX - 1u; + unsigned const n2 = d1, d2 = UINT_MAX; + boost::rational<MyOverflowingUnsigned> const r1( n1, d1 ), r2( n2, d2 ); + + BOOST_REQUIRE_EQUAL( boost::math::gcd(n1, d1), 1u ); + BOOST_REQUIRE_EQUAL( boost::math::gcd(n2, d2), 1u ); + BOOST_REQUIRE( n1 > UINT_MAX / d2 ); + BOOST_REQUIRE( n2 > UINT_MAX / d1 ); + BOOST_CHECK( r1 < r2 ); + BOOST_CHECK( !(r1 < r1) ); + BOOST_CHECK( !(r2 < r1) ); +} + +// "rational::operator< fails for unsigned value types" +BOOST_AUTO_TEST_CASE( patch_1434821_test ) +{ + // If a zero-rational v. positive-integer comparison involves negation, then + // it may fail with unsigned types, which wrap around (for built-ins) or + // throw/be-undefined (for user-defined types). + boost::rational<unsigned> const r( 0u ); + + BOOST_CHECK( r < 1u ); +} + +// "rational.hpp::gcd returns a negative value sometimes" +BOOST_AUTO_TEST_CASE( patch_1438626_test ) +{ + // The issue only manifests with 2's-complement integers that use their + // entire range of bits. [This means that ln(-INT_MIN)/ln(2) is an integer + // and INT_MAX + INT_MIN == -1.] The common computer platforms match this. +#if (INT_MAX + INT_MIN == -1) && ((INT_MAX ^ INT_MIN) == -1) + // If a GCD routine takes the absolute value of an argument only before + // processing, it won't realize that -INT_MIN -> INT_MIN (i.e. no change + // from negation) and will propagate a negative sign to its result. + BOOST_REQUIRE_EQUAL( boost::math::gcd(INT_MIN, 6), 2 ); + + // That is bad if the rational number type does not check for that + // possibility during normalization. + boost::rational<int> const r1( INT_MIN / 2 + 3, 6 ), + r2( INT_MIN / 2 - 3, 6 ), r3 = r1 + r2; + + // If the error happens, the signs of the components will be switched. + // (The numerators' sum is INT_MIN, and its GCD with 6 would be negated.) + BOOST_CHECK_EQUAL( r3.numerator(), INT_MIN / 2 ); + BOOST_CHECK_EQUAL( r3.denominator(), 3 ); +#endif +} + +BOOST_AUTO_TEST_SUITE_END() |