1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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

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

  2. Complex no (Replies: 2)