2

Will there be some issues using multiplication with FFT(fast fourier transform)? I am curious. Thanks.

Junyoung Heo
  • 23
  • 3

1 Answers1

5

I assume by "FFT" you're referring to something like Schönhage–Strassen. The answer is likely that this algorithm, while asymptotically faster than Karatsuba, is more complicated and only achieves this advantage on very large numbers due to larger constant factors (Wikipedia quotes multiple sources that cut over to this algorithm only when the multiplicands have tens of thousands of digits).

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • exactly FFT brings big overhead However there are more issues than just speed with FFT. The major one is accuracy as floating point tend to round off sub-results... Luckily NTT can be used instead to avoid floating point rounding errors and also to improve speed as it uses just integer modular arithmetics and no complex numbers either. For more info and comparisons see my quest for [Fast bignum square computation](https://stackoverflow.com/q/18465326/2521214). Also Its more likely the multiplication algorithm is chosen by the bit-width of operands between Karatsuba and Schönhage–Strassen – Spektre Jan 31 '21 at 20:19