# What are some examples of galactic algorithms that have become practical?

On the Wikipedia article for galactic algorithm (an algorithm that only becomes efficient when the inputs are so large that the algorithm is not used in practice), one of the use cases is that

Available computational power may catch up to the crossover point, so that a previously impractical algorithm becomes practical.

What are some examples of this happening?

I'm looking specifically for impractical algorithms that became practical because problem sizes got larger or computers got faster, and not because of improvements to the algorithm itself that made it practical.

• If the problem size becomes larger, not sure this could make the computation more feasible? It seems only computers going faster could help? May 19, 2023 at 18:21
• @Frank The point, I think, is that a problem may get to be large enough that the "Galactic" algorithm is actually faster than the traditional algorithm. Yes, faster computers will be necessary, but at some point the GA is faster than the TA and we still switch since there's no point in wasting cycles. May 19, 2023 at 21:54
• @MarkOlson OK, I see. May 19, 2023 at 22:17

One example would be Strassen’s matrix multiplication algorithm which can be more efficient than the conventional $$O(n^{3})$$ algorithm for large enough matrices. Unfortunately, there are numerical stability issues that can make it unsuitable in many applications.
• See also here: eprint.iacr.org/2013/107.pdf ; the number of arithmetical operations needed by Stassen algorithm is $7n^5-6n^2$, so it cannot be considered a galactic algorithm (where the hidden constant are in the order of the atoms of the Universe); moreover several efficient variant are proposed and the numerical stability is not an issue over a finite field. However, it is true that on current architectures, a highly optimized traditional multiplication can overcome Strassen method for matrices of order 512, see t.ly/lBP5 May 28, 2023 at 15:46