3 ms·

What is the fastest algorithm for multiplication of two n-digit numbers? What is the fastest algorithm for matrix multiplication? I think those "What is the f

What is the fastest algorithm for multiplication of two n-digit numbers? What is the fastest algorithm for matrix multiplication? I think those "What is the fastest" questions are relative. In my opinion, they are not unsolved problem. There are already solutions for them. And in those current solutions, there is of course the fastest. When a faster algorithm is formulated, a time will come where another algorithm will perform much better. EDIT: Now I get it. That "fastest" is in terms of time complexity. Thanks guys. :)

ginko 13y ago
I believe fastest in this context means that it has been proven that there can be no faster algorithm.
- MojoJolo 13y ago
  Is it really possible? I believe the "fastness" of something is infinite because of numbers being endless.
  - olalonde 13y ago
    The "fast" here refers to the complexity of the algorithm. http://en.wikipedia.org/wiki/Computational_complexity_theory http://en.wikipedia.org/wiki/Computational_complexity_theory
- wlievens 13y ago
  Indeed, in terms of complexity theory I would guess, not in terms of milliseconds.
  - jd007 13y ago
    Read http://en.wikipedia.org/wiki/Big_O_notation http://en.wikipedia.org/wiki/Big_O_notation Basically it's talking about time complexity, or how fast does the time it takes to compute the solution grow as the input grows in size.
  - ginko 13y ago
    An Algorithm with a lower time complexity will always take a shorter amount of time once the problem size grows large enough. You could run one algorithm on a modern cpu, utilizing Simd and tune for cache coherency and the other in QBASIC on an old 386 and the O(n log n) algorithm would still terminate earlier than the O(n^2) one past a certain n.
    - ufo 13y ago
      the problem is that while dropping from n^2 to n log n is a big deal, dropping from (n log n) to n won't help much if you end up increasing the constant costs at the same time.
      - tel 13y ago
        It will eventually. Practical problems are pretty much solved.
fractalsea 13y ago
With regards to matrix multiplication[1]: I think the hidden subtext here is that many people believe there exists a O(n^2) algorithm for matrix multiplication, but it has not been discovered yet. [1] Wouldn't be surprised if this is the case for the other problem too, although I don't know much about it.
- amund 13y ago
  Ran Raz proved that Matrix Inversion is O(n^2 lg n), ref: Ran Raz. On the Complexity of Matrix Product. SIAM Journal on Computing, 32(5):1356–1369, 2003. Based on that I deduced that Matrix Multiplication is O(n^2 lg n), http://amundtveit.info/publications/2003/ComplexityOfMatrixInversion.pdf http://amundtveit.info/publications/2003/ComplexityOfMatrixI... Regarding even faster operations, it has been hypothetized that all matrices are Toeplitz or Hankel (which have O(n lg n) algorithms), ref: D. S. Mackey, N. Mackey, and S. Petrovic. Is Every Matrix Similar to a Toeplitz Matrix. Linear Algebra & its Applications, 297:87105, 1999. But that was proved to not be the case: T. Amdeberhan and G. Heinig - http://www-math.mit.edu/~tewodros/georgmemoriam.pdf http://www-math.mit.edu/~tewodros/georgmemoriam.pdf
jd007 13y ago
It's talking about big O time complexity, which means you have to prove that there can be no faster algorithm. For example comparison sort (so no radix) can be no faster than O(nlogn).

ginko 13y ago

I believe fastest in this context means that it has been proven that there can be no faster algorithm.

MojoJolo 13y ago
Is it really possible? I believe the "fastness" of something is infinite because of numbers being endless.
- olalonde 13y ago
  The "fast" here refers to the complexity of the algorithm. http://en.wikipedia.org/wiki/Computational_complexity_theory http://en.wikipedia.org/wiki/Computational_complexity_theory
wlievens 13y ago
Indeed, in terms of complexity theory I would guess, not in terms of milliseconds.
- jd007 13y ago
  Read http://en.wikipedia.org/wiki/Big_O_notation http://en.wikipedia.org/wiki/Big_O_notation Basically it's talking about time complexity, or how fast does the time it takes to compute the solution grow as the input grows in size.
- ginko 13y ago
  An Algorithm with a lower time complexity will always take a shorter amount of time once the problem size grows large enough. You could run one algorithm on a modern cpu, utilizing Simd and tune for cache coherency and the other in QBASIC on an old 386 and the O(n log n) algorithm would still terminate earlier than the O(n^2) one past a certain n.
  - ufo 13y ago
    the problem is that while dropping from n^2 to n log n is a big deal, dropping from (n log n) to n won't help much if you end up increasing the constant costs at the same time.
    - tel 13y ago
      It will eventually. Practical problems are pretty much solved.

fractalsea 13y ago

With regards to matrix multiplication[1]: I think the hidden subtext here is that many people believe there exists a O(n^2) algorithm for matrix multiplication, but it has not been discovered yet. [1] Wouldn't be surprised if this is the case for the other problem too, although I don't know much about it.

amund 13y ago
Ran Raz proved that Matrix Inversion is O(n^2 lg n), ref: Ran Raz. On the Complexity of Matrix Product. SIAM Journal on Computing, 32(5):1356–1369, 2003. Based on that I deduced that Matrix Multiplication is O(n^2 lg n), http://amundtveit.info/publications/2003/ComplexityOfMatrixInversion.pdf http://amundtveit.info/publications/2003/ComplexityOfMatrixI... Regarding even faster operations, it has been hypothetized that all matrices are Toeplitz or Hankel (which have O(n lg n) algorithms), ref: D. S. Mackey, N. Mackey, and S. Petrovic. Is Every Matrix Similar to a Toeplitz Matrix. Linear Algebra & its Applications, 297:87105, 1999. But that was proved to not be the case: T. Amdeberhan and G. Heinig - http://www-math.mit.edu/~tewodros/georgmemoriam.pdf http://www-math.mit.edu/~tewodros/georgmemoriam.pdf

jd007 13y ago

It's talking about big O time complexity, which means you have to prove that there can be no faster algorithm. For example comparison sort (so no radix) can be no faster than O(nlogn).