Your goal is to find the simplest value in an open interval. In other words, given two values
a<b, output the simplest
a<x<b. This is a code golf, so fewest bytes wins.
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
Being simpler means having smaller
b, tiebroken by smaller absolute value
Equivalently in terms of binary expansions, to find the simpler number:
- Take the one with a shorter fractional part (fewer binary digits after the point).
- 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.)
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
a<x<b. Input can be function input or STDIN, and output can be function return or printing.
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
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.
The simplest dyadic rational strictly between
b. The same rules for the input types apply, except outputting
3 rather than
3.0 is OK.
(-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
.get_denom(), it's OK. Also, the output should be not be written in fraction form. \$\endgroup\$