Find the simplest value between two values

Question

Goal

Your goal is to find the simplest value in an open interval. In other words, given two values a,b with a<b, output the simplest x with a<x<b. This is a code golf, so fewest bytes wins.

Simplicity

All values in this problem are dyadic rationals, which means their binary expansions are finite, or equivalently, are rationals in simplest form a/2^b for some integer a and non-negative integer b. Integers are dyadic rationals with b=0.

Being simpler means having smaller b, tiebroken by smaller absolute value |a|.

Equivalently in terms of binary expansions, to find the simpler number:

1. Take the one with a shorter fractional part (fewer binary digits after the point).
2. In case of tie, take the lexicographically earlier one with length the primary sort, ignoring sign.

So, the numbers in simplicity order are

0, ±1, ±2, ±3, ±4, ...
±1/2, ±3/2, ±5/2, ...
±1/4, ±3/4, ±5/4, ...
±1/8, ±3/8, ... 
±1/16, ...
...

There's no need to say which of ±x is simpler because any interval that contains both candidates also contains 0, which is simpler than both.

(A bit of background and motivation: In combinatorial game theory, positions in a two-player games have a numerical value representing magnitude of advantage, with the sign saying which player is favored. This value is determined recursively from the two values resulting from the best move of each player. You might guess that one averages them, but in fact it's the simplest value in between.)

Program requirements

Write, in as few bytes as possible, a program or named function that takes two dyadic rationals a,b and outputs the simplest dyadic rational x with a<x<b. Input can be function input or STDIN, and output can be function return or printing.

Input format

Two dyadic rationals a,b in whatever type your languages use for real or finite-precision binary values (float, double, etc). Fraction or rational types that store the value as a numerator and denominator are not acceptable. If you language has no valid type (and only then), you may use binary strings like 101.1101, or post a comment and we'll work something out.

You are guaranteed that a,b are dyadic rationals and a<b. Integer values will be given like 3.0, not 3.

You can assume you have sufficient precision to store the values, the output, and any intermediate steps exactly. So, you shouldn't worry about precision or overflows. I won't give an explicit bound on inputs, but your algorithm should take a reasonable amount of time on inputs like the test cases.

You may take your two numbers in any reasonable built-in container like pair, tuple, list, array, or set. Structures specifically representing intervals are not allowed though.

Output

The simplest dyadic rational strictly between a and b. The same rules for the input types apply, except outputting 3 rather than 3.0 is OK.

Test cases

(-1.0, 1.0)
0.0
(0.0, 2.0)
1.0
(0.0, 4.0)
1.0
(0.5, 2.0)
1.0
(-3.25, -2.5)
-3.0
(-4, 1.375)
0.0
(4.5, 4.625)
4.5625
(-1.875, -1.5)
-1.75

Answer 1

Python 2 - 100

I think I revised my entire method for this answer a good 4 or 5 times (which is probably an indication that it's a good code-golf question). I don't know if this answer can be golfed down any more but I do feel as if I'm missing some more clever methodological ways to shorten this.

def f(a,b,i=1.):
    r=0if a<0 else(a*i+1)//1/i
    return-f(-b,-a,i)if b<=0 else r if r<b else f(a,b,i*2)

Answer 2

Haskell, 61 88 75 73

p!q|p<0= -(-q)!(-p)|r<q=max r 0|0<1=(2*p)!(2*q)/2where r=toEnum$floor$p+1

this checks if there is a whole number between the two, and if yes, return the smallest one. if not, multiply the numbers by 2, apply them recursively, divide by 2 and return.
at least, this is how it works in my mind. the actual code is a bit different.

thanks to xnor for his rounding magic

Answer 3

Java - 157 187 186

Probably could be golfed more.

Thanks to Quincunx for a byte.

void f(float a,float b){for(float i=1,d;;i*=2){for(d=0;d<i*Math.max(Math.abs(b),Math.abs(a));d++){for(float x:new float[]{d/i,-d/i}){if(x<b&&x>a){System.out.print(x);System.exit(0);}}}}}

Brute forces all values of the numerator (positive and negative) while the denominator doubles each time.

Answer 4

C, 98 bytes

Using a recursive algorithm (and the fact that f(a,b) = f(2*a,2*b)/2). I also removed some bugs. The right answer is:

float n(float a, float b){return (floor(a+1)<ceil(b))?(a<0?(b>0?0:ceil(b-1)):floor(a+1)):n(2*a,2*b)/2;}

Which, to meet the prerequisites, is 19 bytes longer than the original one (of 79 bytes)

Full code:

#include <stdio.h>
#include <math.h>
float n(float a, float b){return (floor(a+1)<ceil(b))?(a<0?(b>0?0:ceil(b-1)):floor(a+1)):n(2*a,2*b)/2;}
main() 
{
    float a = -4.0;
    float b = -1.4;
    printf("%f",n(a,b));
}

Just copy-paste it into a random online c compiler and run it.

Answer 5

Python 3: 80 bytes

g=lambda a,b:-g(-b,-a)if b<=0 else int(a+1)*(a>=0)if-~int(a)<b else g(2*a,2*b)/2

Ungofed:

def g(a,b):
    if b<=0:return -g(-b,-a)
    if int(a+1)<b:return int(a+1)*(a>=0)
    return g(2*a,2*b)/2

Can probably be golfed more by changing the if/else structure to and/or. The obvious transformation fails due to non-short-circuiting on the Falsey output of 0, but there's likely a rearrangement that does it.

The space in b<=0 else can't be removed as usual because the start letter e is parsed as part of number literals like 1e6.

Answer 6

ES6, 68 67 59

g=(a,b)=>(x=~~(a+1),b>0?x<b?x*(x>0):g(2*a,2*b)/2:-g(-b,-a))

this is a port of xnor's solution (basically, the new thing in it was that it checked for having 0 in the range by *(a>=0). couldn't do this in Haskell because Haskell has a type system :) )

this is the first time I used ES6 ever, so this might still be golfable.

Answer 7

Perl (89)

most probably this can still be golfed

sub S{($q,$w)=@_;$m=1,$r=0;until($q<$r&&$r<$w){$r=int$q+1;$r<$w||map$_*=2,$m,$q,$w}$r/$m}