I have the following code. In principle it takes 2^6 * 1000 = 64000 iterations which is quite a small number. However it takes 9s on my computer and I would like to run it for n = 15 at least.

from __future__ import division
import numpy as np
import itertoolsn=6
iters = 1000
firstzero = 0
bothzero = 0
for S in itertools.product([-1,1], repeat = n+1):for i in xrange(iters):F = np.random.choice(np.array([-1,0,0,1], dtype=np.int8), size = n)while np.all(F ==0):F = np.random.choice(np.array([-1,0,0,1], dtype=np.int8), size = n)FS = np.convolve(F,S, 'valid')if (FS[0] == 0):firstzero += 1if np.all(FS==0):bothzero += 1print "firstzero",    firstzero
print "bothzero",  bothzero

Is it possible to speed this up a lot or should I rewrite it in C?

Profiling indicates it spends most of it time in

   258003    0.418    0.000    3.058    0.000 fromnumeric.py:1842(all)130003    1.245    0.000    2.907    0.000 {method 'choice' of 'mtrand.RandomState' objects}388006    2.488    0.000    2.488    0.000 {method 'reduce' of 'numpy.ufunc' objects}128000    0.731    0.000    2.215    0.000 numeric.py:873(convolve)258003    0.255    0.000    2.015    0.000 {method 'all' of 'numpy.ndarray' objects}258003    0.301    0.000    1.760    0.000 _methods.py:35(_all)130003    0.470    0.000    1.663    0.000 fromnumeric.py:2249(prod)644044    1.483    0.000    1.483    0.000 {numpy.core.multiarray.array}130003    0.164    0.000    1.193    0.000 _methods.py:27(_prod)258003    0.283    0.000    0.624    0.000 numeric.py:462(asanyarray)

An almost fully vectorized version of your code is much faster (16.9%), suppose yours is named f():

def g():n=6iters = 1000S=np.repeat(list(itertools.product([-1,1], repeat = n+1)),iters, axis=0).reshape((-1,n+1))F=np.random.choice(np.array([-1,0,0,1], dtype=np.int8), size = (iters*(2**(n+2)),n)) #oversamplingF=F[~(F==0).all(1)][:iters*(2**(n+1))]FS=np.asanyarray(map(lambda x, y: np.convolve(x, y, 'valid'), F, S))firstzero=(FS[:,0]==0).sum()bothzero=(FS==0).all(1).sum()print "firstzero",    firstzeroprint "bothzero",  bothzero

Timing result:

In [164]:%timeit f()
firstzero 27171
bothzero 12151
firstzero 27206
bothzero 12024
firstzero 27272
bothzero 12135
firstzero 27173
bothzero 12079
1 loops, best of 3: 14.6 s per loop
In [165]:%timeit g()
firstzero 27182
bothzero 11952
firstzero 27365
bothzero 12174
firstzero 27318
bothzero 12173
firstzero 27377
bothzero 12072
1 loops, best of 3: 2.47 s per loop