I was listening to smj do strange and excellent glitching of
the clash on anon radio as my energy to do inane
email-sending tasks waned. It got me in mind of how I could
form some cyber-appendage capable of grasping the stream.
I think actually-doing-it probably could look kind of like
1. Dump my stream into a wave file
2. Streamingly convert wave file to mp3 file
3. Stream that to stream
(If you know better than the seat of my pants, do say. Maybe
there's a tut.)
So actually-doing-what. I've sorely neglected my sometime
life centre of streaming. Laplace (I like to rhyme this with
hapless) transforms create discrete signals from continuous
signals and then inverse the inverse. A popular one is the
Fourier transform, converting between frequency dirac delta
spikes and sinc sounds (etc). The dirac delta function
is 0 when it's argument is not 0, and has an integral of 1.
The discrete Fourier transform takes surprisingly few
operations/has a low complexity to do called the Fast
Fourier Transform, originally known to Euler. Larger Fast
Fourier Transforms are built up recursively, related to
possible factorisations of the input's size. In practice,
terminating small fast fourier transforms are below size 53,
because above that numbers other than 0 or 1 show up in part
of a split-nesting approach, and numbers other than 0 or 1
suck.
Anyway, I want to stream these. My thinking is to stream
through butterflies of little discrete
decimation-in-frequency ffts [whence to anon radio,
eventually]. The key bit of streaming here is that after
some lead time, output has to start leaving exactly as fast
as new inputs arrive.
It is also fast to compute prime sized discrete Fourier
transforms; you can use a fast fourier transform to do the
maths of a prime sized discrete fourier transform, so the
prime one can be fast as well. It's not known how many
operations it takes in the best case in general.
Let's do the simple definition of plus and minus-i discrete
fourier transforms.
(defun naieve-i (v)
(make-array (length v) :initial-contents
(loop for k below (length v) collecting
(loop for n below (length v) summing
(* (aref v n)
(exp (/ (* #c(0 -1) 2 pi k n)
(length v))))))))
and its undoing (or vice versa), the +i
(defun naieve-i (v)
(make-array (length v) :initial-contents
(loop for k below (length v) collecting
(loop for n below (length v) summing
(* (aref v n)
(exp (/ (* #c(0 +1) 2 pi k n)
(length v))))))))
For a given smallish prime number, we can calculate the
Winograd fft, whose attractive properties I am going to fail
to use here.
(defun win-5 (v) \"Today brought to you be the number 5 and
letter nu\"
(let* ((t0 (+ (aref v 1) (aref v 4)))
(t1 (+ (aref v 2) (aref v 3)))
(a4 (- (aref v 3) (aref v 2)))
(a5 (- (aref v 1) (aref v 4)))
(a1 (+ t0 t1))
(a2 (- t0 t1))
(a3 (+ a4 a5))
(a0 (+ (aref v 0) a1))
(th (/ (* 2 pi) 5))
(b0 (* 1 a0))
(b1 (* a1 (1- (* 1/2 (+ (cos th) (cos (* 2 th)))))))
(b2 (* a2 1/2 (- (cos th) (cos (* 2 th)))))
(b3 (* a3 (sin th)))
(b4 (* a4 (+ (sin th) (sin (* 2 th)))))
(b5 (* a5 (- (sin (* 2 th)) (sin th))))
(v0 b0)
(*t0 (+ b0 b1))
(*t1 (- b3 b4))
(*t2 (+ b3 b5))
(*t3 (+ *t0 b2))
(*t4 (- *t0 b2))
(v1 (- *t3 (* #c(0 1) *t1)))
(v2 (- *t4 (* #c(0 1) *t1)))
(v3 (+ *t3 (* #c(0 1) *t1)))
(v4 (+ *t4 (* #c(0 1) *t1))))
(values (make-array (length v) :initial-contents
(list v0 v1 v2 v3 v4)))))
Now hooooopefully
(win-5 #(1 1 0 1 2))
and
(naieve-i #(1 1 0 1 2))
and some print function* give us
5.00 + 0.00j
1.12 + 1.54j
-1.12 + -0.36j
-1.12 + 0.36j
1.12 + -1.54j
and following naieve+i ..
5.00 + 0.00j
5.00 + 0.00j
0.00 + 0.00j
5.00 + 0.00j
10.00 + 0.00j
Since every two transforms the size scales by the length of
the transform. Believe me the Fourier transform version of
this will be good to listen to.