Furer's algorithm ( Multiplication)

Time Complexity

$O(n \log n {2}^{O(\log*n)})$

Space Complexity

$O(n)$ auxiliary? bits

(Depends on DFT/FFT algorithm (though original source describes its own algorithm)? but all vectors/numbers are of size O(n) and there are a constant number of such objects)

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM?

Year

2007

Reference

https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf