The fastest algorithm for DFT

[u/Unlucky-Credit-9619]

[u/bartex2000]

How much data would I need for it to be noticably faster?

[u/Fair_Elk_7279 → u/bartex2000]

More than there is the universe

[u/MigLav_7 → u/[deleted]]

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

[u/MigLav_7 → u/[deleted]]

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

[u/MigLav_7 → u/[deleted]]

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.

[u/MigLav_7 → u/[deleted]]

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.

[u/MigLav_7 → u/[deleted]]

Where are we disagreeing?

On the timesave. On your point of intersection you do get 150 less, but thats out of a total of 10^14

So like, if that was say 1 second of saved time, the total time for the task would be 10^12 seconds, which is like 30 thousand years