-
Notifications
You must be signed in to change notification settings - Fork 27
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
Faster polynomial multiplication #45
Comments
@jonasvanderschaaf Thanks for great suggestion! |
To implement a Fast Fourier Transform, I would need to have access to some implementation of complex numbers. This would probably mean that the addition of this feature would have to be moved to version 0.31, as #35 (complex number support) is also scheduled for this version. |
Oh, sorry for my mistake. I fixed it. |
The current polynomial multiplication has a runtime of O(n^2). This is fine for some cases (especially lower degree polynomials), but is suboptimal, as it is relatively easy to reduce the runtime using a Fast Fourier Transformation to O(n log n). This would be a considerable speedup for higher degree polynomials.
I think it would be best to perhaps use the currrent algorithm for polynomials of low degree, as it is undoubtedly faster for these kinds, but for higher degree polynomials switch to the more complex, but asymptotically faster FFT. The switching point should of course be determined by the implementation details.
If this is something worth considering, I think there would be three ways to go about using this method:
If you think that the second option sounds appealing, I would be willing to write an implementation of the algorithm.
The text was updated successfully, but these errors were encountered: