  Suppose that $X_1,X_2,\ldots$ are independent identically distributed
Bernoulli random variables with mean $p$. A Bernoulli factory for a function
$f$ takes as input $X_1,X_2,\ldots$ and outputs a random variable that is
Bernoulli with mean $f(p).$ A fast algorithm is a function that only depends on
the values of $X_1,\ldots,X_T$, where $T$ is a stopping time with small mean.
When $f(p)$ is a real analytic function the problem reduces to being able to
draw from linear functions $Cp$ for a constant $C > 1$. Also it is necessary
that $Cp \leq 1 - \epsilon$ for known $\epsilon > 0$. Previous methods for this
problem required extensive modification of the algorithm for every value of $C$
and $\epsilon$. These methods did not have explicit bounds on $\text{E}[T]$ as
a function of $C$ and $\epsilon$. This paper presents the first Bernoulli
factory for $f(p) = Cp$ with bounds on $\text{E}[T]$ as a function of the input
parameters. In fact, $\sup_{p \in [0,(1-\epsilon)/C]} \text{E}[T] \leq
9.5C\epsilon^{-1}.$ In addition, this method is very simple to implement.
Furthermore, a lower bound on the average running time of any $Cp$ Bernoulli
factory is shown. For $\epsilon \leq 1/2$, $\sup_{p \in [0,(1 - \epsilon)/C]}
\text{E}[T] \geq 0.004 C \epsilon^{-1}$, so the new method is optimal up to a
constant in the running time.
