Computational complexity

1. Sep 21, 2006

CRGreathouse

'Schoolbook' multiplication takes $O(n^2)$ operations. Karatsuba multiplication takes $O(n^{\lg 3})\approx O(n^{1.59})$ operations. The best method I know of (which is only practical for very large numbers) is $O(n \log n \log\log n)$.

Is there a known nontrivial lower bound on the complexity of multiplication? I read a paper that discussed the time-(silicon) area tradeoff on multiplication, but I wasn't able to get a useful bound from that (caring only about the time and not knowing how to 'remove' the area):
The Area-Time Complexity of Binary Multiplication

Can anyone help me out here?

2. Sep 22, 2006

chronon

Well Donald Knuth's The Art of Computer Programming, Volume 2: Seminumerical Algorithms has a chapter entitled How fast can we multiply and if I remember correctly he comments on the lack of a lower bound for multiplication algorithms. However, that was written over 35 years ago, so you'd think that there'd have been some progress since then. I tried searching for papers with references to that chapter of Knuth's book, but didn't find very many of them.

3. Sep 22, 2006

CRGreathouse

Yeah, I've been searching but haven't found anything. I hoped the new Algorithms by Dasgupta, Papadimitriou, and Vazirani might have something, but no such luck. I don't have a copy of Knuth's book or that's where I would have started (old as it is).

I did find something online, but I don't think I trust it: "Surprisingly, there are several better [multiplication] algorithms, taking as few as $n\log n$ operations (although whether it's possible to solve this in $O(n)$ operations is a major open problem)."
http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec1.pdf
What do you think? On one hand it supports what you remember reading; on the other, it's written for a basic audience and (seems to) misquote the complexity of (what I presume to be) S-S multiplication.

4. Sep 23, 2006

chronon

No, I don't believe the n log n claim either. I did find http://www.csc.liv.ac.uk/~ped/teachadmin/algor/complex.html which reports it as a conjecture, but even then I'm doubtful - I would have thought that an n log n algorithm would be straightforward enough to have been found by now. It looks like S-S is still the optimum. The lack of a good lower bound isn't particularly surprising, proving such things is never easy.