# [Numpy-discussion] Correlation function about a factor of 100 slower than matlab/mathcad ... but with fft even worse ?

qubax at gmx.at qubax at gmx.at
Wed Nov 25 17:50:36 EST 2009

```My own solution (i just heard that a very similar fix is (about to
be) included in the new svn version) - for those who need a quickfix:

*) This quick and dirty solution is about a factor of 300 faster
for an input of 10^5 random numbers. Probably alot more for larger
vectors.

*) The deviation from correlate(v,v,mode='full') is max. about 10^-10 and
similar to the difference between conv() and xcorr() in matlab.

The trick: please notice the fft(x,2**_nextPow2()) part.

------------------------------------------

def myXcorrfun(x):
len_x=len(a)
maxlag = len_x - 1
c = ifft(abs(fft(x,2**__nextPowOf2(2*len_x-1)))**2)
# force it to be real
c = real(c)
c_final = append(c[-maxlag:],c[0:maxlag+1])
return c_final

def __nextPowOf2(x):
# round up what remains after log2 ... that should be
# the next highest power of 2 for the given number
return ceil(log2(x))

----------------------------------------

you can give it a quick try via:

expon = range(5)

for k in expon:
a = random.rand(10**k)
print 'testing with 10^',k,' random numbers'

tic=time.time()
myc = myXcorrfun(a)
mytime = time.time()-tic
print mytime,'seconds for myXcorr'

tic=time.time()
pyc = correlate(a,a,mode='full')
pytime = time.time()-tic
print pytime,'seconds for scipy correlate'
print
print 'estimated speedup:', int(pytime/mytime)
print max(myc-pyc),' max deviation between the two'
print

I hope it helps one or the other out there.

With best regards,
q

On Wed, Nov 25, 2009 at 09:09:50PM +0200, Pauli Virtanen wrote:
> ke, 2009-11-25 kello 19:23 +0100, qubax at gmx.at kirjoitti:
> [clip]
> > Could someone please investigate why correlate and especially
> > fftconvolve are orders of magnitude slower?
>
>
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion at scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion

--
The king who needs to remind his people of his rank, is no king.

A beggar's mistake harms no one but the beggar. A king's mistake,
however, harms everyone but the king. Too often, the measure of
power lies not in the number who obey your will, but in the number