search

ejmahler / RustFFT

RustFFT is a high-performance FFT library written in pure Rust.
Apache License 2.0
678 stars 47 forks source link

A million downloads! #118

Closed HEnquist closed 3 months ago

HEnquist commented 1 year ago
Screenshot 2023-05-10 at 20 54 16

Just saw this on crates.io, had to share but couldn't think of a better place than here :D

WalterSmuts commented 1 year ago

Woot woot!

ejmahler commented 1 year ago

You love to see it. A lot of hard work has gone into it from a lot of people at this point.

For me, it started with splines. You can't compute the arc length of a catmull-rom spline analytically, you have to compute a numeric integral. I looked into what numeric integral algorithms were available, and one that stuck out to me was clenshaw-curtis quadrature. That requires computing some setup data, taking the dct-1 of that data, then using the output as weights for a bunch of samples of your function. So I looked at what dct-1 libraries there were in rust, and there were none. So I looked into implementing it myself, and realized that your choices are either the O(n^2) algorithm, or forward to FFT. So I looked into what FFT libraries were available, and I found this one - but at the time, it only supported prime factors of 2, 3, and 5, everything else got computed with an O(k^2) algorithm, where k is n with all the factors of 2,3,and 5 removed. And the size I'd need, in particular, would be done with the quadratic algorithm. So I started looking into algorithms that could do arbitrary factorizations (Mixed Radix, Good-Thomas), and algorithms that were O(nlogn) even for prime sizes. But once I had those, I needed to add a system that could choose different algorithms based on input size, etc. And 7 years later here we are.

https://www.youtube.com/watch?v=AbSehcT19u0

I never did get around to implementing clenshaw-curtis quadrature for my spline thing.

ejmahler commented 3 months ago

A year later, we're at 2 million. Seems like a good time to close this <3