If you do that a lot, Adaptive Rejection Sampling (or some variant if it's not log-concave) may be useful; it builds up the rejection envelope while trying to s

If you do that a lot, Adaptive Rejection Sampling (or some variant if it's not log-concave) may be useful; it builds up the rejection envelope while trying to sample and often succeed in 5-10 evaluations.