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     constexpr rational();          // Zero
  59     constexpr rational(I n);       // Equal to n/1
  60               rational(I n, I d);  // General case (n/d)
  61    template&lt;typename J&gt;
  62     constexpr explicit rational(const rational&lt;J&gt; &amp;r);  // Cross-instantiation
  63
  64     // Normal copy constructors and assignment operators
  65
  66     // Assignment from I
  67     rational&amp; operator=(I n);
  68
  69     // Assign in place
  70     rational&amp; assign(I n, I d);
  71
  72     // Representation
  73     constexpr I numerator() const;
  74     constexpr I denominator() const;
  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);
  81     rational&amp; operator-= (const rational&amp; r);
  82     rational&amp; operator*= (const rational&amp; r);
  83     rational&amp; operator/= (const rational&amp; r);
  84
  85     // Arithmetic with integers
  86     rational&amp; operator+= (I i);
  87     rational&amp; operator-= (I i);
  88     rational&amp; operator*= (I i);
  89     rational&amp; operator/= (I i);
  90
  91     // Increment and decrement
  92     const rational&amp; operator++();
  93     const rational&amp; operator--();
  94
  95     // Operator not
  96     constexpr bool operator!() const;
  97
  98     // Boolean conversion
  99     constexpr operator bool_type() const;
 100
 101     // Comparison operators
 102               bool operator&lt; (const rational&amp; r) const;
 103     constexpr bool operator== (const rational&amp; r) const;
 104
 105     // Comparison with integers
 106               bool operator&lt; (I i) const;
 107               bool operator&gt; (I i) const;
 108     constexpr bool operator== (I i) const;
 109 };
 110
 111 // Unary operators
 112 template &lt;typename I&gt; constexpr rational&lt;I&gt; operator+ (const rational&lt;I&gt;&amp; r);
 113 template &lt;typename I&gt;           rational&lt;I&gt; operator- (const rational&lt;I&gt;&amp; r);
 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);
 117 template &lt;typename I, typename II&gt; inline rational&lt;I&gt; operator/ (II i, const rational&lt;I&gt;&amp; r);
 118
 119 // Absolute value
 120 template &lt;typename I&gt; rational&lt;I&gt; abs (const rational&lt;I&gt;&amp; r);
 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; constexpr T rational_cast (const rational&lt;I&gt;&amp; r);
 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>The no-argument constructor, single-argument constructor, and cross-version
 304 constructor template are marked as <code>constexpr</code>, making them viable in
 305 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).
 308
 309 <p>The single-argument constructor is <em>not</em> declared as explicit, so
 310 there is an implicit conversion from the underlying integer type to the
 311 rational type.  The two-argument constructor can be considered an implicit
 312 conversion with C++11's uniform initialization syntax, since it is also not
 313 declared explicit.  The cross-version constructor template is declared explicit,
 314 so the direction of conversion between two rational instantiations must be
 315 specified.
 316
 317 <h3><a name="Arithmetic operations">Arithmetic operations</a></h3>
 318 All of the standard numeric operators are defined for the <b>rational</b>
 319 class. These include:
 320 <br>
 321
 322 <pre>
 323     +    +=
 324     -    -=
 325     *    *=
 326     /    /=
 327     ++   --    (both prefix and postfix)
 328     ==   !=
 329     &lt;    &gt;
 330     &lt;=   &gt;=
 331
 332     Unary: + - !
 333 </pre>
 334
 335 <p>So far, only <code>operator ==</code>, unary <code>operator +</code>, and
 336 <code>operator !</code> are <code>constexpr</code>-enabled.
 337
 338 <h3><a name="Input and Output">Input and Output</a></h3>
 339 Input and output operators <tt>&lt;&lt;</tt> and <tt>&gt;&gt;</tt>
 340 are provided. The external representation of a rational is
 341 two integers, separated by a slash (<tt>/</tt>). On input, the format must be
 342 exactly an integer, followed with no intervening whitespace by a slash,
 343 followed (again with no intervening whitespace) by a second integer. The
 344 external representation of an integer is defined by the undelying integer
 345 type.
 346
 347 <h3><a name="In-place assignment">In-place assignment</a></h3>
 348 For any <tt>rational&lt;I&gt; r</tt>, <tt>r.assign(n, m)</tt> provides an
 349 alternate to <tt>r = rational&lt;I&gt;(n, m);</tt>, without a user-specified
 350 construction of a temporary. While this is probably unnecessary for rationals
 351 based on machine integer types, it could offer a saving for rationals based on
 352 unlimited-precision integers, for example.
 353
 354 <p>The function will throw if the given components cannot be formed into a valid
 355 rational number.  Otherwise, it could throw only if the component-level move
 356 assignment (in C++11; copy-assignment for earlier C++ versions) can throw.  The
 357 strong guarantee is kept if throwing happens in the first part, but there is a
 358 risk of neither the strong nor basic guarantees happening if an exception is
 359 thrown during the component assignments.
 360
 361 <h3><a name="Conversions">Conversions</a></h3>
 362 <p>There is a conversion operator to an unspecified Boolean type (most likely a
 363 member pointer).  This operator converts a rational to <code>false</code> if it
 364 represents zero, and <code>true</code> otherwise.  This conversion allows a
 365 rational for use as the first argument of operator <code>?:</code>; as either
 366 argument of operators <code>&amp;&amp;</code> or <code>||</code> without
 367 forfeiting short-circuit evaluation; as a condition for a <code>do</code>,
 368 <code>if</code>, <code>while</code>, or <code>for</code> statement; and as a
 369 conditional declaration for <code>if</code>, <code>while</code>, or
 370 <code>for</code> statements.  The nature of the type used, and that any names
 371 for that nature are kept private, should prevent any inappropriate non-Boolean
 372 use like numeric or pointer operations or as a <code>switch</code> condition.
 373
 374 <p>There are <em>no other</em> implicit conversions from a rational
 375 type. Besides the explicit cross-version constructor template, there is an
 376 explicit type-conversion function, <tt>rational_cast&lt;T&gt;(r)</tt>. This can
 377 be used as follows:
 378
 379 <pre>
 380     rational&lt;int&gt; r(22,7);
 381     double nearly_pi = boost::rational_cast&lt;double&gt;(r);
 382 </pre>
 383
 384 <p>The <tt>rational_cast&lt;T&gt;</tt> function's behaviour is undefined if the
 385 source rational's numerator or denominator cannot be safely cast to the
 386 appropriate floating point type, or if the division of the numerator and
 387 denominator (in the target floating point type) does not evaluate correctly.
 388 Also, since this function has a custom name, it cannot be called in generic code
 389 for trading between two instantiations of the same class template, unlike the
 390 cross-version constructor.
 391
 392 <p>In essence, all required conversions should be value-preserving, and all
 393 operations should behave "sensibly". If these constraints cannot be met, a
 394 separate user-defined conversion will be more appropriate.
 395
 396 <p>Boolean conversion and <tt>rational_cast</tt> are <code>constexpr</code>-enabled.
 397
 398 <p><em>Implementation note:</em>
 399
 400 <p>The implementation of the rational_cast function was
 401
 402 <pre>
 403     template &lt;typename Float, typename Int&gt;
 404     Float rational_cast(const rational&lt;Int&gt;&amp; src)
 405     {
 406         return static_cast&lt;Float&gt;(src.numerator()) / src.denominator();
 407     }
 408 </pre>
 409
 410 Programs should not be written to depend upon this implementation, however,
 411 especially since this implementation is now obsolete.  (It required a mixed-mode
 412 division between types <var>Float</var> and <var>Int</var>, contrary to the <a
 413 href="#Integer%20Type%20Requirements">Integer Type Requirements</a>.)
 414
 415 <h3><a name="Numerator and Denominator">Numerator and Denominator</a></h3>
 416 Finally, access to the internal representation of rationals is provided by
 417 the two member functions <tt>numerator()</tt> and <tt>denominator()</tt>.
 418 These functions are <code>constexpr</code>-enabled.
 419
 420 <p>These functions allow user code to implement any additional required
 421 functionality. In particular, it should be noted that there may be cases where
 422 the above rational_cast operation is inappropriate - particularly in cases
 423 where the rational type is based on an unlimited-precision integer type. In
 424 this case, a specially-written user-defined conversion to floating point will
 425 be more appropriate.
 426
 427 <h2><a name="Performance">Performance</a></h2>
 428 The rational class has been designed with the implicit assumption that the
 429 underlying integer type will act "like" the built in integer types. The
 430 behavioural aspects of this assumption have been explicitly described above,
 431 in the <a href="#Integer%20Type%20Requirements">Integer Type Requirements</a>
 432 section. However, in addition to behavioural assumptions, there are implicit
 433 performance assumptions.
 434
 435 <p> No attempt will be made to provide detailed performance guarantees for the
 436 operations available on the rational class. While it is possible for such
 437 guarantees to be provided (in a similar manner to the performance
 438 specifications of many of the standard library classes) it is by no means
 439 clear that such guarantees will be of significant value to users of the
 440 rational class. Instead, this section will provide a general discussion of the
 441 performance characteristics of the rational class.
 442
 443 <p>There now follows a list of the fundamental operations defined in the
 444 <a href="../../boost/rational.hpp"> &lt;boost/rational.hpp&gt;</a> header
 445 and an informal description of their performance characteristics. Note that
 446 these descriptions are based on the current implementation, and as such should
 447 be considered subject to change.
 448
 449 <ul>
 450 <li>Construction of a rational is essentially just two constructions of the
 451 underlying integer type, plus a normalization.
 452
 453 <li>Increment and decrement operations are essentially as cheap as addition and
 454 subtraction on the underlying integer type.
 455
 456 <li>(In)equality comparison is essentially as cheap as two equality operations
 457 on the underlying integer type.
 458
 459 <li>I/O operations are not cheap, but their performance is essentially
 460 dominated by the I/O time itself.
 461
 462 <li>An (implicit) GCD routine call is essentially a repeated modulus operation.
 463 Its other significant operations are construction, assignment, and comparison
 464 against zero of IntType values. These latter operations are assumed to be
 465 trivial in comparison with the modulus operation.
 466
 467 <li>The (implicit) LCM operation is essentially a GCD plus a multiplication,
 468 division, and comparison.
 469
 470 <li>The addition and subtraction operations are complex. They will require
 471 approximately two gcd operations, 3 divisions, 3 multiplications and an
 472 addition on the underlying integer type.
 473
 474 <li>The multiplication and division operations require two gcd operations, two
 475 multiplications, and four divisions.
 476
 477 <li>The compare-with-integer operation does a single integer division &amp;
 478 modulus pair, at most one extra integer addition and decrement, and at most
 479 three integer comparisons.
 480
 481 <li>The compare-with-rational operation does two double-sized GCD operations,
 482 two extra additions and decrements, and three comparisons in the worst case.
 483 (The GCD operations are double-sized because they are done in piecemeal and the
 484 interim quotients are retained and compared, whereas a direct GCD function only
 485 retains and compares the remainders.)
 486
 487 <li>The final fundamental operation is normalizing a rational. This operation
 488 is performed whenever a rational is constructed (and assigned in place). All
 489 other operations are careful to maintain rationals in a normalized state.
 490 Normalization costs the equivalent of one gcd and two divisions.
 491 </ul>
 492
 493 <p>Note that it is implicitly assumed that operations on IntType have the
 494 "usual" performance characteristics - specifically, that the expensive
 495 operations are multiplication, division, and modulo, with addition and
 496 subtraction being significantly cheaper. It is assumed that construction (from
 497 integer literals 0 and 1, and copy construction) and assignment are relatively
 498 cheap, although some effort is taken to reduce unnecessary construction and
 499 copying. It is also assumed that comparison (particularly against zero) is
 500 cheap.
 501
 502 <p>Integer types which do not conform to these assumptions will not be
 503 particularly effective as the underlying integer type for the rational class.
 504 Specifically, it is likely that performance will be severely sub-optimal.
 505
 506 <h2><a name="Exceptions">Exceptions</a></h2>
 507 Rationals can never have a denominator of zero. (This library does not support
 508 representations for infinity or NaN). Should a rational result ever generate a
 509 denominator of zero, or otherwise fail during normalization, the exception
 510 <tt>boost::bad_rational</tt> (a subclass of <tt>std::domain_error</tt>) is
 511 thrown. This should only occur if the user attempts to explicitly construct a
 512 rational with a denominator of zero, to divide a rational by a zero value, or
 513 generate a negative denominator too large to be normalized.  The exception can
 514 be thrown during a cross-instantiation conversion, when at least one of the
 515 components ends up not being value-preserved and the new combination is not
 516 considered normalized.
 517
 518 <p>In addition, if operations on the underlying integer type can generate
 519 exceptions, these will be propagated out of the operations on the rational
 520 class. No particular assumptions should be made - it is only safe to assume
 521 that any exceptions which can be thrown by the integer class could be thrown
 522 by any rational operation. In particular, the rational constructor may throw
 523 exceptions from the underlying integer type as a result of the normalization
 524 step.  The only exception to this rule is that the rational destructor will
 525 only throw exceptions which can be thrown by the destructor of the underlying
 526 integer type (usually none).
 527
 528 <p>If the component-level assignment operator(s) can throw, then a rational
 529 object's invariants may be violated if an exception happens during the second
 530 component's assignment.  (The <code>assign</code> member function counts here
 531 too.)  This violates both the strong and basic guarantees.
 532
 533 <h2><a name="Internal representation">Internal representation</a></h2>
 534 <em>Note:</em> This information is for information only. Programs should not
 535 be written in such a way as to rely on these implementation details.
 536
 537 <p>Internally, rational numbers are stored as a pair (numerator, denominator)
 538 of integers (whose type is specified as the template parameter for the
 539 rational type). Rationals are always stored in fully normalized form (ie,
 540 gcd(numerator,denominator) = 1, and the denominator is always positive).
 541
 542 <h2><a name="Design notes">Design notes</a></h2>
 543 <h3><a name="Minimal Implementation">Minimal Implementation</a></h3>
 544 The rational number class is designed to keep to the basics. The minimal
 545 operations required of a numeric class are provided, along with access to the
 546 underlying representation in the form of the numerator() and denominator()
 547 member functions. With these building-blocks, it is possible to implement any
 548 additional functionality required.
 549
 550 <p>Areas where this minimality consideration has been relaxed are in providing
 551 input/output operators, and rational_cast. The former is generally
 552 uncontroversial. However, there are a number of cases where rational_cast is
 553 not the best possible method for converting a rational to a floating point
 554 value (notably where user-defined types are involved). In those cases, a
 555 user-defined conversion can and should be implemented. There is no need
 556 for such an operation to be named rational_cast, and so the rational_cast
 557 function does <em>not</em> provide the necessary infrastructure to allow for
 558 specialisation/overloading.
 559
 560 <h3><a name="Limited-range integer types">Limited-range integer types</a></h3>
 561 The rational number class is designed for use in conjunction with an
 562 unlimited precision integer class. With such a class, rationals are always
 563 exact, and no problems arise with precision loss, overflow or underflow.
 564
 565 <p>Unfortunately, the C++ standard does not offer such a class <s>(and neither
 566 does boost, at the present time)</s>. It is therefore likely that the rational
 567 number class will in many cases be used with limited-precision integer types,
 568 such as the built-in <tt>int</tt> type.
 569
 570 <p>When used with a limited precision integer type, the rational class suffers
 571 from many of the precision issues which cause difficulty with floating point
 572 types. While it is likely that precision issues will not affect simple uses of
 573 the rational class, users should be aware that such issues exist.
 574
 575 <p>As a simple illustration of the issues associated with limited precision
 576 integers, consider a case where the C++ <tt>int</tt> type is a 32-bit signed
 577 representation. In this case, the smallest possible positive
 578 rational&lt;int&gt; is <tt>1/0x7FFFFFFF</tt>. In other words, the
 579 "granularity" of the rational&lt;int&gt; representation around zero is
 580 approximately 4.66e-10. At the other end of the representable range, the
 581 largest representable rational&lt;int&gt; is <tt>0x7FFFFFFF/1</tt>, and the
 582 next lower representable rational&lt;int&gt; is <tt>0x7FFFFFFE/1</tt>. Thus,
 583 at this end of the representable range, the granularity ia 1. This type of
 584 magnitude-dependent granularity is typical of floating point representations.
 585 However, it does not "feel" natural when using a rational number class.
 586
 587 <p>Limited-precision integer types may raise issues with the range sizes of
 588 their allowable negative values and positive values.  If the negative range is
 589 larger, then the extremely-negative numbers will not have an additive inverse in
 590 the positive range, making them unusable as denominator values since they cannot
 591 be normalized to positive values (unless the user is lucky enough that the input
 592 components are not relatively prime pre-normalization).
 593
 594 <p>It is up to the user of a rational type based on a limited-precision integer
 595 type to be aware of, and code in anticipation of, such issues.
 596
 597 <h3><a name="Conversion from floating point">Conversion from floating point</a></h3>
 598 The library does not offer a conversion function from floating point to
 599 rational. A number of requests were received for such a conversion, but
 600 extensive discussions on the boost list reached the conclusion that there was
 601 no "best solution" to the problem. As there is no reason why a user of the
 602 library cannot write their own conversion function which suits their
 603 particular requirements, the decision was taken not to pick any one algorithm
 604 as "standard".
 605
 606 <p>The key issue with any conversion function from a floating point value is
 607 how to handle the loss of precision which is involved in floating point
 608 operations. To provide a concrete example, consider the following code:
 609
 610 <pre>
 611     // These two values could in practice be obtained from user input,
 612     // or from some form of measuring instrument.
 613     double x = 1.0;
 614     double y = 3.0;
 615
 616     double z = x/y;
 617
 618     rational&lt;I&gt; r = rational_from_double(z);
 619 </pre>
 620
 621 <p>The fundamental question is, precisely what rational should r be? A naive
 622 answer is that r should be equal to 1/3. However, this ignores a multitude of
 623 issues.
 624
 625 <p>In the first instance, z is not exactly 1/3. Because of the limitations of
 626 floating point representation, 1/3 is not exactly representable in any of the
 627 common representations for the double type. Should r therefore not contain an
 628 (exact) representation of the actual value represented by z? But will the user
 629 be happy with a value of 33333333333333331/100000000000000000 for r?
 630
 631 <p>Before even considering the above issue, we have to consider the accuracy
 632 of the original values, x and y. If they came from an analog measuring
 633 instrument, for example, they are not infinitely accurate in any case. In such
 634 a case, a rational representation like the above promises far more accuracy
 635 than there is any justification for.
 636
 637 <p>All of this implies that we should be looking for some form of "nearest
 638 simple fraction". Algorithms to determine this sort of value do exist.
 639 However, not all applications want to work like this. In other cases, the
 640 whole point of converting to rational is to obtain an exact representation, in
 641 order to prevent accuracy loss during a series of calculations. In this case,
 642 a completely precise representation is required, regardless of how "unnatural"
 643 the fractions look.
 644
 645 <p>With these conflicting requirements, there is clearly no single solution
 646 which will satisfy all users. Furthermore, the algorithms involved are
 647 relatively complex and specialised, and are best implemented with a good
 648 understanding of the application requirements. All of these factors make such
 649 a function unsuitable for a general-purpose library such as this.
 650
 651 <h3><a name="Absolute Value">Absolute Value</a></h3>
 652 In the first instance, it seems logical to implement
 653 abs(rational&lt;IntType&gt;) in terms of abs(IntType).
 654 However, there are a number of issues which arise with doing so.
 655
 656 <p>The first issue is that, in order to locate the appropriate implementation
 657 of abs(IntType) in the case where IntType is a user-defined type in a user
 658 namespace, Koenig lookup is required. Not all compilers support Koenig lookup
 659 for functions at the current time. For such compilers, clumsy workarounds,
 660 which require cooperation from the user of the rational class, are required to
 661 make things work.
 662
 663 <p>The second, and potentially more serious, issue is that for non-standard
 664 built-in integer types (for example, 64-bit integer types such as
 665 <em>long long</em> or <em>__int64</em>), there is no guarantee that the vendor
 666 has supplied a built in abs() function operating on such types. This is a
 667 quality-of-implementation issue, but in practical terms, vendor support for
 668 types such as <em>long long</em> is still very patchy.
 669
 670 <p>As a consequence of these issues, it does not seem worth implementing
 671 abs(rational&lt;IntType&gt;) in terms of abs(IntType). Instead, a simple
 672 implementation with an inline implementation of abs() is used:
 673
 674 <pre>
 675     template &lt;typename IntType&gt;
 676     inline rational&lt;IntType&gt; abs(const rational&lt;IntType&gt;&amp; r)
 677     {
 678         if (r.numerator() &gt;= IntType(0))
 679             return r;
 680
 681             return rational&lt;IntType&gt;(-r.numerator(), r.denominator());
 682     }
 683 </pre>
 684
 685 <p>The same arguments imply that where the absolute value of an IntType is
 686 required elsewhere, the calculation is performed inline.
 687
 688 <h2><a name="References">References</a></h2>
 689 <ul>
 690 <li>The rational number header itself: <a href="../../boost/rational.hpp">rational.hpp</a>
 691 <li>Some example code: <a href="test/rational_example.cpp">rational_example.cpp</a>
 692 <li>The regression test: <a href="test/rational_test.cpp">rational_test.cpp</a>
 693 </ul>
 694
 695 <h2><a name="History and Acknowledgements">History and Acknowledgements</a></h2>
 696
 697 In December, 1999, I implemented the initial version of the rational number
 698 class, and submitted it to the <A HREF="http://www.boost.org/">boost.org</A>
 699 mailing list. Some discussion of the implementation took place on the mailing
 700 list. In particular, Andrew D. Jewell pointed out the importance of ensuring
 701 that the risk of overflow was minimised, and provided overflow-free
 702 implementations of most of the basic operations. The name rational_cast was
 703 suggested by Kevlin Henney. Ed Brey provided invaluable comments - not least
 704 in pointing out some fairly stupid typing errors in the original code!
 705
 706 <p>David Abrahams contributed helpful feedback on the documentation.
 707
 708 <p>A long discussion of the merits of providing a conversion from floating
 709 point to rational took place on the boost list in November 2000. Key
 710 contributors included Reggie Seagraves, Lutz Kettner and Daniel Frey (although
 711 most of the boost list seemed to get involved at one point or another!). Even
 712 though the end result was a decision <em>not</em> to implement anything, the
 713 discussion was very valuable in understanding the issues.
 714
 715 <p>Stephen Silver contributed useful experience on using the rational class
 716 with a user-defined integer type.
 717
 718 <p>Nickolay Mladenov provided the current implementation of operator+= and
 719 operator-=.
 720
 721 <p>Discussion of the issues surrounding Koenig lookup and std::swap took place
 722 on the boost list in January 2001.
 723
 724 <p>Daryle Walker provided a Boolean conversion operator, so that a rational can
 725 be used in the same Boolean contexts as the built-in numeric types, in December
 726 2005.  He added the cross-instantiation constructor template in August 2013.
 727
 728 <p>Revised August 30, 2013</p>
 729
 730 <p>&copy; Copyright Paul Moore 1999-2001; &copy; Daryle Walker 2005, 2013.
 731 Permission to copy, use, modify, sell and distribute this document is granted
 732 provided this copyright notice appears in all copies. This document is provided
 733 &quot;as is&quot; without express or implied warranty, and with no claim as to
 734 its suitability for any purpose.</p>
 735 <!-- boostinspect:nolicense (can't find Paul Moore to change license) -->
 736 </body>
 737 </html>