]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | class bad_rational; | |
50 | ||
51 | template<typename I> 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<typename J> | |
62 | constexpr explicit rational(const rational<J> &r); // Cross-instantiation | |
63 | ||
64 | // Normal copy constructors and assignment operators | |
65 | ||
66 | // Assignment from I | |
67 | rational& operator=(I n); | |
68 | ||
69 | // Assign in place | |
70 | rational& 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& operator+= (const rational& r); | |
81 | rational& operator-= (const rational& r); | |
82 | rational& operator*= (const rational& r); | |
83 | rational& operator/= (const rational& r); | |
84 | ||
85 | // Arithmetic with integers | |
86 | rational& operator+= (I i); | |
87 | rational& operator-= (I i); | |
88 | rational& operator*= (I i); | |
89 | rational& operator/= (I i); | |
90 | ||
91 | // Increment and decrement | |
92 | const rational& operator++(); | |
93 | const rational& 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< (const rational& r) const; | |
103 | constexpr bool operator== (const rational& r) const; | |
104 | ||
105 | // Comparison with integers | |
106 | bool operator< (I i) const; | |
107 | bool operator> (I i) const; | |
108 | constexpr bool operator== (I i) const; | |
109 | }; | |
110 | ||
111 | // Unary operators | |
112 | template <typename I> constexpr rational<I> operator+ (const rational<I>& r); | |
113 | template <typename I> rational<I> operator- (const rational<I>& r); | |
114 | ||
115 | // Reversed order operators for - and / between (types convertible to) I and rational | |
116 | template <typename I, typename II> inline rational<I> operator- (II i, const rational<I>& r); | |
117 | template <typename I, typename II> inline rational<I> operator/ (II i, const rational<I>& r); | |
118 | ||
119 | // Absolute value | |
120 | template <typename I> rational<I> abs (const rational<I>& r); | |
121 | ||
122 | // Input and output | |
123 | template <typename I> std::istream& operator>> (std::istream& is, rational<I>& r); | |
124 | template <typename I> std::ostream& operator<< (std::ostream& os, const rational<I>& r); | |
125 | ||
126 | // Type conversion | |
127 | template <typename T, typename I> constexpr T rational_cast (const rational<I>& 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<T>(rational<I>) 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<I></code> specialization must exist (and be | |
243 | visible before <code>boost::rational<I></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<></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<I> zero; | |
298 | rational<I> r1(n); | |
299 | rational<I> r2(n, d); | |
300 | rational<J> 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 | < > | |
330 | <= >= | |
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><<</tt> and <tt>>></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<I> r</tt>, <tt>r.assign(n, m)</tt> provides an | |
349 | alternate to <tt>r = rational<I>(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>&&</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<T>(r)</tt>. This can | |
377 | be used as follows: | |
378 | ||
379 | <pre> | |
380 | rational<int> r(22,7); | |
381 | double nearly_pi = boost::rational_cast<double>(r); | |
382 | </pre> | |
383 | ||
384 | <p>The <tt>rational_cast<T></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 <typename Float, typename Int> | |
404 | Float rational_cast(const rational<Int>& src) | |
405 | { | |
406 | return static_cast<Float>(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"> <boost/rational.hpp></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 & | |
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<int> is <tt>1/0x7FFFFFFF</tt>. In other words, the | |
579 | "granularity" of the rational<int> representation around zero is | |
580 | approximately 4.66e-10. At the other end of the representable range, the | |
581 | largest representable rational<int> is <tt>0x7FFFFFFF/1</tt>, and the | |
582 | next lower representable rational<int> 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<I> 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<IntType>) 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<IntType>) in terms of abs(IntType). Instead, a simple | |
672 | implementation with an inline implementation of abs() is used: | |
673 | ||
674 | <pre> | |
675 | template <typename IntType> | |
676 | inline rational<IntType> abs(const rational<IntType>& r) | |
677 | { | |
678 | if (r.numerator() >= IntType(0)) | |
679 | return r; | |
680 | ||
681 | return rational<IntType>(-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>© Copyright Paul Moore 1999-2001; © 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 | "as is" 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> |