The recently proposed O(n log n) integer multiplication algorithm [pdf]

1 comments

• flebron 2 minutes ago
  Note in this case the title says "O(n log n)", but the important part is this is "o(n log n)", not just "O(n log n)'. The former is a strict subset of the latter. We already knew how to multiply two n-bit integers in O(n log n) time, via the FFT.