  This paper introduces a fast algorithm, applicable throughout the
electromagnetic spectrum, for the numerical solution of problems of scattering
by periodic surfaces in two-dimensional space. The proposed algorithm remains
highly accurate and efficient for challenging configurations including randomly
rough surfaces, deep corrugations, large periods, near grazing incidences, and,
importantly, Wood-anomaly resonant frequencies. The proposed approach is based
on use of certain `shifted equivalent sources' which enable FFT acceleration of
a Wood-anomaly-capable quasi-periodic Green function introduced recently (Bruno
and Delourme, Jour. Computat. Phys., 262--290, 2014). The Green-function
strategy additionally incorporates an exponentially convergent shifted version
of the classical spectral series for the Green function. While the
computing-cost asymptotics depend on the asymptotic configuration assumed, the
computing costs rise at most linearly with the size of the problem for a number
of important rough-surface cases we consider. In practice, single-core runs in
computing times ranging from a fraction of a second to a few seconds suffice
for the proposed algorithm to produce highly-accurate solutions in some of the
most challenging contexts arising in applications.
