# Find the simplest value between two values

## 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

• Commented Oct 1, 2014 at 22:28
• @MartinBüttner "Fraction or rational types that store the value as a numerator and denominator are not acceptable." But if your rational type is just real numbers stored internally as rational for exact precision and you don't use things like .get_denom(), it's OK. Also, the output should be not be written in fraction form.
– xnor
Commented Oct 1, 2014 at 22:32
• Ugh, it's getting late and my attention span is apparently dwindling... Commented Oct 1, 2014 at 22:33
• Probably should specify that there is at least one representable value between a and b. Commented Oct 2, 2014 at 0:45
• @feersum How would that fail to be the case?
– xnor
Commented Oct 2, 2014 at 0:48

# 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)

• This code doesn't seem to work for large-magnitude numbers. Note that x + 1 may be equal to x, if x is greater than 2**53. Commented Oct 2, 2014 at 0:58
• I didn't intend for overflows or representation limits to be a concern. I've edited to make that clear.
– xnor
Commented Oct 2, 2014 at 1:06
• How is that an overflow? It's only the result of an approach that doesn't work. Commented Oct 2, 2014 at 1:09
• @feersum "You can assume you have sufficient precision to store the values, the output, and any intermediate steps exactly." Is that not sufficient?
– xnor
Commented Oct 2, 2014 at 1:10
• OK, I see you have edited it just now. I prefer the non-watered down version. Or maybe I will make one that uses the intermediate step of adding 2^-1074 until the answer is reached:) Commented Oct 2, 2014 at 1:16

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

• I don't think this works for ranges that contain 0. Trying -3!4 gives -3.5, instead of 0. I think you may be assuming that the inputs have the same sign, although, I admit I don't know much about Haskell, am I doing something wrong? (and sorry, if I am) Commented Oct 3, 2014 at 14:39
• @FryAmTheEggman negatives in Haskell are a bit annoying. -3!4 is parsed as -(3!4), which should be -3.5. but you are infact right, (-3)!4 is -2.0. I'll fix it when i can Commented Oct 3, 2014 at 14:43
• Ah, thanks for that tip :) You might be able to try multiplying (or just returning?) your result by 0 if p*q<0. Again, don't know much about Haskell, but that is usually a good way to check for having different signs. Commented Oct 3, 2014 at 14:56

## Java - 157187 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.

• I don't think imports are free. Commented Oct 2, 2014 at 0:07
• This doesn't work for large values either. E.g. if I call f((float)1e30, (float)1e31) it appears to go into an infinite loop. Or was I just not patient enough? Commented Oct 2, 2014 at 1:07
• I edited the rules to not worry about precision or representation issues. Floats are fine.
– xnor
Commented Oct 2, 2014 at 1:46
• @ypnypn This is an issue that comes in Java in that you can't do imports without wrapping the function in a class. Here's what I say: You can have a "floating" import statement separate from the function, but the chars in the import statement count, including a char for newline. So this is 189 chars.
– xnor
Commented Oct 2, 2014 at 1:49
• @feersum you probably aren't patient enough :) Commented Oct 2, 2014 at 2:37

# 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}

• In perl 5.32 (released in June 2020) comparison operators can be chained. This means that you can replace $q<$r&&$r<$w with $q<$r<\$w and save four bytes. metacpan.org/pod/distribution/perl/pod/… Commented Sep 6, 2020 at 0:17

## 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.

• can I port your code? Commented Oct 5, 2014 at 12:38
– xnor
Commented Oct 5, 2014 at 19:17

# ES6, 6867 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.

• For the type issue of x*(a>=0), an alternative is max(x,0). Can you do that efficiently in Haskell?
– xnor
Commented Oct 5, 2014 at 19:41
• @xnor your rounding magic is ingenious Commented Oct 5, 2014 at 19:54
• Also, you can do x*(x>0). I couldn't do that in Python because I can't assign x.
– xnor
Commented Oct 5, 2014 at 19:55
• I know this is an old post, but I believe ~~(a+1) is the same as -~a, saving 4 bytes. Also, with some rearrangement, you can save another 3 bytes: g=(a,b)=>b>0?-~a<b?-~a*(~a<0):g(2*a,2*b)/2:-g(-b,-a) Commented Sep 8, 2016 at 20:10

# 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.

• Does this give f(-4, 1.375)=0.0? I don't see the code handling that case.
– xnor
Commented Oct 2, 2014 at 19:46
• a and b seem to be reversed, and I think you may have misread the question a bit. n(2.1,1.2) gives me 3.0 instead of 1.5, and any integer input, like n(2.0,1.0) will crash because ceil(a)>a is always false. Commented Oct 2, 2014 at 20:14
• @FryAmTheEggman but the spec tells to assume that the first parameter is smaller Commented Oct 3, 2014 at 8:05
• Does this work on negatives? Your code chooses the smallest whole number in the range, so for example on -7.5, -3.5 this would choose -7 when the result should be -4 Commented Oct 3, 2014 at 8:17
• @Gerwin when are you going to fix this? Commented Oct 4, 2014 at 10:52