Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
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"

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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