# Furer's algorithm ( Multiplication)

Jump to navigation
Jump to search

## 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)

## Description

## 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