Calculating force between n points placed on the x-axis
Suppose that the charges are $q_1,\ldots,q_n$. You need to calculate, for all $i$,
$$
F_i = q_i \sum_{j&gt;i} \frac{q_j}{(i-j)^2} - q_i \sum_{j&lt;i} \frac{q_j}{(i-j)^2}.
$$
In matrix form, we get
$$
\begin{bmatrix}
F_1/q_1 \\ F_2/q_2 \\ \vdots \\ F_n/q_n
\end{bmatrix} =
\begin{bmatrix}
0 &amp; 1 &amp; \frac{1}{4} &amp; \frac{1}{9} &amp; \cdots &amp; \frac{1}{(n-1)^2} \\
-1 &amp; 0 &amp; 1 &amp; \frac{1}{4} &amp; \cdots &amp; \frac{1}{(n-2)^2} \\
\vdots &amp; \vdots &amp; \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\
\frac{-1}{(n-1)^2} &amp; \frac{-1}{(n-2)^2} &amp; \frac{-1}{(n-3)^2} &amp; \frac{-1}{(n-4)^2} &amp; \cdots &amp; 0
\end{bmatrix}
\begin{bmatrix}
q_1 \\ q_2 \\ \vdots \\ q_n
\end{bmatrix}
$$
What the FFT allows us to do is to quickly multiply by a circulant matrix. In order to obtain a circulant matrix, all you have to do is add $n-1$ dummy coordinates:
$$
\begin{bmatrix}
F_1/q_1 \\ F_2/q_2 \\ \vdots \\ F_n/q_n \\ \ast \\ \vdots \\ \ast
\end{bmatrix} =
\begin{bmatrix}
0 &amp; 1 &amp; \frac{1}{4} &amp; \frac{1}{9} &amp; \cdots &amp; \frac{1}{(n-1)^2} &amp; \frac{-1}{(n-1)^2} &amp; \cdots &amp; -1 \\
-1 &amp; 0 &amp; 1 &amp; \frac{1}{4} &amp; \cdots &amp; \frac{1}{(n-2)^2}  &amp; \frac{1}{(n-1)^2} &amp; \cdots &amp; \frac{-1}{4} \\
\vdots &amp; \vdots &amp; \vdots &amp; \vdots &amp; \ddots &amp; \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\
\frac{-1}{(n-1)^2} &amp; \frac{-1}{(n-2)^2} &amp; \frac{-1}{(n-3)^2} &amp; \frac{-1}{(n-4)^2} &amp; \cdots &amp; 0 &amp; 1 &amp; \cdots &amp; \frac{1}{(n-1)^2} \\
\frac{1}{(n-1)^2} &amp; \frac{-1}{(n-1)^2} &amp; \frac{-1}{(n-2)^2} &amp; \frac{-1}{(n-3)^2}  &amp; \cdots &amp; -1 &amp; 0 &amp; \cdots &amp; \frac{1}{(n-2)^2} \\
\vdots &amp; \vdots &amp; \vdots &amp; \vdots &amp; \ddots &amp; \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\
1 &amp; \frac{1}{4} &amp; \frac{1}{9} &amp; \frac{1}{16} &amp; \cdots &amp; \frac{-1}{(n-1)^2} &amp; \frac{-1}{(n-2)^2} &amp; \cdots &amp; 0
\end{bmatrix}
\begin{bmatrix}
q_1 \\ q_2 \\ \vdots \\ q_n \\ 0 \\ \vdots \\ 0
\end{bmatrix}
$$
We don't really care about the $n-1$ asterisked entries. The new matrix is $(2n-1)\times(2n-1)$, and so FFT still runs in $O(n\log n)$. Of course, if your FFT works only for powers of 2, you need an extra padding step.