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.

  • 3
    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. – Doorknob Feb 18 '16 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 '16 at 20:13
  • Sort of dupe? – Martin Ender Feb 18 '16 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 '16 at 21:30
  • 1
    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 '16 at 1:51
up vote 2 down vote accepted

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! – A Simmons Feb 19 '16 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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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