Diffuse scattering is a rich source of information about disorder in crystalline materials, which can be modelled using atomistic techniques such as Monte Carlo and molecular dynamics simulations. Modern X-ray and neutron scattering instruments can rapidly measure large volumes of diffuse-scattering data. Unfortunately, current algorithms for atomistic diffuse-scattering calculations are too slow to model large data sets completely, because the fast Fourier transform (FFT) algorithm has long been considered unsuitable for such calculations [Butler & Welberry, J. Appl. Cryst. 25, 391 (1992)]. Here, a new approach is presented for ultrafast calculation of atomistic diffuse-scattering patterns. It is shown that the FFT can actually be used to perform such calculations rapidly, and that a fast method based on sampling theory can be used to reduce high-frequency noise in the calculations. These algorithms are benchmarked using realistic examples of compositional, magnetic and displacive disorder. They accelerate the calculations by a factor of at least 100, making refinement of atomistic models to large diffuse-scattering volumes practical.