3 ms·

I only skimmed the paper but is this essentially the same thing as Karatsuba multiplication (which I believe also has O(n log n) performance)?

• curtisf 5y ago
  No, Karatsuba multiplication is not linearithmic. Karatsuba multiplication takes time about n^1.58 (as opposed to n^2 in naive multiplication)
  • davesque 5y ago
    Ah, my mistake.
  • dreamcompiler 5y ago
    Karatsuba is generally used for numbers that are too big for ordinary (convolutional) multiplication but too small for Fourier transform multiplication to be worthwhile.