Hacker News Reader

Comment by MojoJolo | Hacker News Reader

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. :)

View on HN

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

Indeed, in terms of complexity theory I would guess, not in terms of milliseconds.

Read 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.

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.

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.

It will eventually. Practical problems are pretty much solved.

Is it really possible? I believe the "fastness" of something is infinite because of numbers being endless.

The "fast" here refers to the complexity of the algorithm. http://en.wikipedia.org/wiki/Computational_complexity_theory

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).

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.

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/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

Reply on news.ycombinator.com