50 ms·
The paper seems to lack a comparison between regular multiplication of large integers and FFT multiplication in base 2.
by nynx 5y ago
The paper seems to lack a comparison between regular multiplication of large integers and FFT multiplication in base 2.
- olliej 5y agoFFT for multiplication and has a well understood complexity of nlogn w.r.t number of digits. “Regular” multiplication could mean n^2 for standard paper arithmetic, n^1.6 for karatsuba, and a few other n^y algorithms with y>1 However as usual in this analysis we have dropped constant factors and the constant factors for FFT are high so you have to be multiplying numbers with at least hundreds of digits if not thousands. Note that the base of the digits isn’t relevant for analytical performance, as it’s a constant factor change