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))

一応これでフーリエ変換っぽい計算はできてるはず。

いいなと思ったら応援しよう!