If I have an arbitrary positive monotonically decreasing function $f(x), x \in [0,\infty]$, is there an 'efficient' method for finding $y$ in: 


$r = \int\limits\_0^y f(x) dx $


for a known $r \in [0, \int\limits\_0^\infty f(x) dx]$. By efficient I guess I mean more efficient than doing numerical integration until one lands in within a given distance from $r$. 


I particularly care about the cases where the integral of $f$ has no closed form.




---


Best answer so far (rewrite of below), doubt it gets much better than this:


Start with $s\_0 = r$, $y\_0 = 0$, then


$y\_{i+1} = y\_i + \frac{s\_i}{f(y\_i)} $


$s\_{i+1} = s\_i - \int\limits\_{y\_i}^{y\_{i+1}}f(x)dx$



Numerical Solution to Inverse Integral (Pseudo Random Number Generation)
I guess the only non-trivial thing about the problem is that:
$$
 x f(0) \geq \int\_0^{x} f(t) dt \geq x f(x).
$$
So you start by computing the integral 
$$
 r\_1 = \int\_0^{y\_1} f(t) dt,\quad y\_1 = \frac{r}{f(0)}.
$$
Then replace $r$ by $r - r\_1$. I think under reasonable assumptions this should converge pretty quickly (and always lower bound). It should be noted that I only use one of the inqualities, one can probably optimize it by using the other one.


