How to detect if a base 10 decimal can be represented exactly in base 2

Question

As part of a numerical library test I need to choose base 10 decimal numbers that can be represented exactly in base 2. How do you detect in C++ if a base 10 decimal number can be represented exactly in base 2?

My first guess is as follows:

bool canBeRepresentedInBase2(const double &pNumberInBase10)
{
    //check if a number in base 10 can be represented exactly in base 2
    //reference: http://en.wikipedia.org/wiki/Binary_numeral_system
    bool funcResult = false;

    int nbOfDoublings = 16*3;
    double doubledNumber = pNumberInBase10;
    for (int i = 0; i < nbOfDoublings ; i++)
    {
     doubledNumber = 2*doubledNumber;
     double intPart;
     double fracPart = modf(doubledNumber/2, &intPart);
     if (fracPart == 0) //number can be represented exactly in base 2
     {
      funcResult = true;
      break;
     }
    }
    return funcResult;
}

I tested this function with the following values: -1.0/4.0, 0.0, 0.1, 0.2, 0.205, 1.0/3.0, 7.0/8.0, 1.0, 256.0/255.0, 1.02, 99.005. It returns true for -1.0/4.0, 0.0, 7.0/8.0, 1.0, 99.005 which is correct.

Any better ideas?

Answer 1

If you're checking to see if it's binary, it will always return true. If your method takes a double as the parameter, the number is already represented in binary (double is a binary type, usually 64 bits). Looking at your code, I think you're actually trying to see if it can be represented exactly as an integer, in which case why can't you just cast to int, then back to double and compare to the original. Any integer stored in a double that's within the range representable by an int should be exact, IIRC, because a 64 bit double has 53 bits of mantissa (and I'm assuming a 32 bit int). That means if they're equal, it's an integer.

Answer 2

Or even easier:

return pNumber == floor(pNumber);

On the other hand, if you have some weird fractional representation (numerator denominator pair, or string with a decimal in it, or something), and you really do want to know if the value can be exactly represented as a double, it's a bit harder.

But you would need a different parameter(s) for that...

Answer 3

As rmeador have pointed out, it might not be a good idea to accept the double, because the number has been converted to a double, an possible approximation to the number that you're trying to check.

So, in a very abstract way, you should split your check into integers, and decimals. Integers should not be too large such that the mantissa cannot express all the integers, (e.g. 9007199254740993 should not be represented properly by a 64-bit fp) Decimal points may be a bit easier, mentally, because if anything after the decimal point (e.g. yyy in xxx.yyy) contains a factor of anything other than 2, the floating point repeats in order to try to represent it. It's the reason why 1/3 cannot be represented with finite digits in base 10 = base (2*5)... See Recurring Decimal

EDIT: As the comments pointed out, if the decimal number has a factor of anything other than 1/2, that would be the mathematically correct way to say it...

Answer 4

I don't think this is what he's asking... I think he's looking for a solution that will tell him if a number can be represented EXACTLY in binary form. For example, 33.3.. That's a number cannot be represented in binary, because it will go on forever, so depending on your FPU settings, it will be represented as something like "33.333333333333336". So, it looks like his method will do the job. I don't know of a better way off the top of my head. \

Answer 5

I think what you are looking for is a number which has a fractional portion which is the sum of a sequence of negative powers of 2 (aka: 1 over a power of 2). I believe this should always be able to be represented exactly in IEEE floats/doubles.

For example:

0.375 = (1/4 + 1/8) which should have an exact representation.

If you want to generate these. You could try do something like this:

#include <iostream>
#include <cstdlib>

int main() {
    srand(time(0));
    double value = 0.0;
    for(int i = 1; i < 256; i *= 2) {
        // doesn't matter, some random probability of including this
        // fraction in our sequence..
        if((rand() % 3) == 0) {
            value += (1.0 / static_cast<double>(i));     
        }
    }
    std::cout << value << std::endl;
}

EDIT: I believe your function has a broken interface. It would be better if you had this:

bool canBeRepresentedExactly(int numerator, int denominator);

because not all fractions have exact representations, but the moment you shove it into a double, you've chosen a representation in binary... defeating the purpose of the test.

Answer 6

As others have mentioned, your method doesn't do what you mean, since you pass a number represented as a (binary) double. The method actually detects, if the number you passed is in the form integer/2^48. This should fail for numbers like (1+2^-50), which is binary, and 259/255, which isn't.

If you really want to test a number for being exactly representable by finite binary string, you have to pass a number in an exact form.

Answer 7

If you're passing in a double, then by definition, it has already been represented in binary and if not, then you've already lost accuracy.

Maybe try passing in numerator and denominator of the fraction to the function. Then you have not lost accuracy and can check to see if you can come up with a binary representation of the answer that is the same as the fraction you've passed in.

Answer 8

You asked for C++ but maybe this algorithm will help. I use "EE" to mean "exactly expressible as a float."

Start with a decimal representation of the number you want to test. Remove any trailing zeroes (that is, 0.123450000 becomes 0.12345).

1) If the number is not an integer, check to see if the rightmost digit is 5. If it's not, then stop -- the number is not EE. 2) Multiply the number by 2. If the result is an integer, then stop -- the number is EE. Otherwise, go back to step 1.

I don't have rigorous proof for this but a "warm fuzzy." Fire up Calculator and enter your favorite fractional power of 2, like 0.0000152587890625. Add it to itself a few dozen times (I just hit "+" once then "=" a bunch of times). If there are any non-zero digits to the right of the decimal point, the last digit is always 5.

Answer 9

You can't pass IN a Double because it's already lost precision. You should be able to use the toString() method of Double to check for this. (example in Java)

public static Boolean canBeRepresentedInBase2(String thenumber)
{
    // Reuturns true of the parsed Double did not loose precision.
    // Only works for numbers that are not converted into scientific notation by toString.
    return thenumber.equals(Double.parseDouble(thenumber).toString())
}

Answer 10

Given a number r it can be represented exactly with finite precision in base 2 iff r can be written as r = m/2^n, where m, n are integers, and n >= 0.

For example 1/7 doesn't have a finite binary expression, also 1/6 and 1/10 can't be written with a finite expression in base 2.

But 1/4+1/32+1/1024, have a finite expression in base.

PS: In general you can express a number r with finite digits in a base b iff r=m/b^n where m, n are integers an n >= 0.

PPS: As almost everybody has stated previously using a double as input is a bad idea, because you are loosing precision, and you will end up with a different number.

Answer 11

Ignoring the general criticism of using a double... For a general finite decimal, you can determine if it has a finite representation in binary with the following algorithm:

1. Extract the fraction part of the decimal.
2. Determine fraction*10^b = c, where b and c are integers.
3. Determine 2^d>=10^b, where d is an integer
4. If c*2^b/10^b is an integer, then the decimal has a finite representation in binary. Otherwise, it doesn't.

You can generalize this to any two bases.

Answer 12

Here is the code in C# and it works. Because it works with the Decimal data - there are no inherent rounding errors that show up in the original code which uses double. (decimal in C# stores using base 10 instead of base 2 - which is what double does)

static bool canBeRepresentedInBase2(decimal pNumberInBase10)
{
 //check if a number in base 10 can be represented exactly in base 2
 //reference: http://en.wikipedia.org/wiki/Binary_numeral_system
 bool funcResult = false;

 int nbOfDoublings = 16*3;
 decimal doubledNumber = pNumberInBase10;
 for (int i = 0; i < nbOfDoublings ; i++)
 {
  doubledNumber = 2*doubledNumber;
  decimal intPart;
  decimal fracPart = ModF(doubledNumber/2, out intPart);
  if (fracPart == 0) //number can be represented exactly in base 2
  {
    funcResult = true;
    break;
  }
 }
 return funcResult;
}

static decimal ModF(decimal number, out decimal intPart)
{
 intPart = Math.Floor(number);
 decimal fractional = number - (intPart);
 return fractional;
}

Tested with the following code (where WL does a Console.WritelLine - SnippetCompiler) WL(canBeRepresentedInBase2(-1.0M/4.0M)); //true WL(canBeRepresentedInBase2(0.0M)); //true WL(canBeRepresentedInBase2(0.1M)); //false WL(canBeRepresentedInBase2(0.2M)); //false WL(canBeRepresentedInBase2(0.205M)); //false WL(canBeRepresentedInBase2(1.0M/3.0M)); //false WL(canBeRepresentedInBase2(7.0M/8.0M)); //true WL(canBeRepresentedInBase2(1.0M)); //true WL(canBeRepresentedInBase2(256.0M/255.0M)); //false WL(canBeRepresentedInBase2(1.02M)); //false WL(canBeRepresentedInBase2(99.005M)); //false WL(canBeRepresentedInBase2(2.53M)); //false