Repository navigation
Binary Search
Binary search is a well-known search algorithm with the fastest worst-case convergence. On every iteration, half of all possible solutions are eliminated. When dealing with root-finding on floats, the bisection method is often synonymous with binary search, but we wish to dispel this misconception and inform our readers on the necessary precautions taken within our solver software to produce a more accurate representation of binary search, which significantly improves the worst case of several thousands of iterations to only about 350 iterations.
Most commonly root-finding is done within double precision (IEEE 754-2008), which uses 64 bits to represent a floating point number. If one bit of accuracy for this float could be recovered per iteration, then convergence can be guaranteed in no more than 64 iterations. Achieving this, however, requires an understanding of the structure of a double, which is often neglected in other root-finding software. Because of this, many other software can take several thousands of iterations to converge, whereas our software is guaranteed to converge in at most about 350 iterations, a stark difference.
The format of a double comes in 3 parts.
- A single sign bit.
- 11 bits for the exponent.
- 52 bits for the mantissa a.k.a. precision or fraction.
Handling the sign bit can be easily done by checking x = 0 if 0 lies in the bracketing interval. All remaining iterations will lie on one side or the other.
Handling the exponent from there can be done using the geometric mean (GM). In short, a binary search over the exponent bits may be conducted until the relative error is sufficiently small i.e. until x / y > 0.5 with | x | < | y |.
Handling the mantissa from there can be done using the arithmetic mean (AM). In short, a binary search over the mantissa bits is conducted.
We remark that all of this can be avoided on a sufficiently low level where doubles can be interpreted as bits. In this case, it suffices to use the arithmetic mean when interpreting the bits as an integer. Because of this, it may be potentially much faster to use integer arithmetic than the case-by-case approach we use below.
The arithmetic mean, as used in bisection, is guaranteed to halve the absolute error. Its formula is given by
AM( x, y ) = 0.5 ( x + y )
and is quite easy to use. We use an altered version when x / y < 1/8 and | x | < | y |:
AM( x, y ) = 0.75 x + 0.25 y
which simulates the original speed of bisection when GM is used with AM alternatingly.
The geometric mean is guaranteed to "halve" the relative error. Its formula is given by
GM( x, y ) = sign( y ) √( x y ) if sign( x ) = sign( y ), otherwise 0
It's worth noting that the square root is used here, and depending on the application, we warn this may be a heavy arithmetic operation. We also remark that 0 should not remain 0 due to the tolerance. This allows the result of the GM to land on one side of 0 or the other.
Although in theory the use of GM is an interesting idea, it cannot be expected that the root will lie more heavily on one side of the interval just because there are more doubles near 0. To simultaneously allow for a fast search through all doubles without ignoring the reality that the distribution of roots need not depend on the distribution of doubles themselves, a combination of both AM and GM is used.
- To ensure both are considered, AM and GM are initially alternated in usage.
- If AM is used and x / y > 0.25 with | x | < | y | then the altered AM with heavy weighting towards x is used and then swapped to GM.
- If GM is used and the absolute error does not decrease by a factor of 0.75, it is considered a failure to bisect the interval and swapped with AM.
- If GM is used and the absolute error decreases by a factor of 0.125, it is considered a success and GM is used again next time binary search is tried.
- To ensure GM is not used unnecessarily due to higher arithmetic complexity, AM is the only mean used once x / y > 0.25 with | x | < | y |.
This combination guarantees both the absolute and relative errors are rapidly decreasing, and hence convergence may be guaranteed in roughly 70 iterations. With default settings, this leads to about 150 iterations at worst to converge when combined with other methods. Without default settings, this leads to about 350 iterations at worst to converge when combined with other methods.