1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ This question may be better suited for CS forum, or possibly physics. And don't say "Colon". Does that expression for the Qletric force remind you of anything? Convolution, for instance? $\endgroup$ Commented May 13, 2014 at 9:23
  • $\begingroup$ en.wikipedia.org/wiki/Coulomb%27s_constant $\endgroup$ Commented May 13, 2014 at 9:31
  • $\begingroup$ hi orion thanks for the help :) in my country we say coulon law so it was my mistake :) $\endgroup$ Commented May 13, 2014 at 9:32
  • 1
    $\begingroup$ It's french, it's supposed to sound strange, it's just spelled that way. $\endgroup$ Commented May 13, 2014 at 9:34

1 Answer 1

Reset to default
2
$\begingroup$

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 $$

$\endgroup$
5
  • $\begingroup$ thanks for the answer but sorry.. I don't see and understand why to doing it. each particle i is found on point (i,0). I have n points. the force that act on each particle is Fi (given by the formula). what the question is ask to do is to calc for each particle it's Fi. $\endgroup$ Commented May 13, 2014 at 15:00
  • $\begingroup$ if i put some values for i and j , i see that some calculations are repeating.. so i understand why the question require to use the FFT algorithm, because it ignore half calculations (am i right?) $\endgroup$ Commented May 13, 2014 at 15:03
  • $\begingroup$ No. You are not understanding the FFT properly. Without FFT, n^2 or using the symmetry, n^2/2 operations are necessary. With FFT this reduces to $O(n\log(n))$, which for large $n$ will be much smaller. $\endgroup$ Commented May 13, 2014 at 15:18
  • $\begingroup$ thanks. if I understand right the formula of Fi is for each single particle. so the data-set is the points that represent the position of each particle on the plane. right? so what i need to do is to perform the FFT algorithm on those points? $\endgroup$ Commented May 13, 2014 at 17:16
  • $\begingroup$ as i see the Fi formula, it's look like polynomials, with FFT we can transform from a coefficients representation into points representations, and this is confusing me on how to use the FFT to solve this problem $\endgroup$ Commented May 13, 2014 at 17:18

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.