  We present first principles calculations of the exchange interactions between
magnetic impurities deposited on (001), (110) and (111) surfaces of Cu and Au
and analyze them, in particular, in the asymptotic regime. For the (110) and
the (111) surfaces we demonstrate that the interaction shows an oscillatory
behavior as a function of the distance, R, of the impurities and that the
amplitude of the oscillations decays as 1/R^2. Furthermore, the frequency of
the oscillations is closely related to the length of the Fermi vector of the
surface states existing on these surfaces. Due to the asymmetry of the the
surface states' dispersion, the frequency of the oscillations becomes also
asymmetric on the (110) surfaces, while on the Au(111) surface two distinct
frequencies are found in the oscillations as a consequence of the
Bychkov-Rashba splitting of the surface states. Remarkably, no long range
oscillations of the exchange interaction are observed for the (001) surfaces
where the surface states are unoccupied. When burying the impurities beneath
the surface layer, oscillations mediated by the bulk states become visible.
