  In 1952, von Neumann introduced the rejection method for random variate
generation. We revisit this algorithm when we have a source of perfect bits at
our disposal. In this random bit model, there are universal lower bounds for
generating a random variate with a given density to within an accuracy
$\epsilon$ derived by Knuth and Yao, and refined by the authors. In general,
von Neumann's method fails in this model. We propose a modification that
insures proper behavior for all Riemann-integrable densities on compact sets,
and show that the expected number of random bits needed behaves optimally with
respect to universal lower bounds. In particular, we introduce the notion of an
oracle that evaluates the supremum and infimum of a function on any rectangle
of $\mathbb{R}^{d}$, and develop a quadtree-style extension of the classical
rejection method.
