Peroxide icon indicating copy to clipboard operation
Peroxide copied to clipboard

Use FFT algorithm for faster polynomial multiplication

Open jonasvanderschaaf opened this issue 2 years ago • 0 comments

This pull request will contain an implementation of the Cooley-Tukey Fast Fourier Transform algorithm, and use it to speed up polynomial multiplication for high degree polynomials. More information can be found in issue #45.

This pull request will contain the following features:

  • [x] An implementation of the Fast Fourier Transform
  • [x] A modification to the polynomial multiplication code to use this algorithm for high degree polynomial multiplication
  • [x] Tests covering most vital functions to ensure proper functioning of multiplication
  • [ ] Benchmarking and optimizing the algorithm

jonasvanderschaaf avatar Aug 05 '21 20:08 jonasvanderschaaf