6.2. Rational numbers (class rational)

Learning objectives

The class rational

Rational numbers are used excessively in geometry. Actually, they are used wherever exact computation is needed and no higher algebraic operations such as extracting exact square roots are involved. LEDA accommodates this need by providing the class rational.

An object of type rational represents a rational number, that is, it has an (integer) numerator and an (integer) denominator. Numerator and denominator are of arbitrary length. Just as the class integer, this class provides all usual arithmetic operators such as +, -, *, /, and %, so that rationals can be used in all usual arithmetic C++ expressions.

As a (non-geometrical) application of rational, we compute the value of a continued fraction. A continued fraction is a representation of a real number in the form

where all ai are non-negative integer numbers. Each continued fraction is a representation of a (positive) real number and each (positive) real number has a continued fraction representation. These representations are very common in number theory.

For example, the continued fraction

where all ai are equal to 1 is the representation of the number Φ = (1+√5)/2 = 1.61803...[44] , the Golden Ratio, a number that is very important in the art world, where it has been considered since ancient times to be the most pleasing ratio for many kinds of design ([7]). Furthermore, Φ frequently occurs in number theory; for example, the ratio Fn+1/Fn of two consecutive Fibonacci numbers is known to converge to Φ.

The following program uses the above continued fraction representation to approximate Φ.

Filename: ContinuedFraction.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#include <LEDA/rational.h>

using leda::rational;
using std::cout;
using std::endl;

int main()
{
  rational r(1,1);

  while(1) {
    cout << r << " is approx. " << r.to_float() << endl;
    r = 1 + 1 / r;
  }
}

The program outputs

1/1 is approx. 1
2/1 is approx. 2
3/2 is approx. 1.5
5/3 is approx. 1.66667
8/5 is approx. 1.6
13/8 is approx. 1.625
21/13 is approx. 1.61538
34/21 is approx. 1.61905
55/34 is approx. 1.61765
89/55 is approx. 1.61818
144/89 is approx. 1.61798
233/144 is approx. 1.61806
377/233 is approx. 1.61803
610/377 is approx. 1.61804
987/610 is approx. 1.61803
1597/987 is approx. 1.61803
...

As we can see, this approximation converges quite fast to Φ. Furthermore, the numerators (and denominators) exactly constitute the sequence of Fibonacci numbers.

The program shows how easy it is to use the class rational. A rational is created by specifying its numerator and denominator in the constructor:

rational r( integer n, integer d );

A rational can be created also from a double:

rational r( double d );

This initializes r to have the same value as d, where “value” means the quotient of the numerator and the denominator.

Numerator and denominator of a rational can be accessed via

integer r.numerator();
integer r.denominator();

In long computations, the numerators and denominators of rational numbers tend to become quite huge, so sometimes it may be worthwhile to normalize intermediate results. This is achieved by

rational& r.normalize();

which returns a (reference to a) normalized rational, that is, whose numerator and denominator are relatively prime.

Normalization is done internally by calling Euclid's algorithm to find a common factor. If, however, a common factor f is known a priori, a rational can also be simplified by

rational& r.simplify( const integer& f );

which returns (a reference to) the simplified rational.

[Important]Important

LEDA's rational numbers are not necessarily normalized, that is, the numerator and denominator of a rational may have one or more common factors. If the numerators and/or denominators of the rational numbers involved in a computation become too large, they can be shortened by calling normalize() or simplify().

To yield a floating point approximation of a rational, the method

double r.to_float();

can be used.

Further information and tips

The class rational has some other useful methods, for example, for negating and inverting rationals, for turning them into strings, for computing roots and powers of rationals, and for rounding them to the nearest integer.

A description of all these methods and more information on the class rational can be found on the corresponding manual page.

LEDA's rationals are about 30-100 times slower than double, but much faster than algebraic real numbers. They should be used if exact arithmetic for rational numbers is needed and no exact higher algebraic operations are involved.

Exercises

Exercise 78.

A general continued fraction is a continued fraction in which the numerators not necessarily have to be equal to 1, but are allowed to be any non-negative integer.

For example, Leonhard Euler discovered the following identity:

where e is Euler's number 2.71828...

Write a program to approximate e using the above formula.

Exercise 79.

Write a program that inputs a rational number x and computes the continued fraction representation of x.

Hint: Use the function floor(r), which returns the nearest integer that is smaller than the rational r.

Then feed in a rational approximation of Euler's number, whose first 25 digits are 2,718281828459045235360287. Can you detect a pattern?

Exercise 80.

Write a program to solve systems of linear equations using Gaussian elimination. Use rational numbers as the underlying type. Make several versions of the program: In one version, keep all intermediate results normalized by calling normalize() after each arithmetic operation involving a rational. In a second version, make no attempt to keep the numbers normalized. In a third version, normalize all entries of the residual matrix only after some numbers of eliminations and/or when the numerators and denominators exceed a certain size.

Solve large systems of linear equations and try to determine the fastest strategy.

Also implement Gaussian elimination with floating point arithmetic (using C++'s double). Solve systems Ax=b in which the entries ai,j of A have the values i+j. These are ill conditioned systems and should lead to unusable results with floating point arithmetic. Use rational arithmetics to compute the exact result.



[44] That is easy to see: Just solve the quadratic equation Φ = 1 + 1 / Φ.




Imprint-Dataprotection