  The two-point correlation function of the galaxy distribution is a key
cosmological observable that allows us to constrain the dynamical and
geometrical state of our Universe. To measure the correlation function we need
to know both the galaxy positions and the expected galaxy density field. The
expected field is commonly specified using a Monte-Carlo sampling of the volume
covered by the survey and, to minimize additional sampling errors, this random
catalog has to be much larger than the data catalog. Correlation function
estimators compare data-data pair counts to data-random and random-random pair
counts, where random-random pairs usually dominate the computational cost.
Future redshift surveys will deliver spectroscopic catalogs of tens of millions
of galaxies. Given the large number of random objects required to guarantee
sub-percent accuracy, it is of paramount importance to improve the efficiency
of the algorithm without degrading its precision. We show both analytically and
numerically that splitting the random catalog into a number of subcatalogs of
the same size as the data catalog when calculating random-random pairs, and
excluding pairs across different subcatalogs provides the optimal error at
fixed computational cost. For a random catalog fifty times larger than the data
catalog, this reduces the computation time by a factor of more than ten without
affecting estimator variance or bias.
