# Decimal Floating Point to Shortest Binary

Might be more of a Comp Sci question so apologies if it's not appropriate.

Basically I have a range bounded by two floating-point decimals <1. I need to find a short binary number lying between them.

For example: [.665811575, .6658289)

My method is to choose the shortest decimal number in the interval (.66582) and apply the following algorithm:

If >=0.5 write down "1" and subtract 0.5
Else if < 0.5 write down "0"
Multiply by 2
Repeat until number is 0.0


This works however the shortest decimal leads to quite a long binary number. A script I wrote spat out a 53 bit binary number. This is an exam question so I don't have time to do 53 iterations of the algorithm.

Does anyone know how I can pick a better number from the range which will lead to a shorter binary number? Or maybe you have a better approach?

Thanks

-
Why don't you convert each endpoint to binary in parallel. After each step, see if your two binary numbers disagree; if they do then you're almost done. –  vadim123 May 5 '13 at 17:07
I'd imagine this would work too but it's a bit more effort when in an exam situation. Thanks though –  carlmango11 May 5 '13 at 17:33

If I recall correctly, your method is near what I'd suggest.

If > 1, write '1' subtract 1, else write 0

Multiply by 2

You want accuracy to 1 in 100000, or 2^17 (131,072) so I believe 17 digits after decimal should do it. It may very well be an infinite non-repeating series, so I'd quit after either X iterations (the 17 I suggest) or until the a less than x less than b is favorable. The '0' may never occur.

Note to readers, it's been a long time since I've written any code. An edit would be appreciated, as I think this is pretty close.

It turns out 18 is correct for this question, (please verify)

.101010100111001011

equals

0.665813446044921875

which is between .665811 and .665828

-
So following this method can I just stop after 17 bits (or whatever power of two provides enough accuracy)? I don't have to keep going until I end up with 0 or anything? –  carlmango11 May 5 '13 at 17:13
I believe so. Perhaps 18. Because 1/(2^17) should get you greater accuracy than the difference of the two number you pose. Zero may never happen. –  JoeTaxpayer May 5 '13 at 17:15
I just tested it out. Stopping after 17 iterations works perfectly but I'll do an extra one in the exam to be safe. Thanks a lot! –  carlmango11 May 5 '13 at 17:32
@carlmango11 - Glad to help. I loved this stuff back in school. –  JoeTaxpayer May 5 '13 at 17:36

a=.665811575; b=.6658289

print "0."

while (b<=.5 or a>.5) {

if (b<=.5) { print "0"; a=2*a; b=2*b; }

else { print "1"; a=2*a-1; b=2*b-1; }

}

print "1"

-
I see how this works, but when does it terminate? –  JoeTaxpayer May 5 '13 at 17:17