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