You are invited to Log in or Register a free Frihost Account!

Implicit assumption that destroys the code

In this post, I've written a code snippet that uses bisection search to find a root of a specific polynomial within the interval [0,1].

The problem with it is that I've assumed that the polynomial does have a solution within this interval.
In general, this need not hold, and when it doesn't hold, the code searching for such a solution in the interval that doesn't contain it will go into an infinite loop.
This is easy to fix, but before that, we should at least characterise exactly when we have or do not have solutions within the interval.

For this, we can use the intermediate value theorem. This theorem rigorously captures the following intuitive idea:
Suppose you have a continuous function (you can draw it without lifting the pen off the paper).
We consider a section of it; starting somewhere on the left, and ending somewhere on the right.
Say, the starting point is at height A, and the ending point is at height B.
Then for any height in-between this A and B, you have, somewhere along the section, a function value that is at that height.
Now we consider part of our polynomial starting at p=0 to p=1.
Here's the polynomial again:
E = (w1 - w2) p^r + (w2 - wS) p^(r-1) + wS p^(r-2) - c

At p=0, E= -c
At p=1, E= w1 - c

where c is the positive cost of entering the drop-out tournament, and w1 is the prize for getting first place.
Note also that we have a continuous function since polynomial is continuous.
So by the intermediate value theorem, since -c is negative, this function will have a real root between 0 and 1 iff w1 - c is greater than or equal to 0.

This suggest that in the code snippet, we can simply fix it by adding a check for the above condition.
If so, we can then go ahead and run the search because we have a solution in [0,1].
Otherwise, the polynomial have no solution in [0,1] and we can terminate the search returning p=0, say. (In particular, it means that w1-c is less than 0, so the cost of entering the tournament is greater than the first place prize. I.e., one cannot gain monetary profit from said tournament.)

The lesson I learned is not so much the fix and the nice application of something from pure maths which also immediately suggests a precise mean to fixing the problem, but the little things that may come as less important from the context of the code and how big their effects can be.
This has been a good exercise for me Smile

0 blog comments below

© 2005-2011 Frihost, forums powered by phpBB.