The dedoublifier, part one

Good Monday morning everyone; I hope my American readers had a lovely Thanksgiving. I sure did!

Well enough chit-chat, here's a problem I was pondering the other day. We know that doubles introduce some "representation error" when trying to represent most numbers. The number 3/4, or 0.75 for example, can be exactly represented by a double, but the number 3/5, or 0.6, cannot.

To digress for a moment with a brief refresher: a double can be thought of as a fraction where the numerator is a 52 bit integer, and the denominator is a largish power of two. For the exact details, see the Wikipedia page on the subject or my old articles. Since 3/4 can clearly be represented by an integer divided by a power of two, it can be represented exactly. But there is no way to make 3/5 come out to have a power of two on the bottom.

Now, fortunately we have conversions from double to decimal, and from double to base-ten strings, that allow us to easily answer the question "what decimal fraction is this double close to?" The question I am pondering is: suppose we have a double which approximates some weird fraction with neither a power of two or ten in the denominator. 33/17 or 85/97 or whatever. Is there some way to easily get that fraction back out of the double?

We'll do this in four parts. In this first part I'll make a new helper class to extract the parts of a double; in the second part I'll make my own rational number type, and we'll finish up by proposing some algorithms that searche the space of rational numbers for the one that best matches a given double, and implementing one of them.

Long-time readers will know that I've solved the first problem before, back in 2011. But today I am excited to try out some of the code-shortening features of C# 6.0. So let's get right into it:

struct DoubleHelper{ public DoubleHelper(double d) { this.RawBits = (ulong)BitConverter.DoubleToInt64Bits(d); } public ulong RawBits { get; } // RawSign is 1 if zero or negative, 0 if zero or positive public int RawSign => (int)(RawBits >> 63); public int RawExponent => (int)(RawBits >> 52) & 0x7FF; public long RawMantissa => (long)(RawBits & 0x000FFFFFFFFFFFFF); public bool IsNaN => RawExponent == 0x7ff && RawMantissa != 0; public bool IsInfinity => RawExponent == 0x7ff && RawMantissa == 0; public bool IsZero => RawExponent == 0 && RawMantissa == 0; public bool IsDenormal => RawExponent == 0 && RawMantissa != 0; // Sign is 1 if positive, -1 if negative, 0 if zero public int Sign => IsZero ? 0 : 1 - RawSign * 2; public long Mantissa => IsZero || IsDenormal || IsNaN || IsInfinity ? RawMantissa : RawMantissa | 0x0010000000000000; public int Exponent { get { if (IsZero) return 0; else if (IsDenormal) return -1074; else if (IsNaN || IsInfinity) return RawExponent; else return RawExponent - 1075; } }}

You know, I was initially skeptical of the => syntax for simple read-only properties, but I really like this. With just these few lines of code I can now analyze a double both in terms of what the raw bit fields are, and be smart about figuring out the meaning of the sign, exponent and mantissa parts.

Next time on FAIC: we'll use this little helper to implement arbitrary precision rational numbers.