  Improved staggered fermion formulations are a popular choice for lattice QCD
calculations. Historically, the algorithm used for such calculations has been
the inexact R algorithm, which has systematic errors that only vanish as the
square of the integration step-size. We describe how the exact Rational Hybrid
Monte Carlo (RHMC) algorithm may be used in this context, and show that for
parameters corresponding to current state-of-the-art computations it leads to a
factor of approximately seven decrease in cost as well as having no step-size
errors.
