2 ms·
According to the article, Schönhage and Strassen introduced the use of fast Fourier transform to integer multiplication in 1971, giving n × log n × log(log n).
by eesmith 8y ago
According to the article, Schönhage and Strassen introduced the use of fast Fourier transform to integer multiplication in 1971, giving n × log n × log(log n). "The technique has been the basis for every fast multiplication algorithm since."
"Over the past decade, mathematicians have found successively faster multiplication algorithms, each of which has inched closer to n × log n, without quite reaching it. Then last month, Harvey and van der Hoeven got there."