4 ms·
How does this beat Schonhage-Strassen (which is the standard way to do IDFT(DFT(a)*DFT(b)) ) by a factor of loglog(n)? IIRC nlog(n) was only achieved in 2019.
by nimish 5y ago
How does this beat Schonhage-Strassen (which is the standard way to do IDFT(DFT(a)*DFT(b)) ) by a factor of loglog(n)? IIRC nlog(n) was only achieved in 2019.
- pkhuong 5y agoThe analysis assumes constant-time arithmetic for the Fourier transforms. This limits the size of the multiplicands, since the error terms eventually grow large enough to affect the computed product. From the paper: "Note that this error is due to the limited precision in which we can represent numbers on computers, it does not occur in exact arithmetic." But of course, exact reals (twiddle factors aren't rational) are rife with undecidability if not uncomputability.