3 releases

0.1.2 Aug 17, 2021
0.1.1 Sep 14, 2020
0.1.0 Sep 11, 2020

#1654 in Math

23 downloads per month
Used in 2 crates

MIT/Apache and LGPL-3.0+

18KB
356 lines

rug-fft

Implementations of the FFT for rug integers.

That is, implementation of the Number Theoretic Transform.

Algorithms

  • Cooley-Tukey, in-place, with bit reversals, iteratively.
  • Cooley-Tukey, partially in-place, recursively
  • Naive

The two Cooley-Tukey variations perform similarly in my (unrigorous tests).

Dependencies

~2.5MB
~47K SLoC