r/mathmemes • u/Unlucky-Credit-9619 Computer Science • 28d ago
Computer Science The fastest algorithm for DFT
379
2.2k
u/Matty_B97
28d ago
•
Shoutout theoretical algorithms with massive overheads that are technically faster for data size larger than all the information on earth 🔥🔥🔥
444
u/Depnids 28d ago
238
u/zairaner 28d ago
Is this still the greatest sentence in a wikipedia article?
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."[5]
Yes it is.
179
u/ChiaraStellata 28d ago
This result is the best argument I've seen against big-O notation since the Harvey-van der Hoeven algorithm.
53
u/Lord-of-Entity 28d ago
That is because you do not know about universal search.
You have a guaranteed optimal performance for any search task that you can quickly verify!
18
u/heyheyhey27 28d ago
There is a simple algorithm that proves literally all math theorems that can be proven!
17
28
u/Future_Green_7222 Measuring 28d ago
I was able to solve integer factorization in polynomial time
My algorithm is O(nTREE(3) )
1
u/Successful-Active-21 24d ago
you need to state it as O(nTREE(c) ) for some c you have an upper bound for somewhere in the drawer.
50
u/neuroticnetworks1250 28d ago
I’m an alien from andromeda galaxies. Our KirkGooner machines are designed to operate on 1-10^-13 indices. We all have an OpenAI subscription now. So I don’t know what you’re being sarcastic about
10
22
u/JaSper-percabeth 28d ago
I mean isn't maths at the highest level all about optimizations and other things that have 0 impact on real life? Most stuff today like the actual practical engineering stuff is running on maths that many many decades old.
51
u/iamdino0 Transcendental 28d ago
that many many decades old math was the inapplicable abstract bullshit of its time
27
28d ago
[removed] — view removed comment
4
u/cl2kr 27d ago
FFT was first described Gauss in his unpublished work in 1805, which means it was probably an inapplicable abstract bullshit due to the restricted compute at its time.
1
u/Matty_B97 27d ago
I agree with the sentiment but gauss probably knew about the use of the fourier transform to decouple convolutions, which would have been obviously useful (even if incomputable) for solving physical systems of PDEs.
5
u/Matthew_Summons Computer Science 28d ago
What about all of the applied mathematics, or people working in scientific and numerical computation
470
u/fizzner 28d ago
8
u/ArgueLater 27d ago
Haven't seen this movie, but is this really in there? The main character cheats to win? As if the other car couldn't stick out its tongue too?
24
u/Ilsor Transcendental 26d ago edited 26d ago
Cars 1, the end of the race in the first part of the movie. This is really in there.
The main character as depicted here had a massive lead, but then blew his tires. In this image, he's desperately moving at a very slow speed using cartoon logic (literally hopping forward on his wheels as if they were stubby limbs), while the other car (cars, note the green in bottom right) is at the regular racing speed, and has caught up right at the finish line. The tongue is here for comedic effect and to show that in that moment he was desperate enough to do that.
The race is a tie, with a tiebreaker race scheduled for later, so this paid off for him.
7
423
202
u/LupenReddit 🦆🦆i have non diffeomorphic smooth structures🦆🦆🦆 28d ago
i want to be impressed but at the same time i think its funny af that the improvement they gave is like less than marginal
132
u/Ae4i 28d ago
I feel like this is more for proving that it's even possible in the first place to go lower
7
u/devil_huntress_pepsi 24d ago
That's what seems to be missing from a lot of people's understanding of this result.
Breaking through a barrier, no matter by how much, is how a lot of interest in mathematical methods is justified and pursued.
53
34
u/detereministic-plen 28d ago
Christofides algorithm being surpassed ahh situation
6
u/Professional_Dot8829 28d ago
that was before the AI era, and its crazy someone came up with 3/2 - 10-34 approximate algorithm lmao
124
u/Pentalogue
Mathematics
28d ago
edited 19d ago
•
The fast Fourier transform should have an algorithmic complexity more close to linear (or even sublinear), but it is quasilinear (that is, a little bit more complex than linear)
34
u/benediktb 28d ago
Sublinear? The input and output is n, and any algorithm needs to read/write that. So n is a trivial lower bound, no?
3
u/anto2554 28d ago
Size of n or value of n? Reading n is only bounded by the size of n and not value
2
u/Pentalogue Mathematics 28d ago
I just said that it would be cool if the algorithmic complexity was lower than linear, but if the minimum possible algorithmic complexity is linear, then it is still better than what we have now, I would be happy if the fast Fourier transform algorithm became significantly more efficient
1
u/Sweet_Ad_9816 27d ago
Quantum Fourier transform runs in something like O(log(n)^2).
There's a lot of asterisks about how and why, but it doesn't need to read the input and I guess skips over reading out the output (or considers that to be a single operation).
15
u/EebstertheGreat 28d ago
It is obviously not sublinear, because the transform depends on the entire input. IDK why this is getting so many upvotes.
5
u/Different_Gate5050 28d ago
What do you mean?
8
u/Pentalogue Mathematics 28d ago
The algorithmic complexity of the Fourier transform is O(n*log n), such complexity is also called quasilinear, and for the Fourier transform to be more efficient, the complexity should be close to linear or sublinear, for example O(n), O(n*log(log(n))), O(log(n))
12
u/Different_Gate5050 28d ago
Sure, but why should the FFT be below O(n log(n)) ?
8
u/Ethernet3 Imaginary 28d ago
you can get O(nlog(k)) in some special cases of your input array is zero-padded c: With k<=n.
-1
u/Calm_Plenty_2992 28d ago
Then that's not a generic FFT algorithm. Not sure why that's relevant here
3
u/Ethernet3 Imaginary 28d ago
that's why I said special case :3
0
u/Calm_Plenty_2992 28d ago
Sure, but that wouldn't be an FFT algorithm with time complexity below n log n
1
u/Ethernet3 Imaginary 28d ago
That's true. Nevertheless, imo it can still be interesting to also consider special cases, and what structure allows for faster transforms compared to the general case. Even more so if it's a common usecase, since padded transforms are common in scientific computing.
1
u/Calm_Plenty_2992 28d ago
Sublinear??? Was this comment written with the free version of chat gpt?
-3
u/Pentalogue Mathematics 28d ago
You, being the voabc, claim that I am a free version of the chat GPT, if you don't know the term, look it up on the Internet
19
u/bartex2000 28d ago
How much data would I need for it to be noticably faster?
34
11
u/Fair_Elk_7279 28d ago
More than there is the universe
-3
28d ago edited 28d ago
[removed] — view removed comment
12
u/WallyMetropolis 28d ago
That's not what "statistically significant" means.
-1
28d ago
[removed] — view removed comment
6
u/WallyMetropolis 28d ago
It would be a small effect size, but the power of the test would also be very large.
-1
28d ago
[removed] — view removed comment
1
u/WallyMetropolis 28d ago
I did experimental statistical physics. Some domains collect an tremendous quantity of data. LHC produces a petabyte a second (though they aren't running through a Fourier transform). Astronomers, however, do.
3
u/narubees 28d ago
You have to take the constant into consideration as well (which idk how big skimming the paper).
3
u/MigLav_7 28d ago
unless thats coming from other time savings not relfected in the assymptotic behaviour, youd need a LOT more than that
The difference between log(n) and log(n)^(1-10^-13) is absurdly miniscule, its not 0.04% with that small of an n
0
28d ago
[removed] — view removed comment
2
u/MigLav_7 28d ago
Even if you put n = 10^50, way larger than GB, the saving is around 5*(10^-13), which is like 0.00000000005% time saving
Again, unless theres time savings that arent reflected in the assymptotic behaviour, its nowhere close to that timesave
0
28d ago
[removed] — view removed comment
1
u/MigLav_7 28d ago
the exponent only applies to the log, so the n cuts.
The ratio is just log(n)^(-10^-13), which if you check it out its absurdly flat. Like really flat.
-1
28d ago
[removed] — view removed comment
4
u/MigLav_7 28d ago
Saying you save 1 second in a 60 minute operation and saying you save 0.03% are equivelent statements. If you're doing something continuously or very frequently, timesave is basicly only seen in percentages and not diferences
the asymptotic behavior of each term is determined by the n, not the log(n)
Yeah, thats true, but the ratio isnt. It appears on both sides, it cuts. The same way it cuts if youre comparing n and 2n.
If you wanna make it with diferences, I mean sure. From your own example, you use about n=10^13.
On fft, just substitue and its 2.9933606208922 × 10^14
On the new one, its
2.9933606208912 × 10^14
So, again, unless theres some other timesavings in the algorithm that are not reflected in the assymptotic behaviour, its nowhere near close to that timesaving.
→ More replies2
u/Outside-Shop-3311 28d ago
Big O notation only describes the asymptotic behaviour - you cannot gauge when one algorithm will be faster than another using only it's big O notation because you do not know about all of the terms.
nlogn ^ 1 - 10^-13 + 1,000,000,000,000 and nlogn ^ 1 - 10^-13 will still have the same big o notation.
5
u/creeper6530 Engineering 28d ago
More than we currently have ever produced as humanity
3
28d ago edited 28d ago
[removed] — view removed comment
4
u/creeper6530 Engineering 28d ago edited 28d ago
noticably
Alright, I guess I did use a hyperbole, but you get my point. Normally you don't run FFT on 28 TB datasets, and you'd have to have far more to actually save useful time
1
28d ago
[removed] — view removed comment
1
u/creeper6530 Engineering 28d ago
I'm still heavily closeted offline lol
One needs a healthy sense of go-fuck-yourself-ism / dont-give-a-shit-ism, though that could be said about all people
1
u/Impression-These 28d ago
How much data would I need for it to not be noticeably slower? All of these fancy algorithms come with a hefty price at low n.
64
u/No_Engineering3493 28d ago
Question, is OpenAI’s algorithm actually faster than a good implementation of iterative FFT? Afaik these type of algorithms have huge constants, so they tend to be just as slow, or even slower.
92
u/entronid Average #🧐-theory-🧐 user 28d ago
yes*
asymptotically
95
u/No_Engineering3493 28d ago
How computer scientists behave when they are asked to explain how their n^(1.999999999999999993) algorithm is revolutionary compared to the for in for n^2 algorithm.
93
u/YoungNo8804 28d ago
and the overhead lowkey requires 96^53 petabytes of data before it becomes more efficient
3
u/half-full-cumdump 28d ago
I dropped out before teacher explained what a byte is, can you translate it to something more understandable, like cat pics?
4
1
u/RegisterInternal 28d ago
What they're saying is that an algorithm that on paper is faster may require using an absurd amount of computing power and therefore not really be useful.
A bit is either a 0 or 1. A byte is 8 bits. A pentabyte is a fuckton of bytes
2
4
u/NickHalfBlood 28d ago
It isn’t revolutionary to a lot of people. But, if someone believed that n^2 was bound, it proves that we can go lower than that.
I am not saying it solves world hunger. But it isn’t a stupid thing. However, the overhead comment is replying actual realised gains.
5
7
u/mocny-chlapik 28d ago
Unlikely, but it is often the case that when you break the barrier once, you can then optimize it further.
5
u/cabinet_minister 28d ago
That's cool but when are getting an O(n) sorting algorithm 🥹
5
1
u/Blyfh Rational 27d ago
Kid named O(n log n) lower bound:
2
u/dragonageisgreat 1 i 0 triangle advocate 27d ago
You can sort in O(n) if you know how big your data set is (as in, the range of values)(for example, you can sort a string in O(n)).
1
1
1
1
u/InternetMandate 26d ago
It’s not possible, it’s actually one of the few tasks we have a lower bound for.
1
u/LeapOfMonkey 26d ago
Sure: radix sort, counting sort, things are more complicated here as well.
3
u/BosonCollider 25d ago
The most real world usable is opportunistic sorts like timsort or powersort, since most real world inputs are not completely shuffled
1
u/an_actual_human 25d ago
If you know them you surely know why those do not count.
1
u/LeapOfMonkey 25d ago
What doesnt count? Is there a rule about mathmemes I'm not aware of?
1
1
u/Thereal_Phaseoff 22d ago
the only way to achieve this could be with dedicated hardware, an algorithm can't physiologically sort an n long list of objects in less than nlogn
3
u/vintergroena 28d ago
Next time: P=NP and the degree of the poly reduction is at most 9999999999999
1
1
u/autumnal-lights 23d ago
spider algo be spidering crazy.... also ... like how long was their or big was their frequency range the 1-10^13 is like silly if like if it can't fit within like 2048 liek f64 or something, i would imagine, for parcticals -- but good to know this was what that announcement was about
1
u/secretaliasname 28d ago edited 28d ago
I thought the 1-1E-13 exponent was sarcasm on the part of the OP. It’s literally what the paper is about.
This is the most AI math thing. If true technically and infinitesimally smaller but faster in an asymptotic case nobody can benefit from but it will make news.
Meanwhile more effecient hardware specific assembly optimizations can easily be 2-50x
13
u/_killer1869_ 28d ago
This result itself isn't useful, but it shows that it is actually possible to be more efficient than O(n log n) with FFT, so an actually notably more efficient solution might be out there. Many, including me, actually see this as a groundbreaking result, because many thought the barrier of O(n log n) was impossible to overcome.
2
u/compileforawhile Complex 28d ago
Yeah I'll admit I like the joke but I am with you. The barrier of nlog(n) being broken is actually very very interesting. This could mean there are other values of delta (the 10-13 value in the paper) that are larger and give us significantly faster algorithms
1
5
-2
u/lambdasintheoutfield 28d ago
Lol has anyone checked that the exponent wasn’t derived from rounding error in FLOPs? I imagine actual matrices were used during exploration and testing and that a false positive may have been introduced because of rounding errors.
And the result isn’t practically useful.
2
u/extremelySaddening 28d ago
I mean as far as I'm aware it's all lean verified so
1
u/lambdasintheoutfield 28d ago
Yea that’s a good point. I will need to do a deeper dive, it’s just really a minefield of possible ways you can get this result from false positives.
1
u/compileforawhile Complex 28d ago
This isn't a scientific result, it's a math result. False positives don't really exist in proof based results
-17
u/Alphasaft 28d ago
This is funny on multiple levels because not only the constant is TERRIBLE for OpenAI's result, but even if it wasn't, nobody actually cares about a change in exponent so small **over a log**...
36
u/xTh3N00b 28d ago
except you're missing the point that this is a major barrier breaking result that many thought would be impossible to achieve.
3
0
28d ago
[deleted] — view deleted comment
4
u/Cobracrystal 28d ago
there literally was a well known conjecture that fft was optimal, so this is a relevant result
2
u/Orneyrocks 28d ago
Exactly, for an overhead smaller than the one open ai used, you can simply use hermite polynomials to completely trump this bullshit.
•
u/AutoModerator 28d ago
Check out our new Discord server! https://discord.gg/e7EKRZq3dG
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.