2以外の底を使った離散フーリエ変換の素案
ベーシックな高速フーリエ変換と並べて、速度の検証予定
def vect(ls,p,r=1,reverse=False):
vecls=np.array([[(i*j)%p for i in range(p)]for j in range(p)])
l=1
def roll(ls,p):
z=lambda y,x:np.append(y[x::],y[:x:])
ans=np.zeros((len(p)))
if reverse==False:
for i in range(len(p)):
ans+=z(ls[i],p[i])
#print('lm',z(ls[i],p[i]))
else:
for i in range(len(p)):
ans+=z(ls[i],p-p[i])
return ans
def vec(lls):#p*p
#print(lls,type(lls))
#print(xs)
#lls=np.array(lls).reshape((1,-1))
lls=np.array(lls)
#lls=np.append(lls,np.zeros((p-1,p)),axis=0).T
llls=np.zeros((p,p))
for i in range(p):
#for j in range(p):
llls[i]=roll(lls,vecls[i])
llls[i]-=min(llls[i])
llls[i]*=r**(p-i-1)
print(llls)
return llls
ls=np.array(ls)
while p**l<len(ls):
l+=1
if len(ls)!=p**l:
ls=np.append(ls,[0]*(p**l-len(ls)))
ls=ls.reshape((-1,p,p))
#print(ls)
for j in range(len(ls)):
ls[j]=vec(ls[j])
#ls=np.apply_along_axis(lambda x:vec(x),1,ls)
#print(ls)
ls=np.concatenate(ls,0)
#print(ls)
ls=ls.reshape((-1))
return ls
def fastdft(ls,p,r=1,reverse=False):
ls=np.array(ls)
if len(ls)%(p-1)!=0:
ls=np.append(ls,[0]*(len(ls)%(p-1)))
ls=ls.reshape((-1,p-1))
ls=np.append(ls,np.zeros((len(ls),1)),axis=1)
l=1
while p**l<len(ls):
l+=1
ls=np.append(ls,np.zeros((p**l-len(ls),p)))
for i in range(l):
ls=vect(ls.reshape(-1),p,r)
ls=ls.reshape((-1,p))
for i in range(len(ls)):
ls[i]-=ls[i][p-1]
return ls[:,:p-1].reshape(-1)
def atosho(ls,p):
ls=ls.reshape((-1,p-1))
return np.append(ls[0],ls[:0:-1])
a=[1,0,0,0,0,2,0,0,0,0,3,0,0,0,0,4,0,0,0,0,5,0,0,0,0]
a=[1,0,1,2,0,1,3,0,1,1,0,1,2,0,1,3,0,1]
print('fast',fastdft(a,5))
print('fast',atosho(fastdft(fastdft(a,5),5),5))
一応これでフーリエ変換っぽい計算はできてるはず。