# How to efficiently find quantile (root) of integral function

Let $f(x)$ be a density function on $\mathbb R$; I want to find numerically the $\alpha$ quantile of the associated distribution, i.e. I want to find $c$ such that

$$\int_{-\infty}^c f(x)dx = \alpha$$

$f(x)$ is reasonably fast to compute, but if I apply the usual root-finding algorithms (say, newton-raphson) I would need to compute the integral of $f(x)$ at every iteration, which is impractical.

Do you have any references as of how solve the problem numerically? Is there a root-finding algorithm that doesn't need the evaluation of the function, but only of its derivative (in this case $f(x)$) ?

• You should be able to compute the integral to machine precision in 30 function evaluations using exp-sinh quadrature, then use bisection->Newton to find the root. I don't see why this is impractical. – user14717 Apr 5 '17 at 0:56
• An additional idea is to use exp-sinh to evaluate $F(0)$, then $F(c)$ can be evaluated via tanh-sinh quadrature in ~10 function evaluations. Start creating a lookup table for $F(c_{i})$ as the iterations proceed. If need be, build a barycentric rational approximation to $F$. – user14717 Apr 5 '17 at 1:08
• @user14717 Hi! What is a barycentirc rational approximation? Anyhow, if I use the tanh-sinh quadrature to compute $F(c)$, I still need to call the density ~11 times per iteration. It could work though. – Ant Apr 5 '17 at 7:24
• pdfs.semanticscholar.org/c6d7/… – user14717 Apr 5 '17 at 15:19
• An implementation of barycentric rational interpolation: github.com/boostorg/math/pull/58 – user14717 Apr 5 '17 at 15:24