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