I maybe should have been more explicit: I was referring to the bit-operation cost of big integer multiplication. The only claimed O(n lg n) algorithm for this t

I maybe should have been more explicit: I was referring to the bit-operation cost of big integer multiplication. The only claimed O(n lg n) algorithm for this task [1] notes: > Let n_0 = 2^(d^12) >= 2^4096 and suppose we wish to multiply numbers with n bits. [...] For n > n_0 we will describe a recursive algorithm [...] 2^4096 bits is enormous. That's way way way past the point where you could fit the numbers into the observable universe. Past the point where the expansion of space has become a real problem. You really should just use the O(n lg n lglg n) algorithm instead [2]. Your other comments indicate you work with polynomials with floating point coefficients. Yes, there are O(n lg n) algorithms for that case. And they are very practical. 1: https://hal.archives-ouvertes.fr/hal-02070778v2/document https://hal.archives-ouvertes.fr/hal-02070778v2/document 2: https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...