4 ms·
Sorry to be pedantic but multiplication requires O(n ln(n)) not O(n^2) [1]. [1] https://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_method
by abetusk 11y ago
Sorry to be pedantic but multiplication requires O(n ln(n)) not O(n^2) [1].
[1] https://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods https://en.wikipedia.org/wiki/Multiplication_algorithm#Fouri...
- dnautics 11y agooh! very cool. Thanks! I knew about toom-cook, and based on what I do I figured it could be faster by breaking up into 'bigger power of 2 digits'. Now I know for sure (without having to implement it myself). Realistically though, you're not gonna implement a FFT mult on a 64-bit integer/float even. Pedantry is not annoying if it's a learning opportunity (or if it's excellently funny), IMO.