How to use FFT algorithm Given a set  of n particles electric charge carriers founds on the points (1,0), (2,0), .... (n,0) on a plane. 
The particle charge that found in point (i,0) is noted as Qi. the force that act on the particle is given by the formula: 
Fi =  $\sum_{j=1}^{i-1}\frac{CQiQj}{(i-j)^2}-$ $\sum_{j=i+1}^{n}\frac{CQiQj}{(i-j)^2}$ 
C is a Coulomb's constant.
Give an algorithm to calculate Fi, for all of the particles in total complexity O(nlgn).
Hint: use FFT algorithm.
It seems that Fi is already divided to the even and odd points..
I thought about to divide each sum to calculate the FFT (but divide until what..?) and
then sum always half of the points (cause this is what FFT cause) and then subtract the result of the sums that given on the formula.. 
any idea of how to do it better? 
 A: Schönhage once presented a trick to speed up Taylor shifts in polynomials. Since
$$
p(t+h)=\sum_ka_k\sum_i\binom ki t^ih^{k-i}=\sum_{0\le i\le k}(k!a_k)\frac{h^{k-i}}{(k-i)!} \cdot \frac{t^i}{i!}
$$
you can represent the computation of the coefficients of $t^i/i!$ as the convolution of the, convieniently zero padded, sequences $a_0,a_1,2a_2,3!a_3,...,n!a_n$ and $h^n/n!, h^{n-1}/(n-1)!,...h^3/3!,h^2/2,h,1$. This convolution can then be computed via FFT.
Your situation is very similar if you factor out the factors $CQ_i$ in $F_i$, i.e., the sequence of $F_i/(CQ_i)$ can be represented as a convolution product...

... of the sequences $$(Q_i)=(Q_1,...,Q_n)$$ and $$C_j=(-\frac1{(n-1)^2},-\frac1{(n-2)^2},...,-\frac14,-1,0,1,\frac14,...,\frac1{(n-1)^n}),$$ the latter padded with $n-1$ zeros at the end, the first padded with $2(n-1)$ zeros at the end to match the length.

$$
\sum_{i=1}^n\frac{F_i}{CQ_i}z^i=\sum_{i=1}^n c_{i-j}z^{i-j}\cdot Q_jz^j=\text{ segment($1..n$) of }\sum_{j=-n+1}^{n-1}c_jz^j\cdot\sum_{k=1}^n Q_kz^k
$$
