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

def T(n,k):
    return e ** -2*j*pi*k/n

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

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

    Fm=[]
    for q in range(p): # 0,1
        fp = f[q::p]
        Fp = fft( fp )
        Fm.extend( Fp )

    Fout=[0]*n
    for k in range(n):
        val = 0
        for q in range(p):
            t = e ** ( -j*2*pi*k*q/n )
            val += Fm[ q*m + (k%m) ] * t
        Fout[k] = val

    return Fout

<commit_msg>*** empty log message ***<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)

    m = n/p
    Fm=[]
    for q in range(p): # 0,1
        fp = f[q::p]
        Fp = fft( fp )
        Fm.extend( Fp )

    Fout=[0]*n
    for k in range(n):
        val = 0
        for q in range(p):
            t = e ** ( j*2*pi*k*q/n )
            val += Fm[ q*m + (k%m) ] * t
        Fout[k] = val

    return Fout

def test(f=range(256),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.16962384669978708, 'fraction_numerical': 0.027679205110007096, 'mean_word_length': 1.5133689839572193, 'pattern_counts': {'":': 0, '<': 3, '<?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': '1226722', 'n_tokens_mistral': 626, 'n_tokens_neox': 605, 'n_words': 153}