lowest possible complexity for multiplying 2 linked lists representing very large numbers?

Question

I have 2 linked lists representing very large numbers (that cannot be saved in anything else other than a linked list). i have an Add method with the complexity of O(n). i wanted to know if it is possible in any way to multiply the 2 numbers WITHOUT converting the whole list to a String/int/long (calculate ON the list if possible), and keep it on a complexity of O(n^2).

for now, no matter what i try i get to an O(n^3) complexity, and it isnt good enough.

thanks for all the help.

Answer 1

The "long multiplication" algorithm most westerners learn in school already gives you O(n²) complexity, so maybe you could explain what algorithm you are using.

There are algorithms with lower complexity: Karatsuba, Tom-Cook, and Schönhage–Strassen algorithm. The last one has the lowest known complexity know to date, O(n log n log log n), but there may be even better algorithms yet to be discovered.