Re:LibBF – a small library to handle arbitrary precision flo...
by dbaupp on Tuesday March 06, 2018 @07:04PM
(#16533282)
"near linear" is sometimes used to refer to O(n log(n)^O(1)), that is, things that are linear other than a polynomial of log(n). This includes Schönhage–Strassen multiplication, with its O(n log(n) log(log(n))) complexity.
I thought the best known multiplication algorithms (the ones based on Fourier transforms) for large numbers are a little slower than O(N log(N)). Has something better been found?