Fractionizer

C++ class to convert floating point values to fractions, by using continued fractions.

Usage

#include "fractionizer.h"
#include "print_float.h"

double val = 22.345;
double num;   // numerator
double denom; // denominator
Fractionizer::fractionize(val, num, denom);
std::cout << "22.345 == " << Print_float::print(num) << '/' << Print_float::print(denom) << std::endl;

One could also use increased precision (e.g. long double):

long double num, denom;
Fractionizer::fractionize(22.345L, num, denom);

How does it work?

How this works is best shown by an example:

The continued fraction has only integer whole numbers, that can be expressed in a vector:

As a formula-equation, the generation of continued fractions can be expressed as:

(with frac(x) as shown here)

As can be seen from the formula-equation above, given a number :
If this number is not yet an integer (whole number)

• we truncate the number, so that we get an integer (whole number):
  and then

• calculate the reciprocal of the fractional part , to get the next number
  and recursion…​

We end, when we get a that is a whole number.

This gives as a vector of whole numbers:

representing a continued fraction:

So much for idealized math.

But given a computers floating point with limited precision (float, double, long double), the program calculates the resulting value of the continued fraction, at each new and compares it to

The program stops, when we are close enough to .

Comments

Printing floating point numbers, so that the text (when read back in) is equivalent to the original floating point number, is not as easy as it seems.
This roundtrip (floating number to text and back to floating number) can be tested nicely as follows:

double num  = 22.345;
double num2;
assert((std::istringstream(Print_float::print(num)) >> num2) && (num == num2));

This uses Print_float::print() (ref), which will always print a floating point number correctly, so that the roundtrip works!
The clue is to use oss << std::setprecision(std::numeric_limits<Tfl>::max_digits10) (ref) as documented here.

Caution

The code currently uses

      do {
         // ...
      }
      //while (std::abs((Fractionizer::calc_frac<Tfl>(vec, num, denom) - val)/val) > numeric_limits<Tfl>::min());
      while (Fractionizer::calc_frac<Tfl>(vec, num, denom) != val);

(ref)
Up till now, the loop has always ended nicely. But I have no proof that it is safe, and it might be better to use some threshold comparision (the comment shows a possibility). If you can provide an example where the loop will not end, or furnish a proof that it will always end, then please let me know!

For the real weirdness of floating point, try this:

long double num, denom;
Fractionizer::fractionize<long double>(22.345, num, denom);  // 22.345 converted to long double parameter

Here I get 98274476749292.L/4398052215229.L Thus 22.345 as a double is so skew (since a double is stored as binary with limited precision); that converting it to long double leads to a different long double, than 22.345L:

assert(static_cast<long double>(22.345) != 22.345L);
std::cout << Print_float::print(static_cast<long double>(22.345) - 22.345L) << std::endl; // -1.13624387676480864684e-15L on my machine (x86_64-linux-gnu, compiled with gcc g++)

But there is a way of converting double 22.345 to long double, that favours numbers as being small fractions.

  long double num, denom;
  Fractionizer::fractionize(22.345, num, denom);
  assert(static_cast<long double>(num/denom) == 22.345L); /* "exact" and interesting method
                                                             of converting double to long double
                                                             Prefers "smaller" fractions */

Using computer calculators (PARI/GP and Calc)

PARI/GP

http://pari.math.u-bordeaux.fr

apt-get install pari-gp

Use e.g.

echo "1+2*3" | gp -f -q   -s 60M   -D realprecision=100

bestappr function

Use bestappr to get fraction approximations, with the given realprecision.

echo "bestappr(22.345)" | gp -f -q   -s 60M   -D realprecision=100

where gp --help shows

### Usage: gp [options] [GP files]
Available options:
[-f,--fast]	     Fast start: do not read .gprc
[-q,--quiet]	     Quiet mode: do not print banner and history numbers
[-s stacksize]	     Start with the PARI stack of given size (in bytes)
...

(so -f causes gp to start, without reading .gprc and without reading /etc/gprc)

and man gp shows

   -D, --default key=val
       performs default(key, val); on startup, overriding values from the gprc preferences file. 'val' must be a constant value and is not
       allowed to involve any computation (e.g. 1+1 is forbidden). Any number of such default-setting statements may appear on the command
       line.

With PARI/GP, you can use much higher precision, than what a normal long double gives you. Try:

echo "bestappr(7.402001334000000000000000000000000001)" | gp -f -q -s 60M -D realprecision=38
echo "bestappr(7.402001334000000000000000000000000001)" | gp -f -q -s 60M -D realprecision=100
echo "bestappr(7.402001334000000000000000000000000001)" | gp -f -q -s 60M -D realprecision=120
echo "bestappr(7.402001334000000000000000000000000001)" | gp -f -q -s 60M -D realprecision=136

contfrac function

Use contfrac to get the continous fraction whole-numbers (with the given realprecision).

echo "contfrac(7.402001334000000000000000000000000001)" | gp -f -q -s 60M -D realprecision=38
echo "contfrac(7.402001334000000000000000000000000001)" | gp -f -q -s 60M -D realprecision=100
echo "contfrac(7.402001334000000000000000000000000001)" | gp -f -q -s 60M -D realprecision=120
echo "contfrac(7.402001334000000000000000000000000001)" | gp -f -q -s 60M -D realprecision=136

Calc

http://www.isthe.com/chongo/tech/comp/calc/

apt-get install apcalc

Use e.g.

calc -p 'c=config("mode", "frac"); 7.402001334000000000000000000000000001'

See also

• cfc - a continued fraction calculator

• Boost

• Notes from the PBC Library

• Wikipedia

• Rosetta