Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Computational complexity

  1. Sep 21, 2006 #1


    User Avatar
    Science Advisor
    Homework Helper

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

    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. jcsd
  3. Sep 22, 2006 #2
    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.
  4. Sep 22, 2006 #3


    User Avatar
    Science Advisor
    Homework Helper

    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 [itex]n\log n[/itex] operations (although whether it's possible to solve this in [itex]O(n)[/itex] operations is a major open problem)."
    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.
  5. Sep 23, 2006 #4
    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Computational complexity
  1. Complex Complex (Replies: 4)

  2. Complex no (Replies: 2)