Let $\{X_i\}$ denote an i.i.d. sequence of Bernoulli variables with parameter $p$. A Bernoulli factory is a procedure that generates events with probability $f(p)$ using the observations $\{X_i\}$, where $f$ is a known function and $p$ is assumed to be unknown.

Is there some general result, or bound, on the number of samples of $\{X_i\}$ needed by a Bernoulli factory?

Some simple examples:

• ($f(p) = p^2$) To generate an event with probability $p^2$ it's sufficient to use two samples of the original sequence $\{X_i\}$. Actually less on average, because if the first of those two samples is $0$ you don't need the second.

• ($f(p) = \sqrt 2$) The algorithm at the top of page 7 of this paper generates an event of probability $\sqrt p$. The number of samples of $\{X_i\}$ used by that procedure can be easily computed.

• There are some general approaches for arbitrary $f$, for example this one using martingales.

So, given a function $f$ and a procedure that generates an event that has probability $f(p)$, how can one know if that's the best procedure, in the sense of using the least possible number of observations $X_i$ (on average) that is possible? Or, failing that, are there some bounds on that number?