<commit_before>#!/usr/local/bin/python2.3
import math
pi=math.pi
e=math.e
j=complex(0,1)

def fft(f):
    n=len(f)
    if n==1:
        return f

    for p in 2,3,5:
        if n%p==0:
            break
    else:
        raise Exception('%s not factorable ' % n)

    #print 'n=%d,p=%d' % (n,p)
    #print f,' << fin'
    m = n/p
    Fout=[]
    for q in range(p): # 0,1
        fp = f[q::p]
        #print fp,'<< fp'
        Fp = fft( fp )
        Fout.extend( Fp )

    for u in range(m):
        scratch = Fout[u::m] # u to end in strides of m
        #print scratch
        for q1 in range(p):
            k = q1*m + u  # indices to Fout above that became scratch
            Fout[ k ] = scratch[0] # cuz e**0==1 in loop below
            for q in range(1,p):
                t = e ** ( j*2*pi*k*q/n )
                Fout[ k ] += scratch[q] * t

    return Fout

def real_fft( f ):
    broken

    N = len(f) / 2

    res = f[::2]
    ims = f[1::2]
    fp = [ complex(r,i) for r,i in zip(res,ims) ]
    Fp = fft( fp )

    Fpr = [ c.real for c in Fp ]
    Fpi = [ c.imag for c in Fp ]

    F1 = [complex(0,0)]*(N+1)
    F2 = [complex(0,0)]*(N+1)

    F1[0] = complex( Fpr[0] , 0 )
    F2[0] = complex( Fpi[0] , 0 )
    #F1[N] = complex( Fpr[N] , 0 )
    #F2[N] = complex( Fpi[N] , 0 )


    for k in range(1,N):
        F1[k] = complex( (Fpr[k]+Fpr[N-k])/2 , j*(Fpi[k]-Fpi[N-k])/2 )
        F2[k] = complex( (Fpi[k]+Fpi[N-k])/2 , j*(Fpr[k]-Fpr[N-k])/2 )

    F = [ complex(0,0) ] * ( N + 1 )
    for k in range(N+1):
        F[k] = F1[k] +  e ** ( j*pi*k/N ) * F2[k]
    return F        

def test(f=range(1024),ntimes=10):
    import time
    t0 = time.time()
    for i in range(ntimes):
        fft(f)
    t1 = time.time()
    print '%ss'% (t1-t0)

<commit_msg>real_fft works<commit_after>#!/usr/local/bin/python2.3
import math
pi=math.pi
e=math.e
j=complex(0,1)

def fft(f):
    n=len(f)
    if n==1:
        return f

    for p in 2,3,5:
        if n%p==0:
            break
    else:
        raise Exception('%s not factorable ' % n)

    #print 'n=%d,p=%d' % (n,p)
    #print f,' << fin'
    m = n/p
    Fout=[]
    for q in range(p): # 0,1
        fp = f[q::p]
        #print fp,'<< fp'
        Fp = fft( fp )
        Fout.extend( Fp )

    for u in range(m):
        scratch = Fout[u::m] # u to end in strides of m
        #print scratch
        for q1 in range(p):
            k = q1*m + u  # indices to Fout above that became scratch
            Fout[ k ] = scratch[0] # cuz e**0==1 in loop below
            for q in range(1,p):
                t = e ** ( j*2*pi*k*q/n )
                Fout[ k ] += scratch[q] * t

    return Fout

def real_fft( f ):
    N = len(f) / 2

    res = f[::2]
    ims = f[1::2]

    fp = [ complex(r,i) for r,i in zip(res,ims) ]

    Fp = fft( fp )

    F = []
    for k in range(N):
        s2 = ( Fp[k] + Fp[-k] ) * .5
        d2 = ( Fp[k] - Fp[-k] ).conjugate() * .5
        F1k = complex( s2.real , d2.imag )
        F2k = complex( s2.imag , d2.real )
        F.append( F1k +  e ** ( -j*pi*k/N ) * F2k )

    F.append( complex( Fp[0].real - Fp[0].imag , 0 ) ) 
    return F

def test(f=range(1024),ntimes=10):
    import time
    t0 = time.time()
    for i in range(ntimes):
        fft(f)
    t1 = time.time()
    print '%ss'% (t1-t0)


{'fraction_non_alphanumeric': 0.182288496652465, 'fraction_numerical': 0.03408399269628728, 'mean_word_length': 1.646537842190016, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '990255', 'n_tokens_mistral': 1482, 'n_tokens_neox': 1426, 'n_words': 365}