@kentpitman @rwxrwxrwx
could I get you two's (et al.'s) opinions on my conference paper idea for #ELS2025:
https://codeberg.org/tfw/cl-series-fft#headline-4
I eventually scrapped together a 3 element Winograd #FFT that was compatible with Waters' Series 1400 line expansion. This year's theme is "going beyond macros" and Series is kinda beyond other macros.
I did it by hand to figure things out, but later I could cover/follow Sidney Burrus' PFA program-generation book, but for #lisp, with Series (instead of Fortran).
Burrus style FFTs with Waters' Series macro package…
Codeberg.org@kentpitman @rwxrwxrwx
otherwise, people often use bordeaux-fft, which are length two (trivial) composite ffts, or else go to C's (Burrus') fftw. I think series-optimised lisp native fft generation sounds exciting. With Series' laziness, it could even add a Goertzel's-like dimension (only evaluating targetted bins through laziness).
@screwtape @kentpitman @rwxrwxrwx
Winograd had a separate FFT per prime length, composing for composite lengths. So we can expect you to also have one per prime p, right? How many primes could there be, after all.
@dougmerritt
I ran out of characters to tag you but I was waiting for this <3
As you know, Winograd's algorithm is only/especially interesting for small primes. To my knowledge one would never go past fifty, and The Usual Winograd's algorithm generations don't go above the 20s, if I recall correctly (you probably recall better).
Anyway, there turn out to be lots of numbers that are multiples of three as well as two, in the first place. Infinitely many ;p
@screwtape @kentpitman @rwxrwxrwx
> I ran out of characters to tag you but I was waiting for this <3
It's *almost* like you're saying I'm some kind of smart ass.
> only/especially interesting for small primes
That's quitter talk!
@screwtape @kentpitman @rwxrwxrwx
More seriously, I always found it intensely annoying that fftw claimed copyright/license on generated code.
Less seriously again:
"name idea is A Worse Is Better Way Of Computing A Fourier Transform"
Not "Better is Worse"?
> PROGN...PROGN...PROGN...SETQ...SETQ...SETQ...GO #....GO #...GO #...
My mistake, worse it is. ;)
Anyway leveraging name recognition on "Worse is Better" really is a good naming idea.
@dougmerritt
Hah, yeah, but I think that the series-expanded code will let us do specific-bins calculation in a special way enabled by lisp's cl-series.
Also, I hand-hacked (using emacs) this machine-generated in-place code into successfully-being-admitted-by-cl-series. So I am not arguing my code was good at all here, just that it worked at all and indicates it's possible.
Burrus-style generated wfta I used as a reference: https://web.archive.org/web/20081220142747/http://cnx.org/content/m17626/latest/
@kentpitman @rwxrwxrwx