03/23/2010, 10:54 AM
To compute the inverse function of a strictly increasing function \( f \) a method that always works is bisection.
perhaps you start with an integer number \( t_0 \) as you described.
Then you know the real value \( t \) such that \( f(t)=y \) must lie in the interval \( (t_0,t_0+1) \), set \( u_0=t+1 \).
Next you divide the interval \( (t_0,u_0) \) into two halfes by \( w_0=\frac{t_0+u_0}{2} \), and you know that \( t \) must either be in the left half \( (t_0,w_0) \) or in the right half \( (w_0,u_0) \); in the first case must \( f(t_0)<y<f(w_0) \) and in the second case \( f(w_0)<y<f(u_0) \). You choose the new interval \( (t_1,u_1) \) accordingly.
And do again bisection on it.
By repetition of bisection you can compute the \( t \) to arbitrary precision (in the above argumentation I assumed that the solution is never on the boundary of the interval, in which case one can abort the bisection, having found the solution).
For a more concise description see wikipedia.
There are also other root-finding algortithms, like Newton method, etc.
perhaps you start with an integer number \( t_0 \) as you described.
Then you know the real value \( t \) such that \( f(t)=y \) must lie in the interval \( (t_0,t_0+1) \), set \( u_0=t+1 \).
Next you divide the interval \( (t_0,u_0) \) into two halfes by \( w_0=\frac{t_0+u_0}{2} \), and you know that \( t \) must either be in the left half \( (t_0,w_0) \) or in the right half \( (w_0,u_0) \); in the first case must \( f(t_0)<y<f(w_0) \) and in the second case \( f(w_0)<y<f(u_0) \). You choose the new interval \( (t_1,u_1) \) accordingly.
And do again bisection on it.
By repetition of bisection you can compute the \( t \) to arbitrary precision (in the above argumentation I assumed that the solution is never on the boundary of the interval, in which case one can abort the bisection, having found the solution).
For a more concise description see wikipedia.
There are also other root-finding algortithms, like Newton method, etc.