feat(fft): add fft/ifft

snarkify / sirius

A Plonkish folding framework for Incrementally Verifiable Computation (IVC).

MIT License

106 stars 15 forks source link

feat(fft): add fft/ifft #271

Closed chaosma closed 1 month ago

chaosma commented 1 month ago

Issue Link / Motivation close #258 In protogalaxy, there are several places need fft/ifft, e.g. when prover wants to compute F, G and K

Changes Overview

root of unity generation for a given fft domain size.
fft and ifft function. The fn best_fft is imported from halo2curves.
unit test for random inputs

cyphersnake commented 1 month ago

Also a question, shouldn't we test this solution with some synthetic example? I'm not sure that the functions I gave above work exactly, since the only thing that is checked is that ifft is the inverse of fft

bbarbakadze commented 1 month ago

Also a question, shouldn't we test this solution with some synthetic example? I'm not sure that the functions I gave above work exactly, since the only thing that is checked is that ifft is the inverse of fft

Agree, convolution test would be good.

chaosma commented 1 month ago

Also a question, shouldn't we test this solution with some synthetic example? I'm not sure that the functions I gave above work exactly, since the only thing that is checked is that ifft is the inverse of fft

I had tested it locally. One more test example added.