We examine the system-size scaling behavior for performing nonlocal op
erations in first-principles total-energy and force computations. A pr
ocedure is derived and demonstrated for computing the nonlocal part of
the total energy and its derivatives in O(N(a)(2)log(2)N(a)) operatio
ns (where N-a is the number of atoms) for calculations involving separ
able, nonlocal pseudopotentials. This procedure is performed in recipr
ocal space and is equivalent to the conventional approach, which scale
s as O(N-a(3)). Thus no approximations or new sources of error are int
roduced.