我需要帮助对大量数据执行 FFT

Question

我正在设计一个电路，需要对非常大的数字（大至几兆字节，以您认为最好的任何合理寄存器长度存储在存储器中）运行 FFT。我想对这个数字运行 FFT 作为将它们相乘的方法。

我怎样才能以绝对精度（所以没有浮点数）来做到这一点，并且一般情况下尽可能使用最少数量的非整数？

Answer 1

你基本上有两个选择：

1. 以浮点形式进行 FFT，具有足够的精度，以保证四舍五入为整数时结果准确。
2. 使用数论变换代替 FFT。这会将复数替换为素数模数的整数余数。