ceph/src/boost/libs/rational/rational.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
   2 <html>
   3 <head>
   4 <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
   5 <title>Rational Number Library</title>
   6 </head>
   7 <body>
   8 <h1><img src="../../boost.png" alt="boost.png (6897 bytes)"
   9      align="middle" width="277" height="86">
  10 Rational Numbers</h1>
  11
  12 <h2><a name="Contents">Contents</a></h2>
  13
  14 <ol>
  15     <li><a href="#Class%20rational%20synopsis">Class rational synopsis</a></li>
  16     <li><a href="#Rationale">Rationale</a></li>
  17     <li><a href="#Background">Background</a></li>
  18     <li><a href="#Integer%20Type%20Requirements">Integer Type Requirements</a></li>
  19     <li><a href="#Interface">Interface</a>
  20     <ul>
  21         <li><a href="#Utility%20functions">Utility functions</a></li>
  22         <li><a href="#Constructors">Constructors</a></li>
  23         <li><a href="#Arithmetic%20operations">Arithmetic operations</a></li>
  24         <li><a href="#Input%20and%20Output">Input and Output</a></li>
  25         <li><a href="#In-place%20assignment">In-place assignment</a></li>
  26         <li><a href="#Conversions">Conversions</a></li>
  27         <li><a href="#Numerator%20and%20Denominator">Numerator and Denominator</a></li>
  28     </ul></li>
  29     <li><a href="#Performance">Performance</a></li>
  30     <li><a href="#Exceptions">Exceptions</a></li>
  31     <li><a href="#Internal%20representation">Internal representation</a></li>
  32     <li><a href="#Design%20notes">Design notes</a>
  33     <ul>
  34         <li><a href="#Minimal%20Implementation">Minimal Implementation</a></li>
  35         <li><a href="#Limited-range%20integer%20types">Limited-range integer types</a></li>
  36         <li><a href="#Conversion%20from%20floating%20point">Conversion from floating point</a></li>
  37         <li><a href="#Absolute%20Value">Absolute Value</a></li>
  38     </ul></li>
  39     <li><a href="#References">References</a></li>
  40     <li><a href="#History%20and%20Acknowledgements">History and Acknowledgements</a></li>
  41 </ol>
  42
  43 <h2><a name="Class rational synopsis">Class rational synopsis</a></h2>
  44 <pre>
  45 #include &lt;boost/rational.hpp&gt;
  46
  47 namespace boost {
  48
  49 class bad_rational;
  50
  51 template&lt;typename I&gt; class rational {
  52     typedef <em>implementation-defined</em> bool_type;
  53
  54 public:
  55     typedef I int_type;
  56
  57     // Constructors
  58     rational();          // Zero;               constexpr since C++11
  59     rational(I n);       // Equal to n/1;       constexpr since C++11
  60     rational(I n, I d);  // General case (n/d); constexpr since C++14
  61     template&lt;typename J&gt;
  62     explicit rational(const rational&lt;J&gt; &amp;r);  // Cross-instantiation; constexpr since C++11
  63
  64     // Normal copy constructors and assignment operators
  65
  66     // Assignment from I
  67     rational&amp; operator=(I n); // constexpr since C++14
  68
  69     // Assign in place
  70     rational&amp; assign(I n, I d); // constexpr since C++14
  71
  72     // Representation
  73     I numerator() const;   // constexpr since C++11
  74     I denominator() const; // constexpr since C++11
  75
  76     // In addition to the following operators, all of the "obvious" derived
  77     // operators are available - see <a href="../utility/operators.htm">operators.hpp</a>
  78
  79     // Arithmetic operators
  80     rational&amp; operator+= (const rational&amp; r); // constexpr since C++14
  81     rational&amp; operator-= (const rational&amp; r); // constexpr since C++14
  82     rational&amp; operator*= (const rational&amp; r); // constexpr since C++14
  83     rational&amp; operator/= (const rational&amp; r); // constexpr since C++14
  84
  85     // Arithmetic with integers
  86     rational&amp; operator+= (I i); // constexpr since C++14
  87     rational&amp; operator-= (I i); // constexpr since C++14
  88     rational&amp; operator*= (I i); // constexpr since C++14
  89     rational&amp; operator/= (I i); // constexpr since C++14
  90
  91     // Increment and decrement
  92     const rational&amp; operator++(); // constexpr since C++14
  93     const rational&amp; operator--(); // constexpr since C++14
  94
  95     // Operator not
  96     bool operator!() const; // constexpr since C++11
  97
  98     // Boolean conversion
  99     operator bool_type() const; // constexpr since C++11
 100
 101     // Comparison operators
 102     bool operator&lt; (const rational&amp; r) const;  // constexpr since C++14
 103     bool operator== (const rational&amp; r) const; // constexpr since C++11
 104
 105     // Comparison with integers
 106     bool operator&lt; (I i) const;  // constexpr since C++14
 107     bool operator&gt; (I i) const;  // constexpr since C++14
 108     bool operator== (I i) const; // constexpr since C++11
 109 };
 110
 111 // Unary operators
 112 template &lt;typename I&gt; rational&lt;I&gt; operator+ (const rational&lt;I&gt;&amp; r); // constexpr since C++11
 113 template &lt;typename I&gt; rational&lt;I&gt; operator- (const rational&lt;I&gt;&amp; r); // constexpr since C++14
 114
 115 // Reversed order operators for - and / between (types convertible to) I and rational
 116 template &lt;typename I, typename II&gt; inline rational&lt;I&gt; operator- (II i, const rational&lt;I&gt;&amp; r); // constexpr since C++14
 117 template &lt;typename I, typename II&gt; inline rational&lt;I&gt; operator/ (II i, const rational&lt;I&gt;&amp; r); // constexpr since C++14
 118
 119 // Absolute value
 120 template &lt;typename I&gt; rational&lt;I&gt; abs (const rational&lt;I&gt;&amp; r); // constexpr since C++14
 121
 122 // Input and output
 123 template &lt;typename I&gt; std::istream&amp; operator&gt;&gt; (std::istream&amp; is, rational&lt;I&gt;&amp; r);
 124 template &lt;typename I&gt; std::ostream&amp; operator&lt;&lt; (std::ostream&amp; os, const rational&lt;I&gt;&amp; r);
 125
 126 // Type conversion
 127 template &lt;typename T, typename I&gt; T rational_cast (const rational&lt;I&gt;&amp; r); // constexpr since C++11
 128 </pre>
 129
 130 <h2><a name="Rationale">Rationale</a></h2>
 131
 132 Numbers come in many different forms. The most basic forms are natural numbers
 133 (non-negative "whole" numbers), integers and real numbers.  These types are
 134 approximated by the C++ built-in types <b>unsigned int</b>, <b>int</b>, and
 135 <b>float</b> (and their various equivalents in different sizes).
 136
 137 <p>The C++ Standard Library extends the range of numeric types available by
 138 providing the <b>complex</b> type.
 139
 140 <p>This library provides a further numeric type, the <b>rational</b> numbers.
 141
 142 <p>The <b>rational</b> class is actually a implemented as a template, in a
 143 similar manner to the standard <b>complex</b> class.
 144
 145 <h2><a name="Background">Background</a></h2>
 146
 147 The mathematical concept of a rational number is what is commonly thought of
 148 as a fraction - that is, a number which can be represented as the ratio of two
 149 integers. This concept is distinct from that of a real number, which can take
 150 on many more values (for example, the square root of 2, which cannot be
 151 represented as a fraction).
 152
 153 <p>
 154 Computers cannot represent mathematical concepts exactly - there are always
 155 compromises to be made. Machine integers have a limited range of values (often
 156 32 bits), and machine approximations to reals are limited in precision. The
 157 compromises have differing motivations - machine integers allow exact
 158 calculation, but with a limited range, whereas machine reals allow a much
 159 greater range, but at the expense of exactness.
 160
 161 <p>
 162 The rational number class provides an alternative compromise. Calculations
 163 with rationals are exact, but there are limitations on the available range. To
 164 be precise, rational numbers are exact as long as the numerator and
 165 denominator (which are always held in normalized form, with no common factors)
 166 are within the range of the underlying integer type. When values go outside
 167 these bounds, overflow occurs and the results are undefined.
 168
 169 <p>
 170 The rational number class is a template to allow the programmer to control the
 171 overflow behaviour somewhat. If an unlimited precision integer type is
 172 available, rational numbers based on it will never overflow (modulo resource
 173 limits) and will provide exact calculations in all circumstances.
 174
 175 <h2><a name="Integer Type Requirements">Integer Type Requirements</a></h2>
 176
 177 <p> The rational type takes a single template type parameter I. This is the
 178 <em>underlying integer type</em> for the rational type. Any of the built-in
 179 integer types provided by the C++ implementation are supported as values for
 180 I. User-defined types may also be used, but users should be aware that the
 181 performance characteristics of the rational class are highly dependent upon
 182 the performance characteristics of the underlying integer type (often in
 183 complex ways - for specific notes, see the <a href="#Performance">Performance</a>
 184 section below). Note: Should the boost library support an unlimited-precision
 185 integer type in the future, this type will be fully supported as the underlying
 186 integer type for the rational class.
 187 </p>
 188
 189 <p>
 190 A user-defined integer type which is to be used as the underlying integer type
 191 for the rational type must be a model of the following concepts.
 192 </p>
 193
 194 <ul>
 195 <li>Assignable
 196 <li>Default Constructible
 197 <li>Equality Comparable
 198 <li>LessThan Comparable
 199 </ul>
 200
 201 <p>
 202 Furthermore, I must be an <em>integer-like</em> type, that is the following
 203 expressions must be valid for any two values n and m of type I, with the
 204 "expected" semantics.
 205
 206 <ul>
 207 <li><code>n + m</code>
 208 <li><code>n - m</code>
 209 <li><code>n * m</code>
 210 <li><code>n / m</code> (must truncate; must be nonnegative if <var>n</var> and
 211     <var>m</var> are positive)
 212 <li><code>n % m</code> (must be nonnegative if <var>n</var> and <var>m</var>
 213     are positive)
 214 <li>Assignment versions of the above
 215 <li><code>+n</code>, <code>-n</code>
 216 <li><code>!n</code> (must be <code>true</code> iff <var>n</var> is zero)
 217 </ul>
 218
 219 <p>
 220 There must be <em>zero</em> and <em>one</em> values available for I. It should
 221 be possible to generate these as <tt>I(0)</tt> and <tt>I(1)</tt>,
 222 respectively. <em>Note:</em> This does not imply that I needs to have an
 223 implicit conversion from integer - an <tt>explicit</tt> constructor is
 224 adequate.
 225
 226 <p>
 227 It is valid for I to be an unsigned type. In that case, the derived rational
 228 class will also be unsigned. Underflow behaviour of subtraction, where results
 229 would otherwise be negative, is unpredictable in this case.
 230
 231 <ul>
 232 <li>
 233 The implementation of rational_cast&lt;T&gt;(rational&lt;I&gt;) relies on the
 234 ability to static_cast from type I to type T, and on the expression x/y being
 235 valid for any two values of type T.
 236 <li>
 237 The input and output operators rely on the existence of corresponding input
 238 and output operators for type I.
 239 </ul>
 240
 241 <p>
 242 The <code>std::numeric_limits&lt;I&gt;</code> specialization must exist (and be
 243 visible before <code>boost::rational&lt;I&gt;</code> needs to be specified).
 244 The value of its <code>is_specialized</code> static data member must be
 245 <var>true</var> and the value of its <code>is_signed</code> static data member
 246 must be accurate.
 247
 248 <h2><a name="Interface">Interface</a></h2>
 249
 250 <h3><a name="Utility functions">Utility functions</a></h3>
 251
 252 <p>Two utility function templates may be provided, that should work with <a
 253 href="#Integer%20Type%20Requirements">any type that can be used</a> with the
 254 <code>boost::rational&lt;&gt;</code> class template.</p>
 255
 256 <table summary="Common-factor utility functions">
 257 <tr>
 258 <td width=5%></td>
 259 <td><tt>gcd(n, m)</tt></td>
 260 <td width=5%></td>
 261 <td>The greatest common divisor of n and m</td>
 262 </tr>
 263 <tr>
 264 <td width=5%></td>
 265 <td><tt>lcm(n, m)</tt></td>
 266 <td width=5%></td>
 267 <td>The least common multiple of n and m</td>
 268 </tr>
 269 </table>
 270
 271 <p>These function templates now forward calls to their equivalents in the <a
 272 href="../integer/">Boost.Integer library</a>.  Their presence can be controlled at
 273 compile time with the <code>BOOST_CONTROL_RATIONAL_HAS_GCD</code> preprocessor
 274 constant.
 275
 276 <h3><a name="Constructors">Constructors</a></h3>
 277 <p>Rationals can be constructed from zero, one, or two integer arguments;
 278 representing default construction as zero, conversion from an integer posing as
 279 the numerator with an implicit denominator of one, or a numerator and
 280 denominator pair in that order, respectively.  An integer argument should be of
 281 the rational's integer type, or implicitly convertible to that type.  (For the
 282 two-argument constructor, any needed conversions are evaluated independently,
 283 of course.)  The components are stored in normalized form.
 284
 285 <p>Rationals can also be constructed from another rational.  When the source and
 286 destination underlying integer types match, the automatically-defined copy- or
 287 move-constructor is used.  Otherwise, a converting constructor template is used.
 288 The constructor does member-wise initialization of the numerator and denominator.
 289 Component-level conversions that are marked <code>explicit</code> are fine.  When
 290 the conversion ends up value-preserving, it is already normalized; but a check
 291 for normalization is performed in case value-preservation is violated.
 292
 293 <p>These imply that the following statements are valid:
 294
 295 <pre>
 296     I n, d;
 297     rational&lt;I&gt; zero;
 298     rational&lt;I&gt; r1(n);
 299     rational&lt;I&gt; r2(n, d);
 300     rational&lt;J&gt; r3(r2);  // assuming J(n) and J(d) are well-formed
 301 </pre>
 302
 303 <p>In C++11, the no-argument constructor, single-argument constructor, and
 304 cross-version constructor template are marked as <code>constexpr</code>, making
 305 them viable in constant-expressions when the initializers (if any) are also constant
 306 expressions (and the necessary operations from the underlying integer type(s)
 307 are <code>constexpr</code>-enabled). Since C++14, all constructors are
 308 <code>constexpr</code>-enabled.
 309
 310 <p>The single-argument constructor is <em>not</em> declared as explicit, so
 311 there is an implicit conversion from the underlying integer type to the
 312 rational type.  The two-argument constructor can be considered an implicit
 313 conversion with C++11's uniform initialization syntax, since it is also not
 314 declared explicit.  The cross-version constructor template is declared explicit,
 315 so the direction of conversion between two rational instantiations must be
 316 specified.
 317
 318 <h3><a name="Arithmetic operations">Arithmetic operations</a></h3>
 319 All of the standard numeric operators are defined for the <b>rational</b>
 320 class. These include:
 321 <br>
 322
 323 <pre>
 324     +    +=
 325     -    -=
 326     *    *=
 327     /    /=
 328     ++   --    (both prefix and postfix)
 329     ==   !=
 330     &lt;    &gt;
 331     &lt;=   &gt;=
 332
 333     Unary: + - !
 334 </pre>
 335
 336 <p>Since C++14, all of these operations are <code>constexpr</code>-enabled.
 337 In C++11, only <code>operator==</code>, <code>operator!=</code>,
 338 unary <code>operator+</code>, and <code>operator!</code> are.
 339
 340 <h3><a name="Input and Output">Input and Output</a></h3>
 341 Input and output operators <tt>&lt;&lt;</tt> and <tt>&gt;&gt;</tt>
 342 are provided. The external representation of a rational is
 343 two integers, separated by a slash (<tt>/</tt>). On input, the format must be
 344 exactly an integer, followed with no intervening whitespace by a slash,
 345 followed (again with no intervening whitespace) by a second integer. The
 346 external representation of an integer is defined by the underlying integer
 347 type.
 348
 349 <h3><a name="In-place assignment">In-place assignment</a></h3>
 350 For any <tt>rational&lt;I&gt; r</tt>, <tt>r.assign(n, m)</tt> provides an
 351 alternate to <tt>r = rational&lt;I&gt;(n, m);</tt>, without a user-specified
 352 construction of a temporary. While this is probably unnecessary for rationals
 353 based on machine integer types, it could offer a saving for rationals based on
 354 unlimited-precision integers, for example.
 355
 356 <p>The function will throw if the given components cannot be formed into a valid
 357 rational number.  Otherwise, it could throw only if the component-level move
 358 assignment (in C++11; copy-assignment for earlier C++ versions) can throw.  The
 359 strong guarantee is kept if throwing happens in the first part, but there is a
 360 risk of neither the strong nor basic guarantees happening if an exception is
 361 thrown during the component assignments.
 362
 363 <h3><a name="Conversions">Conversions</a></h3>
 364 <p>There is a conversion operator to an unspecified Boolean type (most likely a
 365 member pointer).  This operator converts a rational to <code>false</code> if it
 366 represents zero, and <code>true</code> otherwise.  This conversion allows a
 367 rational for use as the first argument of operator <code>?:</code>; as either
 368 argument of operators <code>&amp;&amp;</code> or <code>||</code> without
 369 forfeiting short-circuit evaluation; as a condition for a <code>do</code>,
 370 <code>if</code>, <code>while</code>, or <code>for</code> statement; and as a
 371 conditional declaration for <code>if</code>, <code>while</code>, or
 372 <code>for</code> statements.  The nature of the type used, and that any names
 373 for that nature are kept private, should prevent any inappropriate non-Boolean
 374 use like numeric or pointer operations or as a <code>switch</code> condition.
 375
 376 <p>There are <em>no other</em> implicit conversions from a rational
 377 type. Besides the explicit cross-version constructor template, there is an
 378 explicit type-conversion function, <tt>rational_cast&lt;T&gt;(r)</tt>. This can
 379 be used as follows:
 380
 381 <pre>
 382     rational&lt;int&gt; r(22,7);
 383     double nearly_pi = boost::rational_cast&lt;double&gt;(r);
 384 </pre>
 385
 386 <p>The <tt>rational_cast&lt;T&gt;</tt> function's behaviour is undefined if the
 387 source rational's numerator or denominator cannot be safely cast to the
 388 appropriate floating point type, or if the division of the numerator and
 389 denominator (in the target floating point type) does not evaluate correctly.
 390 Also, since this function has a custom name, it cannot be called in generic code
 391 for trading between two instantiations of the same class template, unlike the
 392 cross-version constructor.
 393
 394 <p>In essence, all required conversions should be value-preserving, and all
 395 operations should behave "sensibly". If these constraints cannot be met, a
 396 separate user-defined conversion will be more appropriate.
 397
 398 <p>Boolean conversion and <tt>rational_cast</tt> are <code>constexpr</code>-enabled.
 399
 400 <p><em>Implementation note:</em>
 401
 402 <p>The implementation of the rational_cast function was
 403
 404 <pre>
 405     template &lt;typename Float, typename Int&gt;
 406     Float rational_cast(const rational&lt;Int&gt;&amp; src)
 407     {
 408         return static_cast&lt;Float&gt;(src.numerator()) / src.denominator();
 409     }
 410 </pre>
 411
 412 Programs should not be written to depend upon this implementation, however,
 413 especially since this implementation is now obsolete.  (It required a mixed-mode
 414 division between types <var>Float</var> and <var>Int</var>, contrary to the <a
 415 href="#Integer%20Type%20Requirements">Integer Type Requirements</a>.)
 416
 417 <h3><a name="Numerator and Denominator">Numerator and Denominator</a></h3>
 418 Finally, access to the internal representation of rationals is provided by
 419 the two member functions <tt>numerator()</tt> and <tt>denominator()</tt>.
 420 These functions are <code>constexpr</code>-enabled.
 421
 422 <p>These functions allow user code to implement any additional required
 423 functionality. In particular, it should be noted that there may be cases where
 424 the above rational_cast operation is inappropriate - particularly in cases
 425 where the rational type is based on an unlimited-precision integer type. In
 426 this case, a specially-written user-defined conversion to floating point will
 427 be more appropriate.
 428
 429 <h2><a name="Performance">Performance</a></h2>
 430 The rational class has been designed with the implicit assumption that the
 431 underlying integer type will act "like" the built in integer types. The
 432 behavioural aspects of this assumption have been explicitly described above,
 433 in the <a href="#Integer%20Type%20Requirements">Integer Type Requirements</a>
 434 section. However, in addition to behavioural assumptions, there are implicit
 435 performance assumptions.
 436
 437 <p> No attempt will be made to provide detailed performance guarantees for the
 438 operations available on the rational class. While it is possible for such
 439 guarantees to be provided (in a similar manner to the performance
 440 specifications of many of the standard library classes) it is by no means
 441 clear that such guarantees will be of significant value to users of the
 442 rational class. Instead, this section will provide a general discussion of the
 443 performance characteristics of the rational class.
 444
 445 <p>There now follows a list of the fundamental operations defined in the
 446 <a href="../../boost/rational.hpp"> &lt;boost/rational.hpp&gt;</a> header
 447 and an informal description of their performance characteristics. Note that
 448 these descriptions are based on the current implementation, and as such should
 449 be considered subject to change.
 450
 451 <ul>
 452 <li>Construction of a rational is essentially just two constructions of the
 453 underlying integer type, plus a normalization.
 454
 455 <li>Increment and decrement operations are essentially as cheap as addition and
 456 subtraction on the underlying integer type.
 457
 458 <li>(In)equality comparison is essentially as cheap as two equality operations
 459 on the underlying integer type.
 460
 461 <li>I/O operations are not cheap, but their performance is essentially
 462 dominated by the I/O time itself.
 463
 464 <li>An (implicit) GCD routine call is essentially a repeated modulus operation.
 465 Its other significant operations are construction, assignment, and comparison
 466 against zero of IntType values. These latter operations are assumed to be
 467 trivial in comparison with the modulus operation.
 468
 469 <li>The (implicit) LCM operation is essentially a GCD plus a multiplication,
 470 division, and comparison.
 471
 472 <li>The addition and subtraction operations are complex. They will require
 473 approximately two gcd operations, 3 divisions, 3 multiplications and an
 474 addition on the underlying integer type.
 475
 476 <li>The multiplication and division operations require two gcd operations, two
 477 multiplications, and four divisions.
 478
 479 <li>The compare-with-integer operation does a single integer division &amp;
 480 modulus pair, at most one extra integer addition and decrement, and at most
 481 three integer comparisons.
 482
 483 <li>The compare-with-rational operation does two double-sized GCD operations,
 484 two extra additions and decrements, and three comparisons in the worst case.
 485 (The GCD operations are double-sized because they are done in piecemeal and the
 486 interim quotients are retained and compared, whereas a direct GCD function only
 487 retains and compares the remainders.)
 488
 489 <li>The final fundamental operation is normalizing a rational. This operation
 490 is performed whenever a rational is constructed (and assigned in place). All
 491 other operations are careful to maintain rationals in a normalized state.
 492 Normalization costs the equivalent of one gcd and two divisions.
 493 </ul>
 494
 495 <p>Note that it is implicitly assumed that operations on IntType have the
 496 "usual" performance characteristics - specifically, that the expensive
 497 operations are multiplication, division, and modulo, with addition and
 498 subtraction being significantly cheaper. It is assumed that construction (from
 499 integer literals 0 and 1, and copy construction) and assignment are relatively
 500 cheap, although some effort is taken to reduce unnecessary construction and
 501 copying. It is also assumed that comparison (particularly against zero) is
 502 cheap.
 503
 504 <p>Integer types which do not conform to these assumptions will not be
 505 particularly effective as the underlying integer type for the rational class.
 506 Specifically, it is likely that performance will be severely sub-optimal.
 507
 508 <h2><a name="Exceptions">Exceptions</a></h2>
 509 Rationals can never have a denominator of zero. (This library does not support
 510 representations for infinity or NaN). Should a rational result ever generate a
 511 denominator of zero, or otherwise fail during normalization, the exception
 512 <tt>boost::bad_rational</tt> (a subclass of <tt>std::domain_error</tt>) is
 513 thrown. This should only occur if the user attempts to explicitly construct a
 514 rational with a denominator of zero, to divide a rational by a zero value, or
 515 generate a negative denominator too large to be normalized.  The exception can
 516 be thrown during a cross-instantiation conversion, when at least one of the
 517 components ends up not being value-preserved and the new combination is not
 518 considered normalized.
 519
 520 <p>In addition, if operations on the underlying integer type can generate
 521 exceptions, these will be propagated out of the operations on the rational
 522 class. No particular assumptions should be made - it is only safe to assume
 523 that any exceptions which can be thrown by the integer class could be thrown
 524 by any rational operation. In particular, the rational constructor may throw
 525 exceptions from the underlying integer type as a result of the normalization
 526 step.  The only exception to this rule is that the rational destructor will
 527 only throw exceptions which can be thrown by the destructor of the underlying
 528 integer type (usually none).
 529
 530 <p>If the component-level assignment operator(s) can throw, then a rational
 531 object's invariants may be violated if an exception happens during the second
 532 component's assignment.  (The <code>assign</code> member function counts here
 533 too.)  This violates both the strong and basic guarantees.
 534
 535 <h2><a name="Internal representation">Internal representation</a></h2>
 536 <em>Note:</em> This information is for information only. Programs should not
 537 be written in such a way as to rely on these implementation details.
 538
 539 <p>Internally, rational numbers are stored as a pair (numerator, denominator)
 540 of integers (whose type is specified as the template parameter for the
 541 rational type). Rationals are always stored in fully normalized form (ie,
 542 gcd(numerator,denominator) = 1, and the denominator is always positive).
 543
 544 <h2><a name="Design notes">Design notes</a></h2>
 545 <h3><a name="Minimal Implementation">Minimal Implementation</a></h3>
 546 The rational number class is designed to keep to the basics. The minimal
 547 operations required of a numeric class are provided, along with access to the
 548 underlying representation in the form of the numerator() and denominator()
 549 member functions. With these building-blocks, it is possible to implement any
 550 additional functionality required.
 551
 552 <p>Areas where this minimality consideration has been relaxed are in providing
 553 input/output operators, and rational_cast. The former is generally
 554 uncontroversial. However, there are a number of cases where rational_cast is
 555 not the best possible method for converting a rational to a floating point
 556 value (notably where user-defined types are involved). In those cases, a
 557 user-defined conversion can and should be implemented. There is no need
 558 for such an operation to be named rational_cast, and so the rational_cast
 559 function does <em>not</em> provide the necessary infrastructure to allow for
 560 specialisation/overloading.
 561
 562 <h3><a name="Limited-range integer types">Limited-range integer types</a></h3>
 563 The rational number class is designed for use in conjunction with an
 564 unlimited precision integer class. With such a class, rationals are always
 565 exact, and no problems arise with precision loss, overflow or underflow.
 566
 567 <p>Unfortunately, the C++ standard does not offer such a class <s>(and neither
 568 does boost, at the present time)</s>. It is therefore likely that the rational
 569 number class will in many cases be used with limited-precision integer types,
 570 such as the built-in <tt>int</tt> type.
 571
 572 <p>When used with a limited precision integer type, the rational class suffers
 573 from many of the precision issues which cause difficulty with floating point
 574 types. While it is likely that precision issues will not affect simple uses of
 575 the rational class, users should be aware that such issues exist.
 576
 577 <p>As a simple illustration of the issues associated with limited precision
 578 integers, consider a case where the C++ <tt>int</tt> type is a 32-bit signed
 579 representation. In this case, the smallest possible positive
 580 rational&lt;int&gt; is <tt>1/0x7FFFFFFF</tt>. In other words, the
 581 "granularity" of the rational&lt;int&gt; representation around zero is
 582 approximately 4.66e-10. At the other end of the representable range, the
 583 largest representable rational&lt;int&gt; is <tt>0x7FFFFFFF/1</tt>, and the
 584 next lower representable rational&lt;int&gt; is <tt>0x7FFFFFFE/1</tt>. Thus,
 585 at this end of the representable range, the granularity ia 1. This type of
 586 magnitude-dependent granularity is typical of floating point representations.
 587 However, it does not "feel" natural when using a rational number class.
 588
 589 <p>Limited-precision integer types may raise issues with the range sizes of
 590 their allowable negative values and positive values.  If the negative range is
 591 larger, then the extremely-negative numbers will not have an additive inverse in
 592 the positive range, making them unusable as denominator values since they cannot
 593 be normalized to positive values (unless the user is lucky enough that the input
 594 components are not relatively prime pre-normalization).
 595
 596 <p>It is up to the user of a rational type based on a limited-precision integer
 597 type to be aware of, and code in anticipation of, such issues.
 598
 599 <h3><a name="Conversion from floating point">Conversion from floating point</a></h3>
 600 The library does not offer a conversion function from floating point to
 601 rational. A number of requests were received for such a conversion, but
 602 extensive discussions on the boost list reached the conclusion that there was
 603 no "best solution" to the problem. As there is no reason why a user of the
 604 library cannot write their own conversion function which suits their
 605 particular requirements, the decision was taken not to pick any one algorithm
 606 as "standard".
 607
 608 <p>The key issue with any conversion function from a floating point value is
 609 how to handle the loss of precision which is involved in floating point
 610 operations. To provide a concrete example, consider the following code:
 611
 612 <pre>
 613     // These two values could in practice be obtained from user input,
 614     // or from some form of measuring instrument.
 615     double x = 1.0;
 616     double y = 3.0;
 617
 618     double z = x/y;
 619
 620     rational&lt;I&gt; r = rational_from_double(z);
 621 </pre>
 622
 623 <p>The fundamental question is, precisely what rational should r be? A naive
 624 answer is that r should be equal to 1/3. However, this ignores a multitude of
 625 issues.
 626
 627 <p>In the first instance, z is not exactly 1/3. Because of the limitations of
 628 floating point representation, 1/3 is not exactly representable in any of the
 629 common representations for the double type. Should r therefore not contain an
 630 (exact) representation of the actual value represented by z? But will the user
 631 be happy with a value of 33333333333333331/100000000000000000 for r?
 632
 633 <p>Before even considering the above issue, we have to consider the accuracy
 634 of the original values, x and y. If they came from an analog measuring
 635 instrument, for example, they are not infinitely accurate in any case. In such
 636 a case, a rational representation like the above promises far more accuracy
 637 than there is any justification for.
 638
 639 <p>All of this implies that we should be looking for some form of "nearest
 640 simple fraction". Algorithms to determine this sort of value do exist.
 641 However, not all applications want to work like this. In other cases, the
 642 whole point of converting to rational is to obtain an exact representation, in
 643 order to prevent accuracy loss during a series of calculations. In this case,
 644 a completely precise representation is required, regardless of how "unnatural"
 645 the fractions look.
 646
 647 <p>With these conflicting requirements, there is clearly no single solution
 648 which will satisfy all users. Furthermore, the algorithms involved are
 649 relatively complex and specialised, and are best implemented with a good
 650 understanding of the application requirements. All of these factors make such
 651 a function unsuitable for a general-purpose library such as this.
 652
 653 <h3><a name="Absolute Value">Absolute Value</a></h3>
 654 In the first instance, it seems logical to implement
 655 abs(rational&lt;IntType&gt;) in terms of abs(IntType).
 656 However, there are a number of issues which arise with doing so.
 657
 658 <p>The first issue is that, in order to locate the appropriate implementation
 659 of abs(IntType) in the case where IntType is a user-defined type in a user
 660 namespace, Koenig lookup is required. Not all compilers support Koenig lookup
 661 for functions at the current time. For such compilers, clumsy workarounds,
 662 which require cooperation from the user of the rational class, are required to
 663 make things work.
 664
 665 <p>The second, and potentially more serious, issue is that for non-standard
 666 built-in integer types (for example, 64-bit integer types such as
 667 <em>long long</em> or <em>__int64</em>), there is no guarantee that the vendor
 668 has supplied a built in abs() function operating on such types. This is a
 669 quality-of-implementation issue, but in practical terms, vendor support for
 670 types such as <em>long long</em> is still very patchy.
 671
 672 <p>As a consequence of these issues, it does not seem worth implementing
 673 abs(rational&lt;IntType&gt;) in terms of abs(IntType). Instead, a simple
 674 implementation with an inline implementation of abs() is used:
 675
 676 <pre>
 677     template &lt;typename IntType&gt;
 678     inline rational&lt;IntType&gt; abs(const rational&lt;IntType&gt;&amp; r)
 679     {
 680         if (r.numerator() &gt;= IntType(0))
 681             return r;
 682
 683             return rational&lt;IntType&gt;(-r.numerator(), r.denominator());
 684     }
 685 </pre>
 686
 687 <p>The same arguments imply that where the absolute value of an IntType is
 688 required elsewhere, the calculation is performed inline.
 689
 690 <h2><a name="References">References</a></h2>
 691 <ul>
 692 <li>The rational number header itself: <a href="../../boost/rational.hpp">rational.hpp</a>
 693 <li>Some example code: <a href="test/rational_example.cpp">rational_example.cpp</a>
 694 <li>The regression test: <a href="test/rational_test.cpp">rational_test.cpp</a>
 695 </ul>
 696
 697 <h2><a name="History and Acknowledgements">History and Acknowledgements</a></h2>
 698
 699    <p>
 700       In December, 1999, I implemented the initial version of the rational number
 701       class, and submitted it to the <A HREF="http://www.boost.org/">boost.org</A>
 702       mailing list. Some discussion of the implementation took place on the mailing
 703       list. In particular, Andrew D. Jewell pointed out the importance of ensuring
 704       that the risk of overflow was minimised, and provided overflow-free
 705       implementations of most of the basic operations. The name rational_cast was
 706       suggested by Kevlin Henney. Ed Brey provided invaluable comments - not least
 707       in pointing out some fairly stupid typing errors in the original code!</p>
 708
 709    <p>David Abrahams contributed helpful feedback on the documentation.</p>
 710
 711    <p>
 712       A long discussion of the merits of providing a conversion from floating
 713       point to rational took place on the boost list in November 2000. Key
 714       contributors included Reggie Seagraves, Lutz Kettner and Daniel Frey (although
 715       most of the boost list seemed to get involved at one point or another!). Even
 716       though the end result was a decision <em>not</em> to implement anything, the
 717       discussion was very valuable in understanding the issues.
 718    </p>
 719
 720    <p>
 721       Stephen Silver contributed useful experience on using the rational class
 722       with a user-defined integer type.
 723    </p>
 724
 725    <p>
 726       Nickolay Mladenov provided the current implementation of operator+= and
 727       operator-=.
 728    </p>
 729    <p>
 730       Discussion of the issues surrounding Koenig lookup and std::swap took place
 731       on the boost list in January 2001.
 732    </p>
 733    <p>
 734       Daryle Walker provided a Boolean conversion operator, so that a rational can
 735       be used in the same Boolean contexts as the built-in numeric types, in December
 736       2005.  He added the cross-instantiation constructor template in August 2013.
 737    </p>
 738    <p>
 739    July 2014: Updated numerator/denominator accessors to return values by constant
 740    reference: this gives a performance improvement when using with multiprecision (class) types.
 741    </p>
 742    <p>
 743       July 2014: Updated to use BOOST_THROW_EXCEPTION uniformly throughout.
 744    </p>
 745    <p>
 746       July 2014: Added support for C++11 constexpr constructors, plus tests to match.
 747    </p>
 748    <p>
 749       Nov 2014: Added support for gcd and lcm of rational numbers.
 750    </p>
 751    <p>
 752       Dec 2016: Reworked constructors and operators to prohibit narrowing implicit
 753       conversions, in particular accidental conversion from floating point types.
 754    </p>
 755    <p>
 756       Oct/Nov 2018: Add more constexpr.
 757    </p>
 758
 759 <p>Revised July 14, 2017</p>
 760
 761 <p>&copy; Copyright Paul Moore 1999-2001; &copy; Daryle Walker 2005, 2013.
 762 Permission to copy, use, modify, sell and distribute this document is granted
 763 provided this copyright notice appears in all copies. This document is provided
 764 &quot;as is&quot; without express or implied warranty, and with no claim as to
 765 its suitability for any purpose.</p>
 766 <!-- boostinspect:nolicense (can't find Paul Moore to change license) -->
 767 </body>
 768 </html>