Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Use Cooley-Tukey FFT to accelerate prediction. #8

Closed
tiger2005 opened this issue Mar 19, 2023 · 3 comments
Closed

Use Cooley-Tukey FFT to accelerate prediction. #8

tiger2005 opened this issue Mar 19, 2023 · 3 comments
Assignees
Labels
enhancement New feature or request

Comments

@tiger2005
Copy link

tiger2005 commented Mar 19, 2023

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
Copy link
Owner

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

@tiger2005
Copy link
Author

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

@baoliay2008 baoliay2008 self-assigned this Sep 2, 2023
@baoliay2008 baoliay2008 added the enhancement New feature or request label Sep 2, 2023
@baoliay2008
Copy link
Owner

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

2 participants