diff options
| author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-27 18:24:20 +0000 |
|---|---|---|
| committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-27 18:24:20 +0000 |
| commit | 483eb2f56657e8e7f419ab1a4fab8dce9ade8609 (patch) | |
| tree | e5d88d25d870d5dedacb6bbdbe2a966086a0a5cf /src/boost/libs/rational/rational.html | |
| parent | Initial commit. (diff) | |
| download | ceph-upstream.tar.xz ceph-upstream.zip | |
Adding upstream version 14.2.21.upstream/14.2.21upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/boost/libs/rational/rational.html')
| -rw-r--r-- | src/boost/libs/rational/rational.html | 768 |
1 files changed, 768 insertions, 0 deletions
diff --git a/src/boost/libs/rational/rational.html b/src/boost/libs/rational/rational.html new file mode 100644 index 00000000..ebacab7f --- /dev/null +++ b/src/boost/libs/rational/rational.html @@ -0,0 +1,768 @@ +<!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; constexpr since C++11 + rational(I n); // Equal to n/1; constexpr since C++11 + rational(I n, I d); // General case (n/d); constexpr since C++14 + template<typename J> + explicit rational(const rational<J> &r); // Cross-instantiation; constexpr since C++11 + + // Normal copy constructors and assignment operators + + // Assignment from I + rational& operator=(I n); // constexpr since C++14 + + // Assign in place + rational& assign(I n, I d); // constexpr since C++14 + + // Representation + I numerator() const; // constexpr since C++11 + I denominator() const; // constexpr since C++11 + + // 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); // constexpr since C++14 + rational& operator-= (const rational& r); // constexpr since C++14 + rational& operator*= (const rational& r); // constexpr since C++14 + rational& operator/= (const rational& r); // constexpr since C++14 + + // Arithmetic with integers + rational& operator+= (I i); // constexpr since C++14 + rational& operator-= (I i); // constexpr since C++14 + rational& operator*= (I i); // constexpr since C++14 + rational& operator/= (I i); // constexpr since C++14 + + // Increment and decrement + const rational& operator++(); // constexpr since C++14 + const rational& operator--(); // constexpr since C++14 + + // Operator not + bool operator!() const; // constexpr since C++11 + + // Boolean conversion + operator bool_type() const; // constexpr since C++11 + + // Comparison operators + bool operator< (const rational& r) const; // constexpr since C++14 + bool operator== (const rational& r) const; // constexpr since C++11 + + // Comparison with integers + bool operator< (I i) const; // constexpr since C++14 + bool operator> (I i) const; // constexpr since C++14 + bool operator== (I i) const; // constexpr since C++11 +}; + +// Unary operators +template <typename I> rational<I> operator+ (const rational<I>& r); // constexpr since C++11 +template <typename I> rational<I> operator- (const rational<I>& r); // constexpr since C++14 + +// 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); // constexpr since C++14 +template <typename I, typename II> inline rational<I> operator/ (II i, const rational<I>& r); // constexpr since C++14 + +// Absolute value +template <typename I> rational<I> abs (const rational<I>& r); // constexpr since C++14 + +// 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); // constexpr since C++11 +</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 (modulo resource +limits) 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="../integer/">Boost.Integer 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>Rationals can also be constructed from another rational. When the source and +destination underlying integer types match, the automatically-defined copy- or +move-constructor is used. Otherwise, a converting constructor template is used. +The constructor does member-wise initialization of the numerator and denominator. +Component-level conversions that are marked <code>explicit</code> are fine. When +the conversion ends up value-preserving, it is already normalized; but a check +for normalization is performed in case value-preservation is violated. + +<p>These imply that the following statements are valid: + +<pre> + I n, d; + rational<I> zero; + rational<I> r1(n); + rational<I> r2(n, d); + rational<J> r3(r2); // assuming J(n) and J(d) are well-formed +</pre> + +<p>In C++11, the no-argument constructor, single-argument constructor, and +cross-version constructor template are marked as <code>constexpr</code>, making +them viable in constant-expressions when the initializers (if any) are also constant +expressions (and the necessary operations from the underlying integer type(s) +are <code>constexpr</code>-enabled). Since C++14, all constructors are +<code>constexpr</code>-enabled. + +<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. The two-argument constructor can be considered an implicit +conversion with C++11's uniform initialization syntax, since it is also not +declared explicit. The cross-version constructor template is declared explicit, +so the direction of conversion between two rational instantiations must be +specified. + +<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) + == != + < > + <= >= + + Unary: + - ! +</pre> + +<p>Since C++14, all of these operations are <code>constexpr</code>-enabled. +In C++11, only <code>operator==</code>, <code>operator!=</code>, +unary <code>operator+</code>, and <code>operator!</code> are. + +<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 underlying 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 an +alternate to <tt>r = rational<I>(n, m);</tt>, without a user-specified +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. + +<p>The function will throw if the given components cannot be formed into a valid +rational number. Otherwise, it could throw only if the component-level move +assignment (in C++11; copy-assignment for earlier C++ versions) can throw. The +strong guarantee is kept if throwing happens in the first part, but there is a +risk of neither the strong nor basic guarantees happening if an exception is +thrown during the component assignments. + +<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. Besides the explicit cross-version constructor template, there is an +explicit type-conversion function, <tt>rational_cast<T>(r)</tt>. This can +be used as follows: + +<pre> + rational<int> 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. +Also, since this function has a custom name, it cannot be called in generic code +for trading between two instantiations of the same class template, unlike the +cross-version constructor. + +<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>Boolean conversion and <tt>rational_cast</tt> are <code>constexpr</code>-enabled. + +<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>. +These functions are <code>constexpr</code>-enabled. + +<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, or otherwise fail during normalization, 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, to divide a rational by a zero value, or +generate a negative denominator too large to be normalized. The exception can +be thrown during a cross-instantiation conversion, when at least one of the +components ends up not being value-preserved and the new combination is not +considered normalized. + +<p>In addition, if operations on the underlying integer type can generate +exceptions, these will be propagated 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). + +<p>If the component-level assignment operator(s) can throw, then a rational +object's invariants may be violated if an exception happens during the second +component's assignment. (The <code>assign</code> member function counts here +too.) This violates both the strong and basic guarantees. + +<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 <s>(and neither +does boost, at the present time)</s>. 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>Limited-precision integer types may raise issues with the range sizes of +their allowable negative values and positive values. If the negative range is +larger, then the extremely-negative numbers will not have an additive inverse in +the positive range, making them unusable as denominator values since they cannot +be normalized to positive values (unless the user is lucky enough that the input +components are not relatively prime pre-normalization). + +<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="test/rational_example.cpp">rational_example.cpp</a> +<li>The regression test: <a href="test/rational_test.cpp">rational_test.cpp</a> +</ul> + +<h2><a name="History and Acknowledgements">History and Acknowledgements</a></h2> + + <p> + 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> + + <p>David Abrahams contributed helpful feedback on the documentation.</p> + + <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> + + <p> + Stephen Silver contributed useful experience on using the rational class + with a user-defined integer type. + </p> + + <p> + Nickolay Mladenov provided the current implementation of operator+= and + operator-=. + </p> + <p> + Discussion of the issues surrounding Koenig lookup and std::swap took place + on the boost list in January 2001. + </p> + <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. He added the cross-instantiation constructor template in August 2013. + </p> + <p> + July 2014: Updated numerator/denominator accessors to return values by constant + reference: this gives a performance improvement when using with multiprecision (class) types. + </p> + <p> + July 2014: Updated to use BOOST_THROW_EXCEPTION uniformly throughout. + </p> + <p> + July 2014: Added support for C++11 constexpr constructors, plus tests to match. + </p> + <p> + Nov 2014: Added support for gcd and lcm of rational numbers. + </p> + <p> + Dec 2016: Reworked constructors and operators to prohibit narrowing implicit + conversions, in particular accidental conversion from floating point types. + </p> + <p> + Oct/Nov 2018: Add more constexpr. + </p> + +<p>Revised July 14, 2017</p> + +<p>© Copyright Paul Moore 1999-2001; © Daryle Walker 2005, 2013. +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> +<!-- boostinspect:nolicense (can't find Paul Moore to change license) --> +</body> +</html> |