# What is the circuit depth of asymptotically fast multiplication algorithms?

I know the circuit depth (i.e. amount of sequential operations on the longest path) for long multiplication can easily be made $$O(\log(n))$$ (possibly at the cost of increasing the computational complexity by a small constant factor), and I’m pretty sure the same applies to Karatsuba and Toom-Cook. However, I don’t understand enough about the asymptotically faster algorithms (e.g. Schönhage–Strassen or faster) to know their circuit depth. Are they also $$O(\log(n))$$ or is there something inherently sequential about them, effectively creating a complexity-parallelizability trade off.

• Please define at least circuit depth for the purpose of this question (and in context of parallel-computing - I'm unsettled by worst case depth of a combinational difference, if not before). And try to characterise the asymptotically faster algorithms: Schönhage–Strassen to Harvey–van der Hoeven? How do I increase the computational complexity? Jul 22 at 4:11
• @greybeard I hope I addressed most of your questions. I want to know if there is a lower bound on how quickly (wall clock) a supercomputer could multiply extremely large numbers (from 10GB to 10TB), with out sacrificing too much complexity relative to the best non-wall-clock-optimized algorithm.
– Nic
Jul 22 at 14:48