Talk:Galactic algorithm

Multiplication algorithm

I think this is WP:SYNTH since in no place does that paper claim that $n_{0}=2^{1729^{1}2}\approxeq 10^{2.148\cdot 10^{38}}$ is the lowest such number, and indeed claims that d = 8, with a substantially smaller value of $d^{12}$ is sufficient. We should instead be vaguer, perhaps saying it needs to be bigger than can be written in the observable universe.--Jasper Deng (talk) 00:30, 14 August 2019 (UTC)[reply]

This is reasonable. I replaced this with a less spectacular but better supported bound, based on the fact that the algorithm is built upon a 1729 dimensional transform. Since each dimension must have a size of > 1, this requires data of at least 2¹⁷²⁹ bits even to fill the array. LouScheffer (talk) 00:18, 15 August 2019 (UTC)[reply]

Citation?

"Computer sizes may catch up to the crossover point, so that a previously impractical algorithm becomes practical."

This makes no sense and isn't cited. Is it correct? Galactic algorithm are impractically because they involve data that isn't in practice used? Increased 'Computer sizes' won't change that. — Preceding unsigned comment added by 61.68.214.83 (talk) 11:02, 5 October 2019 (UTC)[reply]

Data sizes also catch up too. For example, the AKS test at some point must begin outperforming all other known deterministic primality tests, and it's possible that future computer sizes will realize that. The Strassen algorithm would not have been practical on early computers (today's data matrices are far larger than anything back then). Even with quantum computers, Shor's algorithm is arguably galactic at this time as it is impractical for all but the smallest integers at this time, even though we believe we can construct quantum computers of sufficient size to make it more practical than classical algorithms.--Jasper Deng (talk) 11:10, 5 October 2019 (UTC)[reply]

Shannon is not an example

Shannon's coding example is not related to the scale of the input and therefore it is not a galactic algorithm. Full Decent (talk) 17:18, 5 October 2019 (UTC)[reply]

AKS primality test?

The AKS primality test page claims it is a galactic algorithm. I had heard it had this property (though not the moniker galactic when the test was discovered). Any interest in adding this example to our main page, with citations? 72.92.54.85 (talk) 21:35, 3 May 2020 (UTC)[reply]

AKS may or may not be galactic. AKS has a known running time of O(log(n)⁶). Competitor ECPP has an empirical run time of O(log(n)⁵), but no one knows the worst case for it. If the worst case is > O(log(n)⁶), the AKS is galactic, otherwise not. LouScheffer (talk) 17:56, 5 May 2020 (UTC)[reply]