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]

The paper seems to indicate that the transform can be modified to be as low as 9-dimensional. I don't see why you need 2¹⁷²⁹ bits to fill the array, then: shouldn't this algorithm work for multiplying numbers as small as twenty billion billion? TricksterWolf (talk) 06:26, 23 March 2022 (UTC)[reply]

One of the authors of the paper states "On the other hand, we are hopeful that with further refinements, the algorithm might become practical for numbers with merely billions or trillions of digits." Since the paper mentions the reduction to 9 dimensions, this indicates that although 9 dimensions are clearly better than 1729, still further refinements would be needed to make it practical. LouScheffer (talk) 13:13, 23 March 2022 (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]

Optimality (simulated annealing) not an example of a galactic algorithm?

The example given of simulated annealing with a logarithmic cooling schedule does not seem to fit the definition of a galactic algorithm as being asymptotically better than practical solutions, unless I am misunderstanding? 2A00:23C6:4C28:9E01:E9CC:320E:F1BE:BFA4 (talk) 16:50, 4 September 2022 (UTC)[reply]

To my knowledge, the asymptotic superiority comes from being able to find the minimum of *any* objective function, no matter how ill-formed. No practical optimization algorithm can make this promise. LouScheffer (talk) 20:29, 4 September 2022 (UTC)[reply]

Two kinds of galactic-ness?

This article mixes up two closely related kinds of galactic. In both cases, the algorithm is better than any used in practice.

In one case (like multiplication), it only excels on impractically large examples.
In other cases (Shannon, Simulated annealing) it gives superior results, but only if impractical amounts of computer power are used.

The second kind was not included in the original definition, but my opinion is that it is in the same spirit - it's a theoretically great algorithm that is not practical. And it has the same benefits as the first kind (inspiring research, showing limits, etc.)

Perhaps a better title might be "Superior but impractical algorithms", but I think "Galactic" is a catchier shorthand for this. LouScheffer (talk) 20:26, 4 September 2022 (UTC)[reply]