# Calculating force between n points placed on the x-axis

There are $n$ charges placed on the x-axis at points $1,2,3,\dots,n$. We need to calculate the force on each charge by every other charge. I need the exact force. Charges can be arbitrary. Inputs are the charges possibly in the form of an array. Force is defined in the usual physical way.

I know an $O(n^2)$ algorithm to do the task. However, it can be done in $O(n\log n)$.

I have read about FFT, but I don't know how to apply it here. I know that we can multiply two degree $n$ polynomials in $O(n\log n)$. This problem is similar to that problem. Any help will be appreciated.

Suppose that the charges are $q_1,\ldots,q_n$. You need to calculate, for all $i$, $$F_i = q_i \sum_{j>i} \frac{q_j}{(i-j)^2} - q_i \sum_{j<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 & 1 & \frac{1}{4} & \frac{1}{9} & \cdots & \frac{1}{(n-1)^2} \\ -1 & 0 & 1 & \frac{1}{4} & \cdots & \frac{1}{(n-2)^2} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2} & \frac{-1}{(n-4)^2} & \cdots & 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 & 1 & \frac{1}{4} & \frac{1}{9} & \cdots & \frac{1}{(n-1)^2} & \frac{-1}{(n-1)^2} & \cdots & -1 \\ -1 & 0 & 1 & \frac{1}{4} & \cdots & \frac{1}{(n-2)^2} & \frac{1}{(n-1)^2} & \cdots & \frac{-1}{4} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2} & \frac{-1}{(n-4)^2} & \cdots & 0 & 1 & \cdots & \frac{1}{(n-1)^2} \\ \frac{1}{(n-1)^2} & \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2} & \cdots & -1 & 0 & \cdots & \frac{1}{(n-2)^2} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ 1 & \frac{1}{4} & \frac{1}{9} & \frac{1}{16} & \cdots & \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \cdots & 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.