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