4 ms·

Yes, it offends my aesthetic sense when the asymptotically fastest algorithms for simple problems are complex monsters. It didn't used to be like that: early fa

by tlb 5y ago

Yes, it offends my aesthetic sense when the asymptotically fastest algorithms for simple problems are complex monsters. It didn't used to be like that: early fast algorithms (like heapsort and FFT) are only very slightly more complex than the naive ones.

anon_tor_12345 5y ago
lol cooley-tukey FFT is anything but simple when you actually have to implement it.
- Greek0 5y ago
  Cooley-Tukey Fast Fourier Transform can be complex to implement, if you want to optimize it. A basic version is surprisingly simple, I implemented it for fun in Python a couple of years ago: def fft(x): N = len(x) if N == 1: return x assert N % 2 == 0 E = fft(x[::2]) O = fft(x[1::2]) X = [None] * N for k in range(N // 2): tf = np.exp(-2j * np.pi * k / N) X[k] = E[k] + tf * O[k] X[k + N//2] = E[k] - tf * O[k] return X The Wikipedia article describing it is surprisingly decent: https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algor...
klyrs 5y ago
Computer science was a new branch of mathematics 100 years ago. Folks discovered the easy, low-lying algorithms. I don't know about you, but I've rediscovered quite old results that are named so-and-so's algorithm or what's-their-face's theorem; because they were the obviously efficient ways of solving those problems. Supposing P=NP, one would expect the polytime algorithm to be brain-meltingly complex. Same goes for, say, a n^2log(n) matrix multiplication algorithm. Simplification is a really good strategy for optimizing algorithms. But sometimes, doing less work requires doing a bit of thinking upfront, or carefully cleaning up behind yourself (but not cleaning too eagerly).
- asimpletune 5y ago
  I really don’t understand why this is being downvoted. Beyond trivial algorithms, as mentioned in the parent, fast algorithms come from deep knowledge of the problem, leading to highly tailored data structures, and thus very complicated algorithms. I’m not sure why this is controversial? Also citing aesthetic sensibility is fine, but it’s also fine to update or recalibrate one’s aesthetic intuition.

by tlb 5y ago

anon_tor_12345 5y ago

lol cooley-tukey FFT is anything but simple when you actually have to implement it.

Greek0 5y ago
Cooley-Tukey Fast Fourier Transform can be complex to implement, if you want to optimize it. A basic version is surprisingly simple, I implemented it for fun in Python a couple of years ago: def fft(x): N = len(x) if N == 1: return x assert N % 2 == 0 E = fft(x[::2]) O = fft(x[1::2]) X = [None] * N for k in range(N // 2): tf = np.exp(-2j * np.pi * k / N) X[k] = E[k] + tf * O[k] X[k + N//2] = E[k] - tf * O[k] return X The Wikipedia article describing it is surprisingly decent: https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algor...

klyrs 5y ago

Computer science was a new branch of mathematics 100 years ago. Folks discovered the easy, low-lying algorithms. I don't know about you, but I've rediscovered quite old results that are named so-and-so's algorithm or what's-their-face's theorem; because they were the obviously efficient ways of solving those problems. Supposing P=NP, one would expect the polytime algorithm to be brain-meltingly complex. Same goes for, say, a n^2log(n) matrix multiplication algorithm. Simplification is a really good strategy for optimizing algorithms. But sometimes, doing less work requires doing a bit of thinking upfront, or carefully cleaning up behind yourself (but not cleaning too eagerly).

asimpletune 5y ago
I really don’t understand why this is being downvoted. Beyond trivial algorithms, as mentioned in the parent, fast algorithms come from deep knowledge of the problem, leading to highly tailored data structures, and thus very complicated algorithms. I’m not sure why this is controversial? Also citing aesthetic sensibility is fine, but it’s also fine to update or recalibrate one’s aesthetic intuition.