Binary question

[electroRF]

hi,
I'd appreciate your help

You're given a decimal number, i.e. 0.625, and you need to either:
- print its binary represenation
OR
- print ERROR if it can't be represeneted in binary

How can you tell if a number can't be represented in binary?

for example, 0.625 can be represented in binary : 1 / 2^1 + 1 / 2^3

But, 0.1 can't.

Thank you.

 

[misterT]

Are you saying that the decimal number is given as a string, and you need to convert that to IEEE standard floating point and print its binary presentation? And "error" if the given string can't be exactly converted to IEEE floating point?

 

[electroRF]

hi T,
Yes, the decimal number is given in string..
They did not state in which format to present in binary.

I think that's not the main part, because you can choose to present it any way you like, isn't it?

The tough part is taking the fractional part of the number, and decide whether it can't or can be represented in binary.

 

[misterT]

The tough part is taking the fractional part of the number, and decide whether it can't or can be represented in binary.

Fast answer to that is: Take the fractional part and keep myltiplying it by two. If you do not end up with an integer number "soon enough" (how many fractional bits you have), then the number can not be presented exactly in binary.

That method is also the key to finding the binary presentation of the number. I don't have time to write more at the moment. Also I would like to get more specs before writing any actual algorithms.. or is this a school assignment?

 

[misterT]

quick example, Convert:
3.625

Integer part in binary:
11

Fractional part:
Take fractional part and multiply by 2:
0.625 * 2 = 1.25 // this is over one, so the first fractional bit is 1

Take fractional part from previous result and multiply by two:
0.25 * 2 = 0.5 // This is less than one, the second fractional bit is 0

Again, take fractional part and myltiply by two:
0.5 * 2 = 1 // Equal to one, The third fractional bit is 1, end of algorithm.

Final binary presentation:
11.101

From that it should not be very hard to construct an IEEE compliant float.

The most "code intensive" part is probably working with the string (you need to write the algorithm so that it does the math in string format, or some clever data structure, so that you do not lose precision).

 

[NorthGuy]

You will not always reach the point where it is equal 1.

0.1*2 = 0.2 // bit 0
0.2*2 = 0.4 // bit 0
0.4*2 = 0.8 // bit 0
0.8*2 = 1.6 // bit 1
0.6*2 = 1.2 // bit 1
0.2*2 = 0.4 // bit 0

The last line is the same a line #2, so you go into a loop which runs forever
0.00011001100110011 ...

 

[misterT]

I was thinking about using the math with strings. I think this is quite simple and efficient way.

Assume you have string:
"3.625"

This is a char array:
char str[] = {'3', '.', '6', '2', '5', '\0'};

Convert the fractional part to an integer array:
int fract[3];

fract[0] = (int)(str[2] - '0'); // subtract ASCII '0', to convert character to integer value
fract[1] = (int)(str[3] - '0');
fract[2] = (int)(str[4] - '0');

Now you have an integer array with values:
{6, 2, 5}

You can multiply that by 2 element by element:

int carry = 0;

fract[2] += fract[2] + carry;
carry = 0;
if (fract[2] > 9){  // check for carry
    carry = 1;
    fract[2] -= 10;
}

fract[1] += fract[1] + carry;
carry = 0;
if (fract[1] > 9){  // check for carry
    carry = 1;
    fract[1] -= 10;
}

fract[0] += fract[0] + carry;
carry = 0;
if (fract[0] > 9){  // check for carry
    carry = 1;
    fract[0] -= 10;
}

return carry;

It is easy to write that in a general function which returns the next fractional bit of your floating point binary presentation. Repeat calling the function until all the array elements are zero, or certain number of calls (precision limit) has been reached (to you this would be the "error" case).

 

[misterT]

The function would be something like:

int array_multiply_by_two(int *fract, int length){
    int carry = 0;

    while(length){

        length--;
        fract[length] += fract[length] + carry;

        carry = 0;
        if (fract[length] > 9){  // check for carry
            carry = 1;
            fract[length] -= 10;
        }
    }
    return carry;
}

 

[NorthGuy]

The easier way to convert is to disregard the decimal point, convert to an integer, then convert it to float and divide by 10, 100, 1000 depending on where the decimal point was.

 

[misterT]

The easier way to convert is to disregard the decimal point, convert to an integer, then convert it to float and divide by 10, 100, 1000 depending on where the decimal point was.

Yeah, sure. That assumes that you already have a floating point library that (more or less) does the things I explained

Easiest way is to use the standard "atof()" -library function. Then convert the float back to string using "sprintf()" and see if it matches with the original string, if not, then you lost precision.

 

[electroRF]

Guys,
Thank you very much.

T, I appreciate so much your posts! they are very helpful!

I suspected that there isn't really a way to tell that a decimal number can't be represented in binary without getting a precision limit, right?

 

[misterT]

I suspected that there isn't really a way to tell that a decimal number can't be represented in binary without getting a precision limit, right?

NorthGuy explained one method in post #6. If you get in a loop with the algorithm, then you know there is no way you can represent the number in binary (because the representation would require infinite number of bits).
There should be an analytical way to find out, but I have to think about that more.

 

[NorthGuy]

I suspected that there isn't really a way to tell that a decimal number can't be represented in binary without getting a precision limit, right?

Take some big enough number 2^N. For simplicity, make N a number of decimal digits multiplied by four. Then multiply your number by 2^N. If what you get is integer it can. If it's fractional it cannot.

 

[misterT]

Take some big enough number 2^N. For simplicity, make N a number of decimal digits multiplied by four. Then multiply your number by 2^N. If what you get is integer it can. If it's fractional it cannot.

Yes, but you are setting a precision limit N there. I think what electroRF wondered was that how to find out if that limit N exists for a given decimal number.

 

[NorthGuy]

Yes, but you are setting a precision limit N there. I think what electroRF wondered was that how to find out if that limit N exists for a given decimal number.

The precision is set by the number of decimal digits. I'm just trying to convert it into binary. 4x limit for N is definitely too much. In fact, 1x would work.

Say, you have 1 decimal digit. Only 0.0 and 0.5 have binary presentation. If you multiply by 2^1, you get 0 and 1 respectively. Everything else is fractional.

With 2 decimal digits. Only 0.00, 0.25, 0.50 and 0.75 have representation. If you multiply by 2^2 = 2, you get 0, 1, 2 and 4. Everything else is fractionl.

3 digits. 0.000, 0.125, 0.250, 0.375, 0.500, 0.625, 0. 750, 0.875. If you mutiply by 2^3 = 8 these and only these numbers will become integer.

And so on ...

 

[misterT]

Yes, that is correct NorthGuy. The answer was so simple that I did not see it at first

So, if your decimal number "x" has "N" fractional digits and you multiply the decimal number:
x * 2^N

If the result is not an integer, then the decimal number can't be presented exactly in floating point binary.

 

[electroRF]

So nice solution

thank you NG ant T!

 

[misterT]

I found a really great website full of this stuff.
https://www.exploringbinary.com/topics/

 

[electroRF]

Awesome! thank you