The dedoublifier, part three
All right, we have an arbitrary-precision rational arithmetic type now, so we can do arithmetic on fractions with confidence. Remember the problem I set out to explore here was: a double is actually a fraction whose denominator is a large power of two, so fractions which do not have powers of two in their denominators cannot be represented with full fidelity by a double. Now that we have this machinery we can see exactly what the representation error is:
Console.WriteLine(Rational.FromDouble(2.0 / 5.0));
This program fragment produces the output
3602879701896397/9007199254740992
Clearly that is not 2/5, but how close is it?
Console.WriteLine(Rational.FromDouble(2.0 / 5.0) - Rational.FromIntegers(2, 5));
The result is astonishing:
1/45035996273704960
People often point out that doubles introduce representation error but seldom do they quantify that error. In this case the error is less than one part in 45 quadrillion. That's a tiny error! And yet of course we can all think of situations where that error has compounded to the point where we expect $0.15 to be output and instead we get $0.1499999999. As I've often said, use decimals for currency computations.
Rounding problems aside, a lot of work has gone into making sure that doubles can be "round tripped" back to decimal strings when need be. But what if we have some more unusual fraction? Suppose we've done some computations in doubles and the result is the double closest to five sevenths:
Console.WriteLine(Rational.FromDouble(5.0 / 7.0));Console.WriteLine(Rational.FromDouble(5.0 / 7.0) - Rational.FromIntegers(5, 7));
This produces
6433713753386423/90071992547409921/63050394783186944
The question then is: suppose we have that double in hand. How do we get back out the fact that this is probably intended to be five sevenths?
You're all computer programmers. Give it some thought before you read on. To make the problem easier let us suppose without loss of generality that the double we've been given is between zero and one.
.
.
.
Probably a bunch of different thoughts occurred to you.
We could start by computing each fraction: 1.0/2.0, 1.0/3.0, 2.0/3.0, 1.0/4.0, " and so on. Compare each fraction to the target, keep track of the current closest fraction, and pick the fraction that is closest after a certain number of rationals go by. Unfortunately this gets inefficient as the denominators get large; there are too many fractions to check.
We could multiply the double by 2.0, 3.0, 4.0, 5.0, and so on, and see if any of the results are close to a whole number. If we multiply by 7.0 and get something close to 5.0 then it was 5 / 7. This seems more efficient, and in fact we could code up a solution that uses either of these techniques even without our rational number type; they can be done entirely in fast double arithmetic.
You probably also thought "can I use a divide and conquer strategy?" Binary search and related strategies are well known for their ability to rapidly converge on a correct solution.
Unfortunately a straight-up binary search of the rationals does not solve our problem. Imagine we have 6433713753386423 / 9007199254740992 in hand and we are searching for the fraction of small denominator that it "really" is. It does us no good to say:
- It's between 0 and 1. Let's try 1/2.
- It is bigger than 1/2.
- Let's split the difference and try 3/4.
- It is smaller than 3/4.
- Let's split the difference and try 5/8.
- "
Binary search in this manner does not actually hit all the fractions, and in fact only hits those that we are specifically trying to avoid: those with powers of two in the denominator!
However, there is a way to binary-search the space of rational numbers between zero and one that does hit all of them. Next time on FAIC: we'll use it to solve our problem.
