浮点数的二进制搜索/二分法

Question

用二分查找很容易找到一个整数even if it can be arbitrarily large：先猜数量级，然后一直划分区间。 This answer 描述了如何找到任意有理数。

设置场景后，我的问题是类似的：我们如何猜测 IEEE 754 浮点数？假设它不是 NaN，但其他一切都是公平的游戏。对于每次猜测，您的程序都会被告知所讨论的数字是更高、相等还是更低。尽量减少最坏情况下所需的猜测次数。

（这不是家庭作业。不过，我可能会把它做成一个，如果结果有一个有趣的答案，而不仅仅是 "beat the floating point numerical difficulties to death with lots and lots of special case handling."）

编辑：如果我更擅长搜索，我本可以找到 answer--- 但这只有在您已经知道重新解释为 int 有效（有某些注意事项）的情况下才有效。所以留下这个。感谢哈罗德的精彩回答！

Answer 1

相同的方法可以应用于浮点数。最坏的情况运行时间是 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);
    }
}

Answer 2

IEEE-754 64 位浮点数实际上是 64 位表示。此外，除了 NaN 值之外，浮点数比较和正值的整数比较之间没有区别。（也就是说，两个未设置符号位的位模式将产生相同的比较结果，无论您将它们作为 int64_t 还是 double 进行比较，除非其中一个位模式是浮点 NaN-。 )

这意味着你可以通过一次猜一个位在64次猜测中找到一个数字，即使这个数字是±∞。首先将数字与 0 进行比较；如果目标是 "less"，则以与下面相同的方式产生猜测，但在猜测之前否定它们。（由于 IEEE-754 浮点数是 sign/magnitude，您可以通过将符号位设置为 1 来取反数字。或者您可以进行正位模式重新解释，然后浮点取反结果。）

之后，从最高位开始，一次猜一位。如果数字大于或等于猜测，则将该位设置为 1；如果数字较小，则将该位设置为 0；并继续下一位，直到不再有为止。要构建猜测，请将位模式重新解释为 double.

有两个注意事项：

用对比测试无法区分±0。这意味着如果你的对手想让你区分它们，他们将不得不为你提供一种询问与 -0 是否相等的方法，并且你必须在你显然确定数字为 0 之后使用该机制（这将在第 64 次猜测时发生）。这将增加一个猜测，总共 65.
如果你确定target不是NaN，那么就没有其他问题了。如果它可能是一个 NaN，你需要小心你如何比较：如果你总是问 "is X less than this guess?"，事情会很好，因为 NaN 比较总是 return 错误。这意味着在 11 个连续的 "no" 个答案（不包括建立符号的那个）之后，你会发现自己在猜测 ∞，假设如果数字不小于 ∞，则它必须相等。但是，仅在这种情况下 您还需要显式测试相等性，因为如果目标是 NaN，那也将是错误的。这不会将额外的猜测添加到计数中，因为它总是会在 64 次猜测用完之前很久发生。

浮点数的二进制搜索/二分法

Binary search / bisection for floating point numbers

algorithm

floating-point

binary-search

numerics