File Rational.h

↰ Parent directory (ADS/numeric)

The exact rational numbers of Knuth (4.5.1), beyond the book: a fraction u / u’ of integers of any length [see File BigInteger.h] kept in lowest terms, with u’ > 0.

Definition (ADS/numeric/Rational.h)

Detailed Description

The sum and the product reduce by the greatest common divisors of the smaller numbers, as Henrici suggested, instead of by that of the result: for u / u’ + v / v’, with :math:` d_1 = gcd( u’ , v’ ) , the numerator is :math: t = u ( v’ / d_1 ) + v ( u’ / d_1 ) ` and, with :math:` d_2 = gcd( t , d_1 ) , the result is :math: ( t / d_2 ) / ( ( u’ / d_1 ) ( v’ / d_2 ) ) , already in lowest terms; for the product, :math: d_1 = gcd( u , v’ ) ` and :math:` d_2 = gcd( u’ , v ) ` cancel crosswise. Since :math:` d_1 = 1 ` with probability about :math:` 6 / pi^2 , the second gcd is most often skipped; a division by a gcd of 1 is skipped too, each quotient is computed once, by the exact division of Hensel when the gcd has one digit [see BigInteger::divExact()], the sum of the two products is made in place, and the gcds are those of Lehmer [see :ref:`file_ADS_numeric_BigInteger.h], one folded remainder when a denominator has one digit.

The contracts [see File Contract.h]: the denominator and a divisor are not 0; the invariant is u’ > 0 and :math:` gcd( u , u’ ) = 1 `, an audit. The operations are defined in Rational.tpp.

    1. Knuth, The Art of Computer Programming, vol. 2, 3rd ed., Addison-Wesley, 1998, section 4.5.1

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes