Viewing a single comment thread. View all comments

nomadiclizard t1_irh1khu wrote

I wonder if there's a faster fourier transform algorithm out there o.o

30

uneaknayum t1_irh65rm wrote

Of the subspace of Algos that exist, we have only discovered a handful.

It is statistically likely that there will be, within that same space, an algorithm exists to do most things faster.

Addition might be pretty solved by this point, but no one has said solving a 100k digit addition problem by hand would be efficient.

Faster FT means a faster QTF. Gangbusters!

17

carlthome t1_irhwo6z wrote

FFT is already O(n*log(n)) though so what could be improved? Linear time?

4

_Ruffy_ t1_iri6u60 wrote

I'd say the multiplicative factors left out in the O-notation actually matter in practice..

20

jpopham91 t1_irmwio4 wrote

Isn't what people thought about matrix multiplication before Strassen's algorithm too?

1

-xylon t1_irjih2c wrote

Relax this is just better compilation for algorithms that exist, not new algos.

0