[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

*) 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):
  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'

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

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

I hope it helps one or the other out there.

With best regards,

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?
> Read http://projects.scipy.org/numpy/ticket/1260
> _______________________________________________
> 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
who suffer your stupidity.

More information about the NumPy-Discussion mailing list