# original code for the FFT Tukey-Cooley schedul:
# https://www.nayuki.io/res/free-small-fft-in-multiple-languages/fft.py
"""
- # Radix-2 decimation-in-time FFT
- size = 2
- while size <= n:
- halfsize = size // 2
- tablestep = n // size
- for i in range(0, n, size):
- k = 0
- for j in range(i, i + halfsize):
+ # Radix-2 decimation-in-time FFT (real, not complex)
+ size = 2
+ while size <= n:
+ halfsize = size // 2
+ tablestep = n // size
+ for i in range(0, n, size):
+ k = 0
+ for j in range(i, i + halfsize):
jh = j+halfsize
jl = j
- temp1 = vec[jh] * exptable[k]
- temp2 = vec[jl]
- vec[jh] = temp2 - temp1
- vec[jl] = temp2 + temp1
- k += tablestep
- size *= 2
+ temp1 = vec[jh] * exptable[k]
+ temp2 = vec[jl]
+ vec[jh] = temp2 - temp1
+ vec[jl] = temp2 + temp1
+ k += tablestep
+ size *= 2
"""
# python "yield" can be iterated. use this to make it clear how
skip = 0
while True:
for size in x_r: # loop over 3rd order dimension (size)
+ x_end = size == x_r[-1]
# y_r schedule depends on size
halfsize = size // 2
tablestep = n // size
# invert if requested
if SVSHAPE.invxyz[1]: y_r.reverse()
for i in y_r: # loop over 2nd order dimension
+ y_end = i == y_r[-1]
k_r = []
j_r = []
k = 0
if SVSHAPE.invxyz[2]: k_r.reverse()
if SVSHAPE.invxyz[2]: j_r.reverse()
for j, k in zip(j_r, k_r): # loop over 1st order dimension
- # skip the first entries up to offset
- if skip < SVSHAPE.offset:
- skip += 1
- continue
+ z_end = j == j_r[-1]
# now depending on MODE return the index
if SVSHAPE.skip == 0b00:
result = j # for vec[j]
elif SVSHAPE.skip == 0b10:
result = k # for exptable[k]
- yield result
+ loopends = (z_end |
+ ((y_end and z_end)<<1) |
+ ((y_end and x_end and z_end)<<2))
+
+ yield result + SVSHAPE.offset, loopends
def demo():
# set the dimension sizes here
prefix = "i %d\t" % i
k = 0
for j in range(i, i + halfsize):
- jl, jh, ks = schedule[idx]
+ (jl, je), (jh, he), (ks, ke) = schedule[idx]
print (" %-3d\t%s j=%-2d jh=%-2d k=%-2d -> "
- "j[jl=%-2d] j[jh=%-2d] exptable[k=%d]" % \
+ "j[jl=%-2d] j[jh=%-2d] ex[k=%d]" % \
(idx, prefix, j, j+halfsize, k,
- jl, jh, ks))
+ jl, jh, ks,
+ ),
+ "end", bin(je)[2:], bin(je)[2:], bin(ke)[2:])
k += tablestep
idx += 1
size *= 2