# totally cool *in-place* DCT algorithm
def inverse_transform_iter(vec):
+ # in-place, but actually have to protect the input list!
+ vec = deepcopy(vec)
+
# Initialization
n = len(vec)
print ()
# this table could be cached and used multiple times rather than
# computed every time.
ctable = []
- size = n
- while size >= 2:
+ size = 2
+ while size <= n:
halfsize = size // 2
for i in range(n//size):
for ci in range(halfsize):
ctable.append((math.cos((ci + 0.5) * math.pi / size) * 2.0))
- size //= 2
+ size *= 2
# first divide element 0 by 2
vec[0] /= 2.0
print("transform2-inv pre-itersum", vec)
- #vec = halfrev2(vec, True)
+ vec = [vec[ri[i]] for i in range(n)]
+ vec = halfrev2(vec, True)
#print("transform2-inv post-itersum-reorder", vec)
# first the outer butterfly (iterative sum thing)
jr.reverse()
print ("itersum jr", i+halfsize, i+size, jr)
for jh in jr:
- #x = vec[ji[jh]]
- #y = vec[ji[jh+size]]
- #vec[ji[jh+size]] = x + y
- x = vec[jh]
- y = vec[jh+size]
- vec[jh+size] = x + y
+ x = vec[ji[ri[jh]]]
+ y = vec[ji[ri[jh+size]]]
+ vec[ji[ri[jh+size]]] = x + y
print (" itersum", size, i, jh, jh+size,
x, y, "jh+sz", vec[ji[jh+size]])
size *= 2
print("transform2-inv post-itersum", vec)
- # and pretend we LDed data in half-swapped *and* bit-reversed order as well
- # TODO: merge these two
- vec = [vec[ri[i]] for i in range(n)]
- vec = halfrev2(vec, True)
- ri = list(range(n))
-
- print("transform2-inv post-reorder", vec)
-
# start the inner butterfly (coefficients)
size = 2
k = 0
jr.reverse()
print (" xform jr", j, jr)
for ci, (jl, jh) in enumerate(zip(j, jr)):
- #t1, t2 = vec[ri[ji[jl]]], vec[ri[ji[jh]]]
t1, t2 = vec[ji[jl]], vec[ji[jl+halfsize]]
- coeff = (math.cos((ci + 0.5) * math.pi / size) * 2.0)
- #coeff = ctable[k]
+ #coeff = (math.cos((ci + 0.5) * math.pi / size) * 2.0)
+ coeff = ctable[k]
k += 1
# normally DCT would use jl+halfsize not jh, here.
# to be able to work in-place, the idea is to perform a
# swap afterwards.
- #vec[ri[ji[jl]]] = t1 + t2/coeff
- #vec[ri[ji[jh]]] = t1 - t2/coeff
vec[ji[jl]] = t1 + t2/coeff
vec[ji[jl+halfsize]] = t1 - t2/coeff
print ("coeff", size, i, "ci", ci,