1
$\begingroup$

I'm reading a book which says that to transform a number from decimal representation to binary representation you have to follow these steps:

  1. Take the integer part (the one before the point) of the number and transform it in binary like you normally do with integer numbers: that is the integer part of the binary representation of the number we are trying to convert.
  2. Take the decimal part (the one after the point) of the original number and multiply it by 2, the integer part of the obtained number is a digit (the current one) of the decimal part of the binary number.
  3. Repeat step 2 until:
    • You got 0 as the decimal part of the obtained number.
    • Obtained numbers start to repeat, in that case the number is periodic.

At the end you should get the binary transformation of the original number.

I tried to apply the algorithm to the number: 0,264 and got:

  • 0,264 (dec part) -> 0,264 * 2 = 0,528

  • 0,528 (dec part) -> 0,528 * 2 = 1,056

  • 1,056 (dec part) -> 0,056 * 2 = 0,112

  • 0,112 (dec part) -> 0,112 * 2 = 0,224

  • 0,224 (dec part) -> 0,224 * 2 = 0,448

  • 0,448 (dec part) -> 0,448 * 2 = 0,896

  • 0,896 (dec part) -> 0,896 * 2 = 1,792

  • 1,792 (dec part) -> 0,792 * 2 = 1,584

  • 1,584 (dec part) -> 0,584 * 2 = 1,168

  • 1,168 (dec part) -> 0,168 * 2 = 0,336

  • 0,336 (dec part) -> 0,336 * 2 = 0,672

  • 0,672 (dec part) -> 0,672 * 2 = 1,344

  • 1,344 (dec part) -> 0,344 * 2 = 0,688

  • 0,688 (dec part) -> 0,688 * 2 = 1,376

  • 1,376 (dec part) -> 0,376 * 2 = 0,752

  • 0,752 (dec part) -> 0,752 * 2 = 1,504

  • 1,504 (dec part) -> 0,504 * 2 = 1,008

  • 1,008 (dec part) -> 0,008 * 2 = 0,016

    ......

... And so on.

As you can see neither we found just 0 as the decimal part of the numbers we got, neither these numbers started to repeat.

Nevertheless, trying to convert 0,264 using this online converter gets the following: 0,01000011100101011, which stops one step before where I stopped in the algorithm calculation I showed in this question.

So I was wondering:

  • Why does it stop there? Are there other criteria for stopping in the algorithm?
  • Am I getting the algorithm wrong?

I think it may have something to do with precision you want to get, but then what should be the correct criteria for stopping?

$\endgroup$
1
  • $\begingroup$ The title of the post does not reflect the question. $\endgroup$
    – user16034
    Apr 3 at 15:23

2 Answers 2

2
$\begingroup$

No, you have not done anything wrong.

However, you have not done enough. You have done step 2 for 18 times. You will have to repeat step 2 for another 82 times. Then you will observe that the "obtained numbers start to repeat".

The binary representation of $0.264$ is $$0.\underline{0100001110010101100000010000011000100100110111010010111100011010100111111011111001110110110010001011}$$ where I use the underline to indicate the first shortest period, which turns out to be the first 100 binary digits right after the decimal separator.

This large value of period length is more of a norm than an outlier. Here is a list of the lengths of the periods in the binary representations of a few decimal factions.

decimal fraction length of periods in its binary representation
0.6 4
0.06 20
0.006 100
0.0006 500
0.0006 2500

You might have noticed a few patterns in the table above. I will leave them for you to explore, discover, verify and extend.


Why does it stop there?

That website cuts off the computation of the binary digits at some arbitrary length. Or that is what appears to me. A different website or tool may choose a different cut-off point, such as this one.

You can stop the algorithm at any time you prefer. If you would like to run the algorithm entirely, follow step 3. It is an algorithm after all.

$\endgroup$
0
$\begingroup$

If you want IEEE 64 bit floating point numbers, you need 53 mantissa bits. If the integer part is non-zero and has k bits, you need 53-k bits from the fractional part. If the integer part is zero, then you ignore the initial zero bits from the fractional part, and you need 53 bits starting with the first non-zero bit.

When you are done, the remaining fractional part is used to round the result correctly. Less than 0.5 means unchanged, greater than 0.5 means you round up, and exactly 0.5 means you round so that the last bit becomes zero.

You need to handle numbers >= 2^53, and the number zero. If you have number like 1.2345678901234567890e-300 this will take ages; you can convert the fractional part to base 10^9 and do 30 steps at a time by multiplying by 2^30, making the operation 270 times faster. For large numbers like 1.2345678901234567890e300 you can convert the whole digit string to base 10^9 and divide by 2^30 as often as needed.

PS. The pattern must repeat. You had three digits. There are only 1000 possibilities to have three digits. So after 1001 iterations you must have repeated one combination, and from then in the pattern repeats. If you had 20 digits it might take a very long time until it repeats.

For conversion to binary floating point the pattern is actually not relevant.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.