Use Cooley-Tukey FFT to accelerate prediction.

[tiger2005]

During the Elo rating system, calculating $f(x) = \sum \dfrac{1}{1 + 10^{x - R_i}}$ each time in linear complexity is actually a waste of time. By using FFT, we can calculate $f(x)$ for all $x \in \mathbb{Z}$ and $x \in [0, 8000]$.

You can check out here to learn how python make it done. In short, set $g(x)$ as the count of people with a rating $x$, and $h(x) = \dfrac{1}{1 + 10^{x}}$. By computing $g(x)$ and $h(x)\ \ (x \in [-8000,8000])$, we can use a FFT to convolve these two functions, thus calculates $f(x)$.

In Leetcode, I think we can multiply each rating by 10 and round them to integers. The lengths of arrays will be bigger than usual, but the complexity of this algorithm is still perfect. $O(10M \log (10M) + n \log M)$ is way smaller than $O(N^2 \log M)$.

[baoliay2008]

Greetings, @tiger2005 . Your advice is truly valuable and I will definitely take it into consideration.

[tiger2005]

Note: The formula of $f(x)$ is modified.

[baoliay2008]

Hi, @tiger2005 FFT has been incorporated into this project. I will utilize this new FFT function to implement additional computation-intensive functionalities and will upload a benchmarking report later.