Viewing a single comment thread. View all comments

MrSuperHappyPants t1_j246qix wrote

Other people have posted great answers. The following doesn't really contribute much that's new to the discussion, but since I wrote it I'll paste it here - consider it a way of paraphrasing previous responses.


The bisection method is simple enough to try and eli5:

Consider the square root (sqrt) of 2. Find two test values that will "bracket" the root. 1^2 = 1 (1 is too low), 2^2 = 4 (2 is too high).

So, cut the size of this interval in half (hence the "bisection" thing). If 1.5 is still too big (it is), we throw out 2 and the new interval of interest is between 1 and 1.5 (if it were too small we'd throw out 1 and the new interval would be between 1.5 and 2). 1 is too small, 1.5 is too big. Okay.

So now we're working with the interval between 1 and 1.5, and have tested both endpoints. So we try the midpoint of that interval which is 1.25. That's too small; there's now no need to bother checking anything between 1 and 1.25, so toss out 1. Now we're working with numbers between 1.25 and 1.5.

Basically we keep checking intervals that are each half the length of the previous one, where we know one endpoint is too big and the other one is too small.

  1. Evaluate at the midpoint of an interval.
  2. Toss out the endpoint that matches the "too big" or "too small" nature of the result of step 1.
  3. Create a new interval accordingly and repeat.

There are faster methods than this, but they are a bit harder to eli5.

1