w^2}{\pi^2 \delta_A} \frac{N_w}{6} [N_w + 1][2 N_w + 1] \right ) \\
& \simeq & -\frac{4}{3} \kappa^2 \log \epsilon \frac{w_{\rm max}^2}{\pi^2 \delta_A} N_w\end{aligned}$$

Theoretical Performance Comparison for Gridding {#sec:perf_comparison}
===============================================

We consider the gridding problem for two scenarios, $L=1$ and $L=2$. We assuming $\delta_A=1$ pixel, a required accuracy of $\epsilon=10^{-3}$, a 1 degree field of view and a 6 km maximum baseline at $\lambda = 0.2$ giving a $w_{\rm max}$ of $30 k \lambda$. The convolution function size at maximum $w$ of $M_{\rm wmax}=191$ pixels. We assume the cost of evaluating a complex exponential is $N_{\rm cexp} = 100$ flops. This estimate is also justified by measurements of our implementation (Fig. \[fig:procratio\_vs\_w\]).

The FGT method for $L=1$ and $L=2$ is outperformed by standard gridding both in terms of operations and memory bandwidth, if cheating is not enabled (Figure \[fig:fgt\_vs\_gridding\]). For the $L=1$ case in particular, the operations count is dominated by the complex exponential.

If cheating is enabled, then the situation is substantially improved. Once the $w$ value reaches above a certain threshold, the order $q' = 0$, and only one Taylor coefficient is updated per box. In the $L=1$ case, the memory bandwidth is reduced to 0.5 of the 