nor's blog

Convenient and near-optimal binary search on floating point numbers
By nor, 8 months ago, In English

https://nor-blog.codeberg.page/posts/2024-03-05-floating-point-binsearch/

  • Vote: I like it
  • +46
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +52 Vote: I do not like it

the blog: *about binary search*

the code:

template <std::size_t N_BITS>
using int_least_t = std::conditional_t<
    N_BITS <= 8, std::uint8_t,
    std::conditional_t<
        N_BITS <= 16, std::uint16_t,
        std::conditional_t<
            N_BITS <= 32, std::uint32_t,
            std::conditional_t<
                N_BITS <= 64, std::uint64_t,
                std::conditional_t<N_BITS <= 128, __uint128_t, void>>>>>;
→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    Please tell Bjarne Stroustrup to add templated int_least_t to the STL instead of the concrete type definitions :(

    → Reply
»
8 months ago, # |
  Vote: I like it +11 Vote: I do not like it

"I am pretty sure that this method has been explored before" Yes.

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Great Blog!

→ Reply
»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Since most problems allow some relative error in the answer, it is usually not necessary to do the full 64 iterations. For example, if the answer is positive and we can tolerate a $$$10^{-6}$$$ relative error, then we can do binary search on doubles like this:

while (get_int(a) + (1ULL << 32) < get_int(b)) {
    auto m = std::midpoint(get_int(a), get_int(b));
    if (predicate(get_float(m))) {
        a = get_float(m);
    } else {
        b = get_float(m);
    }
}

Outside of annoying edge cases (0, NaN, inf, subnormal, etc.), the condition get_int(a) + (1ULL << 32) >= get_int(b) implies the relative error of $$$a$$$ and $$$b$$$ is at most $$$2^{-20}$$$ < $$$10^{-6}$$$.

Proof

The same could work for any $$$b < 52$$$ for $$$2^{-(52 - b)}$$$ precision. How to modify nor's template to support this is an exercise for the reader.

→ Reply