search

catid / leopard

Leopard-RS : O(N Log N) MDS Reed-Solomon Block Erasure Code for Large Data
BSD 3-Clause "New" or "Revised" License
137 stars 24 forks source link

Investigate Frobenius Additive FFT #5

Open catid opened 6 years ago

catid commented 6 years ago

I believe this can be a drop-in replacement for the FFT that is currently being used: https://arxiv.org/pdf/1802.03932.pdf

More background: http://www.texmacs.org/joris/ffft/ffft.pdf

catid commented 4 years ago

~5x faster for 16-bit field, ~3x faster for 8-bit field hypothetically:

affft.test_fft(8) FFT performance for k=8 : 2304 adds, 2304 muladds IFFT performance for k=8 : 2304 adds, 2304 muladds Test successful! Output = Input affft.test_affft2(8) FAFFT2 performance for k=8 : 656 adds, 656 muladds IFAFFT2 performance for k=8 : 176 adds, 656 muladds Test successful! Output = Input

affft.test_affft2(16) FAFFT2 performance for k=16 : 198656 adds, 198656 muladds IFAFFT2 performance for k=16 : 71680 adds, 198656 muladds Test successful! Output = Input affft.test_fft(16) FFT performance for k=16 : 1114112 adds, 1114112 muladds IFFT performance for k=16 : 1114112 adds, 1114112 muladds Test successful! Output = Input

TheBlueMatt commented 4 years ago

Is the code for this somewhere I can test? :p

catid commented 4 years ago

Maybe one day :)