I wrote a much more in-depth analysis of Schonhage-Strassen and why exactly it's an O(N log N log log N) algorithm here: https://psun.me/post/fft2/
It's pretty interesting--it's actually a recursive multiplication algorithm with log log N levels of recursion and N log N work at each level. And it actually uses another fast multiplication algorithm within it, the Karatsuba algorithm.
It's pretty interesting--it's actually a recursive multiplication algorithm with log log N levels of recursion and N log N work at each level. And it actually uses another fast multiplication algorithm within it, the Karatsuba algorithm.