FFT over large vectors >=2^16 -- FFT_test_exe test1 error in index

[dstarin]

Nice work on the project.

I compiled the library and wanted to benchmark using fft_furer1.cpp over vectors of size >= 2^16.
I'm getting an error when the check is performed. Any idea what the problem could be?

Thanks,
Dan

My .config_furer:
8
180143985094819841
3
2485986994308513793
5

$ ./FFT_test_exe 1 32768
1-D FFTs (sec): 0.006723
pass.

$ ./FFT_test_exe 1 65536
1-D FFTs (sec): 0.003044
error in index 32769!
$ ./FFT_test_exe 1 1048576
1-D FFTs (sec): 0.043169
error in index 2049!

[maliasadi]

Thank you for writing to us.

This test function checks the correctness of an old C++ integration of Furer FFT that only works with particular configurations and this issue might come from a bad one. See PBPAS::DFT_eff which is an up and running integrated version of Furer FFT, and tested rigorously in other modules (e.g., dense univariate polynomials over prime fields (DUSP)). The FFT details can be found here. In addition, we have a brand new 6-step FFT (multi-core supported) published in ISSAC'19 and its test file can be found here.

We will fix this problem properly and get back to you soon.