3 ms·
No, Karatsuba multiplication is not linearithmic. Karatsuba multiplication takes time about n^1.58 (as opposed to n^2 in naive multiplication)
by 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 agoAh, my mistake.
- dreamcompiler 5y agoKaratsuba is generally used for numbers that are too big for ordinary (convolutional) multiplication but too small for Fourier transform multiplication to be worthwhile.