Decimals to fractions: JK iterative algorithm casting problem in C++

42 Views Asked by At

I'm working in a small personal project to keep practice and decided to code John Kennedy's iterative algorithm. The idea is to have a class Fraction(long, long) and a function Fraction doubleToFraction(double)

The issue: Z is a Real number (double) and D, N are integer (long).

Basic code is:

do
    {
        z = 1.0 / (z - floor(z));
        Di = denominator;
        denominator = Di * floor(z) + previousDenominator;

        previousNumerator = numerator;
        numerator = round(value * denominator);

        previousDenominator = Di;

        diff = abs(numerator / denominator - value);
        zdiff = abs(z - floor(z));
    }
    while (diff > maxError && zdiff > maxError);

Then I worked around the 3rd eq casting issue, making denominator and numerator long and checking for overflow:

    double z = value;
    long previousDenominator = 0, previousNumerator = 0;
    long denominator = 1;
    long numerator = 0, Di = 0;
    double diff, zdiff;

    do
    {
        z = 1.0 / (z - floor(z));
        Di = denominator;
        denominator = Di * floor(z) + previousDenominator;

        previousNumerator = numerator;
        numerator = round(value * denominator);

        if(numerator < 0){  //checks overflow
            numerator = previousNumerator;
            denominator = Di;
            break;
        }

        previousDenominator = Di;

        diff = abs(numerator / denominator - value);
        zdiff = abs(z - floor(z));
    }
    while (diff > maxError && zdiff > maxError);

But this only works if it doesn't fail the first iteration, and if Di * floor(z) doesn't overflow. Trying to use only double pushes the problem to the end of the algorithm:

    }
    while (diff > maxError && zdiff > maxError);

    if(max(numerator,denominator) > LONG_MAX){
        double comm = floor(max(numerator,denominator) / LONG_MAX);
        numerator = floor(numerator/comm);
        denominator = ceil(denominator/comm);
    }

    return Fraction((long)numerator * sign, (long)denominator);

But the difference between the fraction returned and the one it should is very big. Maybe this snippet can be improved?

Any ideas to solve this casting problem are welcome :)

PS: the last number giving me trouble is 944.00000000351042. For that number, z is 284866021.83457476 and denominator = 284866021 on the first iteration. Then, numerator = 268913523825 which is bigger than LONG_MAX, and since it fails on the first iteration returns Fraction(0,1). I could keep maxError below or equal to 1e-8 but then I could face the same problem with another number that gives me a bigger numerator than LONG_MAX on the first iteration. I want to keep maxError as smaller as possible.

PS2: I just found that 4865998.0002105972 has the same problem... now I would need to take maxError below 1e-3 T_T

0

There are 0 best solutions below