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.
$\begingroup$
$\endgroup$
2
-
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$– greybeardJul 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$– NicJul 22 at 14:48
Add a comment
|