Binary search / bisection for floating point numbers

Question

It is easy to find an integer with binary search even if it can be arbitrarily large: first guess the order of magnitude, then keep dividing the interval. This answer describes how to find an arbitrary rational number.

Having set the scene, my question is similar: how can we guess a IEEE 754 floating point number? Assume it is not NaN, but everything else is fair game. For each guess, your program will be told whether the number in question is higher, equal or lower. Minimize the number of guesses required in the worst case.

(This is not a homework assignment. Though, I might make it one, if this turns out to have an interesting answer that's not just "beat the floating point numerical difficulties to death with lots and lots of special case handling.")

Edit: if I were better at searching I could have found the answer---but that only works if you already know that reinterpretation as int works (with certain caveats). So leaving this up. Thanks to Harold for a great answer!

Answer 1

IEEE-754 64-bit floating point numbers are really 64-bit representations. Furthermore, with the exception of NaN values, there is no difference between floating point comparison and integer comparison of positive values. (That is, two bit patterns with the sign bit unset will produce the same comparison result regardless of whether you compare them as int64_t or double, unless one of the bit patterns is a floating point NaN-.)

That means you can find a number in 64 guesses by guessing one bit at a time, even if the number is ±∞. Start by comparing the number with 0; if the target is "less", then produce the guesses in the same way as below, but negate them before guessing. (Since IEEE-754 floats are sign/magnitude, you can negate the number by setting the sign bit to 1. Or you could do the positive bit-pattern reinterpretation and then floating point negate the result.)

After that, guess one bit at a time, starting with the highest-order value bit. Set that bit to 1 if the number is greater than or equal to the guess; set that bit to 0 if the number is less; and continue with the next bit until there aren't any more. To construct the guess, reinterpret the bit pattern as a double.

There are two caveats:

1. You cannot distinguish between ±0 with comparison tests. That means that if your opponent wants you to distinguish between them, they will have to supply you with a way to ask about equality with −0, and you'll have to use that mechanism after you've apparently established that the number is 0 (which will happen on the 64th guess). This would add one guess, for a total of 65.

2. If you are assured that the target is not a NaN, then there is no other problem. If it might be a NaN, you need to be careful how you compare: things will work out fine if you always ask "is X less than this guess?", because a NaN comparison will always return false. That means that after 11 successive "no" answers (not counting the one to establish the sign), you will find yourself guessing ∞, with the assumption that if the number is not less than ∞, it must be equal. However, in this case alone you need to explicitly test for equality as well, because that will also be false if the target is a NaN. This doesn't add an additional guess to the count, because it will always happen long before 64 guesses have been used up.

Answer 2

The same approach can be applied to a floating point number. Worse case run time is O(log n).

public class GuessComparer
{
    private float random;
    public GuessComparer() // generate a random float and keep it private
    {
        Random rnd = new Random();
        var buffer = new byte[4];
        rnd.NextBytes(buffer);
        random = BitConverter.ToSingle(buffer, 0);
    }
    public int CheckGuess(float quess) // answer whether number is high, lower or the same.
    {
        return random.CompareTo(quess);
    }
}
public class FloatFinder
{

    public static int Find(GuessComparer checker)
    {
        float guess = 0;
        int result = checker.CheckGuess(guess);
        int guesscount = 1;
        var high = float.MaxValue;
        var low = float.MinValue;
        while (result != 0)
        {
            if (result > 0) //random is higher than guess
                low = guess;
            else// random is lower than guess

                high = guess;

            guess = (high + low) / 2;
            guesscount++;
            result = checker.CheckGuess(guess);
        }
        Console.WriteLine("Found answer in {0}", guesscount);
        return guesscount;
    }

    public static void Find()
    {
        var checker = new GuessComparer();
        int guesses = Find(checker);
    }
}