Hacker News Reader

Comment by ryao | Hacker News Reader

Is there any reason to think that this algorithm will actually be faster than what is currently done in practice?

For arrays in B-tree nodes, which is the main place where I have encountered this problem, I doubt it will be faster than just using `memmove()`, and for truly large arrays, it would be easier to use a B tree.

If that is the case, this joins a number of algorithms that are asymptotically faster than algorithms in use and paradoxically slower than them. Examples of such algorithms include all of the fast matrix multiplication algorithms, which are slower than good implementations of the the textbook O(n^3) algorithm (GEMM).

View on HN

These are sometimes called Galactic Algorithms: https://en.wikipedia.org/wiki/Galactic_algorithm

The very first example on the page has a pretty good quote describing their usefulness:

>>> An example of a galactic algorithm is the fastest known way to multiply two numbers, which is based on a 1729-dimensional Fourier transform. It needs O(n log n) bit operations, but as the constants hidden by the big O notation are large, it is never used in practice. However, it also shows why galactic algorithms may still be useful. The authors state: "we are hopeful that with further refinements, the algorithm might become practical for numbers with merely billions or trillions of digits."

One interesting thing about working on numbers so large is that it becomes harder to assume that memory access is constant time. It's already not that easy now (cache miss vs hit, and external memory), but when you operate on data sizes that large, memory accesses matter by at least the square or cube root of N. If you require largely sequential access it is possible to outperform an algorithm that requires conditional random access by some function of those factors, which can make some algorithms look much worse or better compared to the classical analysis. Of course, it still does not matter whether your algorithm is going to finish in a couple of trillion years or a trillion trillion years.

Reply on news.ycombinator.com