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]

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

The practical example of stealth aircraft should be mentioned in the article. A complete theory of radar reflection minimalization was first created by a *soviet* mathematician in 1964 and published in open scientific press, because the resulting equations were considered transcomputable for the foreseeable future. The CIA archived that thesis and checked back on it regularly. By the late 1970s, Moore's Law increased free-world computing power enough that stealth airframe shapes composed of just flat panels could be designed and thus the F-117 was born. By the late 1980s, further increases in CPU / RAM power allowed simulating the radar reflection of elaborate 3D-curved surfaces and the Northrop B-2 Spirit strategic stealth bomber was produced (albeit at the insane price tag of 2 billion then-dollars apiece.) It's similar but smaller and supposedly more affordable cousin, the B-21 Raider has just been unveiled, with her first flight expected in early 2023. 92.249.156.122 (talk) 17:29, 17 December 2022 (UTC)[reply]

Pyotr Yakovlevich Ufimtsev is the name of the soviet scientist mentioned above. 92.249.156.122 (talk) 17:33, 17 December 2022 (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]

Original research

While the concept is understandable, but it seems that this neologism didnt catch up. Therefore the whole article is WP:SYNTH, because refs cired for the examples do not use the term. - Altenmann >talk 02:30, 24 November 2023 (UTC)[reply]

While good faith, I think this viewpoint is incorrect. It is true that many of the algorithms cited do not call themselves by the specific word "galactic", but they include phrases indicating they are not likely to be used in practice, or else critics have noted this for them. In terms of detailed changes, the two sentences marked with "citation needed" are given directly in the first reference, as was the removed section on a hypothetical n^2^100 algorithm for SAT. Since this article is already cited in both the lede and the paragraph, citing each individual sentence seems excessive, though they could be included if editors feel strongly they are needed. As far as the removed section on the travelling salesman problem, this qualifies for the references article's definition, which is "simpler algorithms are used in practice". I've changed the lede to include this additional (cited) definition. LouScheffer (talk) 12:39, 25 November 2023 (UTC)[reply]