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.

  • 2
    $\begingroup$ 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? $\endgroup$
    – greybeard
    Jul 22 at 4:11
  • $\begingroup$ @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. $\endgroup$
    – Nic
    Jul 22 at 14:48


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.