  We present a fast and accurate algorithm for the evaluation of nonlocal
(long-range) Coulomb and dipole-dipole interactions in free space. The
governing potential is simply the convolution of an interaction kernel $U(\bx)$
and a density function $\rho(\bx)=|\psi(\bx)|^2$, for some complex-valued wave
function $\psi(\bx)$, permitting the formal use of Fourier methods. These are
hampered by the fact that the Fourier transform of the interaction kernel
$\widehat{U}(\bk)$ has a singularity at the origin $\bk={\bf 0}$ in Fourier
(phase) space. Thus, accuracy is lost when using a uniform Cartesian grid in
$\bk$ which would otherwise permit the use of the FFT for evaluating the
convolution. Here, we make use of a high-order discretization of the Fourier
integral, accelerated by the nonuniform fast Fourier transform (NUFFT). By
adopting spherical and polar phase-space discretizations in three and two
dimensions, respectively, the singularity in $\hat{U}(\bk)$ at the origin is
canceled, so that only a modest number of degrees of freedom are required to
evaluate the Fourier integral, assuming that the density function $\rho(\bx)$
is smooth and decays sufficiently fast as $\bx \rightarrow \infty$. More
precisely, the calculation requires $O(N\log N)$ operations, where $N$ is the
total number of discretization points in the computational domain. Numerical
examples are presented to demonstrate the performance of the algorithm.
