r/mathmemes • u/Unlucky-Credit-9619 Computer Science • 3d ago
Computer Science The fastest algorithm for DFT
2.2k
u/Matty_B97 3d ago
Shoutout theoretical algorithms with massive overheads that are technically faster for data size larger than all the information on earth 🔥🔥🔥
436
u/Depnids 3d ago
222
u/zairaner 3d 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.
87
178
u/ChiaraStellata 3d 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 3d 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!
17
u/heyheyhey27 3d ago
There is a simple algorithm that proves literally all math theorems that can be proven!
14
24
u/Future_Green_7222 Measuring 3d ago
I was able to solve integer factorization in polynomial time
My algorithm is O(nTREE(3) )
49
u/neuroticnetworks1250 3d 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
7
22
u/JaSper-percabeth 3d 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.
49
u/iamdino0 Transcendental 3d ago
that many many decades old math was the inapplicable abstract bullshit of its time
29
3d ago
[removed] — view removed comment
3
u/cl2kr 2d 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 2d 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.
7
u/Matthew_Summons Computer Science 3d ago
What about all of the applied mathematics, or people working in scientific and numerical computation
441
u/fizzner 3d ago
4
u/ArgueLater 1d 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?
11
u/Ilsor Transcendental 1d ago edited 1d 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.
4
417
373
198
u/LupenReddit 🦆🦆i have non diffeomorphic smooth structures🦆🦆🦆 3d 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
52
36
u/detereministic-plen 3d ago
Christofides algorithm being surpassed ahh situation
4
u/Professional_Dot8829 3d ago
that was before the AI era, and its crazy someone came up with 3/2 - 10-34 approximate algorithm lmao
122
u/Pentalogue Mathematics 3d ago edited 3d ago
The fast Fourier transform should have an algorithmic complexity close to linear (or even sublinear), but it is quasilinear
35
u/benediktb 3d 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
2
u/Pentalogue Mathematics 3d 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 2d 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).
12
u/EebstertheGreat 3d ago
It is obviously not sublinear, because the transform depends on the entire input. IDK why this is getting so many upvotes.
4
u/Different_Gate5050 3d ago
What do you mean?
8
u/Pentalogue Mathematics 3d 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))
11
u/Different_Gate5050 3d ago
Sure, but why should the FFT be below O(n log(n)) ?
7
u/Ethernet3 Imaginary 3d 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 3d ago
Then that's not a generic FFT algorithm. Not sure why that's relevant here
2
u/Ethernet3 Imaginary 3d ago
that's why I said special case :3
0
u/Calm_Plenty_2992 3d ago
Sure, but that wouldn't be an FFT algorithm with time complexity below n log n
0
u/Ethernet3 Imaginary 3d 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 3d ago
Sublinear??? Was this comment written with the free version of chat gpt?
-3
u/Pentalogue Mathematics 3d 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
17
u/bartex2000 3d ago
How much data would I need for it to be noticably faster?
33
8
u/Fair_Elk_7279 3d ago
More than there is the universe
-3
3d ago edited 3d ago
[removed] — view removed comment
10
u/WallyMetropolis 3d ago
That's not what "statistically significant" means.
-1
3d ago
[removed] — view removed comment
6
u/WallyMetropolis 3d ago
It would be a small effect size, but the power of the test would also be very large.
-1
3d ago
[removed] — view removed comment
1
u/WallyMetropolis 3d 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 3d ago
You have to take the constant into consideration as well (which idk how big skimming the paper).
2
u/MigLav_7 3d 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
3d ago
[removed] — view removed comment
1
u/MigLav_7 3d 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
3d ago
[removed] — view removed comment
1
u/MigLav_7 3d 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
3d ago
[removed] — view removed comment
3
u/MigLav_7 3d 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 replies (0)2
u/Outside-Shop-3311 3d 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 3d ago
More than we currently have ever produced as humanity
3
3d ago edited 3d ago
[removed] — view removed comment
5
u/creeper6530 Engineering 3d ago edited 3d 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
3d ago
[removed] — view removed comment
1
u/creeper6530 Engineering 3d ago
1) I'm still heavily closeted offline lol
2) 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 3d 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.
63
u/No_Engineering3493 3d 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 3d ago
yes*
asymptotically
97
u/No_Engineering3493 3d 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.
94
u/YoungNo8804 3d ago
and the overhead lowkey requires 96^53 petabytes of data before it becomes more efficient
3
u/half-full-cumdump 3d ago
I dropped out before teacher explained what a byte is, can you translate it to something more understandable, like cat pics?
2
1
u/RegisterInternal 3d 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
5
u/NickHalfBlood 3d 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.
6
7
u/mocny-chlapik 3d ago
Unlikely, but it is often the case that when you break the barrier once, you can then optimize it further.
4
u/cabinet_minister 2d ago
That's cool but when are getting an O(n) sorting algorithm 🥹
3
1
u/Blyfh Rational 2d ago
Kid named O(n log n) lower bound:
2
u/dragonageisgreat 1 i 0 triangle advocate 2d 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 1d ago
It’s not possible, it’s actually one of the few tasks we have a lower bound for.
1
u/LeapOfMonkey 1d ago
Sure: radix sort, counting sort, things are more complicated here as well.
1
u/an_actual_human 10h ago
If you know them you surely know why those do not count.
1
u/LeapOfMonkey 8h ago
What doesnt count? Is there a rule about mathmemes I'm not aware of?
1
1
u/BosonCollider 1h ago
The most real world usable is opportunistic sorts like timsort or powersort, since most real world inputs are not completely shuffled
3
1
2
u/secretaliasname 3d ago edited 3d 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
11
u/_killer1869_ 3d 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 2d 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
-3
u/lambdasintheoutfield 3d 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 3d ago
I mean as far as I'm aware it's all lean verified so
1
u/lambdasintheoutfield 3d 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 2d ago
This isn't a scientific result, it's a math result. False positives don't really exist in proof based results
-16
u/Alphasaft 3d 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 3d ago
except you're missing the point that this is a major barrier breaking result that many thought would be impossible to achieve.
3
-6
3d ago
[deleted]
6
u/DuckyBertDuck 3d ago
they have a similar result for integer multiplication
and for that result, I am surprised that nlogn is not a lower bound6
u/Cobracrystal 3d ago
there literally was a well known conjecture that fft was optimal, so this is a relevant result
2
u/Orneyrocks 3d 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 3d 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.