By: Squishy Thinking

Re-posted from: http://squishythinking.com/2014/02/22/bisecting-floats/

Bisection is about the simplest algorithm there is for isolating a root of a continuous function:

1. Start with an interval such that the function takes on oppositely signed values on the endpoints.
2. Split the interval at its midpoint.
3. Recurse into whichever half has endpoints on which the function takes on oppositely signed values.

After each step, the new interval is half as large as the previous interval and still contains at least one zero (by the Intermediate Value Theorem).

I want to highlight a couple of interesting issues that arise when implementing bisection in floating point arithmetic that you might miss if you just looked at the definition of the algorithm.

Continue reading →