Fast Fourier Transform in Rust | Hacker News Reader

Fast Fourier Transform in Rust

github.com

55 pointslogicalguess10 comments

Btw, Rust is big in 'crypto', and for eg Zero Knowledge Proofs we do a lot of Fourier transforms, too. And there's a few implementations in Rust for that.

See https://en.wikipedia.org/wiki/Discrete_Fourier_transform_ove...

This isn't really apples-to-apples comparing with FFTW.

  1. It's been my experience that distros don't configure AVX properly for it, and 
  2. PhastFT takes its inputs de-interleaved in separate real/imaginary arrays which is generally not how complex data is provided, so that overhead doesn't appear in PhastFT.

Hi,

One of the authors of PhastFT here. Thank you for your interest.

We went out of our way to configure FFTW for AVX-512. The Rust bindings don't do it, but the FFTW itself in the benchmark does.

It's worth noting that with FFTW you have to choose between building it for your CPU and making it non-portable, or targeting the lowest common denominator of CPU features so that it runs everywhere but much slower. Meanwhile PhastFT detects the available CPU features at runtime, and will utilize the fastest CPU features without sacrificing portability.

Lastly, we are currently working on support for interleaved format [1]. That should ship in the next release.

[1] https://github.com/QuState/PhastFT/pull/27

FFTW will definitely query cpuid at runtime too, since it's piecing together kernels anyways it's not much more work for it to choose to ignore AVX, etc. If you use the [guru interface](https://www.fftw.org/fftw3_doc/Guru-vector-and-transform-siz...) to configure it to work with split arrays (and maybe use FFTW_MEASURE when planning) I think the benchmarks will be a lot more 1:1

For those who are interested, there is a strong connection between FFT and quantum gates. Applying a gate to a target qubit in a quantum system follows the same computing pattern as one stage in FFT. Consequently, any quantum simulator contains an FFT implementation, and an efficient FFT implementation can be ported to a quantum simulator implementation.

To see how quantum gates work, take a look at Spinoza: https://github.com/QuState/spinoza, a sister project for PhastFT, and Hume, a simpler, but lower performing, Python version: https://github.com/learnqc/code/tree/main/src/hume.

When will Rust be available for the GPU, and will this code work then?

Rust is already available for GPU, kind of: https://github.com/EmbarkStudios/rust-gpu

I don't think it's production ready though and I have no idea if this library should work on this.

How does this differ from outputting wgpu from rust?

I have no idea, I just saw this pop up on reddit again yesterday in a thread[1], I had seen it before and forgotten its existence.

[1]: https://www.reddit.com/r/rust/comments/1cho244/luminal_compi...

wgpu uses WGSL as its shader language, not rust..?

Reply on news.ycombinator.com