# Shortest binary number in range

Given two arbitrarily precise decimal numbers 0 ≤ x < y ≤ 1, compute the shortest (in digits) binary number b such that xb < y.

Output the binary digits of b after the binary point as an array or a string of zeroes and ones. Note that the empty array means 0.0, by virtue of deleting trailing zeroes. This also makes sure that there is a unique correct answer for any range.

If you are unfamiliar with binary fractional numbers, they work just like decimal numbers:

Base 10   0.625 = 0.6 + 0.02 + 0.005 = 6 x 10^-1  +  2 x 10^-2  +  5 x 10^-3
Base  2   0.101 = 0.1 + 0.00 + 0.001 = 1 x  2^-1  +  0 x  2^-2  +  1 x  2^-3
|             |             |
v             v             v
Base 10                        0.625 =   0.5      +     0       +   0.125


Built-ins that trivialize this problem are disallowed.

Examples:

0.0, 1.0 -> ""
0.1, 1.0 -> "1"
0.5, 0.6 -> "1"
0.4, 0.5 -> "0111"


Shortest code wins.

• Does "arbitrarily precise" mean "within the limits of your language's types," or do we have to support input of (0.98983459823945792125172638374187268447126843298479182647, 0.98983459823945792125172638374187268447126843298479182648)? Also, test cases would be helpful. Feb 18, 2016 at 20:11
• @Doorknob Arbitrarily precise means that your answer should work for any input, up to limits of the physical machine (memory). So yes, that input must be supported.
– orlp
Feb 18, 2016 at 20:13
• Feb 18, 2016 at 21:27
• @MartinBüttner Really close (wasn't aware of it), but this question requires arbitrary precision and output as bits.
– orlp
Feb 18, 2016 at 21:30
• Aaaah the top-half-open interval x ≤ b < y is hard to deal with, it would be so much easier with x < b ≤ y.
– xnor
Feb 19, 2016 at 1:51

# CJam, 46

q'.-_,:M;S/{3a.+M'0e]~GM#*AM(#/(2b}/_@.=0#)<2>


Try it online

Explanation:

The general idea is: multiply both numbers by 10some big enough exponent to get integers, multiply again by 2another big enough exponent to "make room" for binary digits in integer form, integer-divide back by 10the first exponent, decrement the numbers (to get to the "x < b ≤ y" case) and convert the results to base 2. Find the first different digit (it will be 0 in the first number and 1 in the second number), and print all the digits from the second number up to and including that one.

Before starting with the multiplications, I'm adding 3 to the integer parts in order to ensure that the results have the same number of binary digits (with no leading zeros) after decrementing. At the end, I am skipping the first 2 binary digits to compensate.

q          read the input as a string
'.-        remove the dots
_,         duplicate and get the string length
:M;        store in M and pop; M-1 will be the first exponent
S/         split by space
{…}/       for each number (in string form)
3a.+     add 3 to the first digit (vectorized-add [3] to the string)
M'0e]    pad to the right with '0's up to length M
this is like multiplying the decimal number with 10^(M-1)
but done as a string operation
~        evaluate the result as an integer
GM#*     multiply by 16^M (G=16) = 2^(4*M) -- 4*M is the second exponent
AM(#/    divide by 10^(M-1) (A=10)
(2b      decrement and convert to base 2 (array of digits)
_          duplicate the 2nd array
@          bring the first array to the top
.=         vectorized-compare the arrays (digit by digit)
0#         find the position of the first 0 (meaning digits are not equal)
)<         increment and slice the other copy of the 2nd array before that position
2>         discard the first 2 digits


## Ruby, 138 132 bytes

->x,y{d,*a=->{a.map.with_index{|n,i|n/BigDecimal.new(2)**(i+1)}.inject(:+)||0};[a+=[1],a[-1]=d[]>=y ?0:1]while d[]<x;a}


13 bytes added for the  -rbigdecimal flag. Expects input as two BigDecimals.

Sample run:

irb(main):029:0> f=->x,y{d,*a=->{a.map.with_index{|n,i|n/BigDecimal.new(2)**(i+1)}.inject(:+)||0};[a+=[1],a[-1]=d[]>=y ?0:1]while d[]<x;a}
=> #<Proc:0x00000001053a10@(irb):29 (lambda)>
irb(main):030:0> f[BigDecimal.new('0.98983459823945792125172638374187268447126843298479182647'),BigDecimal.new('0.98983459823945792125172638374187268447126843298479182648')]
=> [1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1]


Explanation:

->x,y{
d,*a=   # sets d to the following, and a to [] with fancy splat operator
->{     # lambda...
a.map.with_index{|n,i|       # map over a with indices
n/BigDecimal.new(2)**(i+1)  # this will return:
#  - 0 [ /2**(i+1) ] if n is 0
#  - 1   /2**(i+1)   if n is 1
}.inject(:+)                 # sum
||0                          # inject returns nil on empty array; replace with 0
};      # this lambda turns [0, 1, 1]' into BigDecimal(0b0.011)'
[       # [...]while x' is a fancy/golfy way to say while x;...;end'
a+=[1],            # add a digit 1 to the array
a[-1]=d[]>=y ?0:1  # replace it with 0 if we exceeded upper bound
]while d[]<x;       # do this while(below the lower bound)
a       # return the array of digits
}


# Mathematica, 72 bytes

IntegerDigits[#2[[-1,-1]],2,Log2@#]&@@Reap[1//.a_/;Sow@⌈a#⌉>=a#2:>2a]&


Explanation

The method is to find the smallest multiplier of form 2^n that enlarges the gap between two input numbers so that it contains an integer.

For example, 16*{0.4,0.5} = {6.4,8.} contains 7, so the answer is 7/16.

Test case

%[0.4,0.5]
(* {0,1,1,1} *)

• Nice Reap and Sow! Feb 19, 2016 at 10:08

## JavaScript (ES6), 144 bytes

f=(x,y,b='',d=s=>s.replace(/\d/g,(n,i)=>(i&&n*2%10)+(s[i+1+!i]>4)).replace(/[.0]+\$/,''),n=d(x),m=d(y))=>n?n>'1'||(m||2)<='1'?f(n,m,b+n[0]):b+1:b


Assumes input in the form 0.<digits> (or 1.<zeros> is acceptable for y). d is a function which takes the decimal part of a number and doubles it, then trims trailing zeros. The leading digit must be present but it is ignored. Conveniently d("0.0") is empty, and this is therefore used as a test to see whether x is an exact binary fraction; in this case b already holds the result. Otherwise, there is a somewhat convoluted test to determine whether suffixing a 1 to b serves to distinguish between x and y; if so that is returned. Otherwise the MSB of x is suffixed to the result and the function calls itself recursively to process the next bit.

If instead we desire x < b ≤ y the function is much simpler, something like this (untested):

f=(x,y,b='',d=s=>s.replace(/\d/g,(n,i)=>(i&&n*2%10)+(s[i+1+!i]>4)),n=d(x),m=d(y))=>n>='1'||m<'1'?f(n,m,b+n[0]):b+1