Fast evaluation of big polynomials

edit

If i do the following, on a 5-year old laptop i got:

sage: R = BooleanPolynomialRing(256,'x')
sage: P = R.random_element(degree=8, terms=100)
sage: L = [ZZ.random_element(2) for _ in range(256)]
sage: %timeit P(*L)
1000 loops, best of 3: 988 µs per loop

Which seems not so long, especially if you only have 256 polynomials to test. So, could you please be more precise on how you constructed your polynomials, what are your timings, and which timings do you expect ?

The problem with the code sample you posted in your second comment isn't the part you highlighted, but the first loop, i.e. the generation of the polynomials.

Indeed, on my 5 year old Intel Core i5 2500K I get

sage: R = BooleanPolynomialRing(256,'x')
sage: %timeit R.random_element(degree=8,terms=10)
100 loops, best of 3: 11.3 ms per loop
sage: %timeit R.random_element(degree=8,terms=100)
10 loops, best of 3: 112 ms per loop
sage: %timeit R.random_element(degree=8,terms=1000)
1 loops, best of 3: 1.12 s per loop
sage: %timeit R.random_element(degree=8,terms=10000)
1 loops, best of 3: 11.3 s per loop
sage: %timeit R.random_element(degree=8,terms=100000)
1 loops, best of 3: 1min 52s per loop

which suggests that the time to generate a random polynomial of degree at most $8$ in $256$ variables scales linearly with the number of terms. Now, the total number of monomials of degree at most $8$ is

$$ \sum_{k=0}^8 {{256}\choose{k}} = 423203101008289 $$

(which I computed with sum(map(lambda k: binomial(256,k), range(0,9)))), thus the time needed to generate one polynomial with R.random_element(degree=8,terms=+infinity) should be

sage: t = 423203101008289/1000 * 1.12 * s
sage: t.convert(units.time.year)
15030.0441758398*year

On the other hand, you could try to speed this up with the choose_degree=True option, which helps a little bit

sage: %timeit R.random_element(degree=8, terms=1000, choose_degree=True)
10 loops, best of 3: 47.1 ms per loop
sage: %timeit R.random_element(degree=8, terms=10000, choose_degree=True)
1 loops, best of 3: 523 ms per loop
sage: %timeit R.random_element(degree=8, terms=100000, choose_degree=True)
1 loops, best of 3: 6.66 s per loop
sage: %timeit R.random_element(degree=8, terms=1000000, choose_degree=True)
1 loops, best of 3: 1min 28s per loop

although I almost ran out of my 8 GB of RAM with the last one, so unless you have access to lots of memory it is unlikely that you would be able to store the result of R.random_element(degree=8,terms=+infinity) even if you could compute it in a reasonable time, let alone $256$ of those...

Final note: If you don't need to use your polynomials more than once, you could try to directly generate their evaluation at some given point, although I fear that won't help much. Anyway, since this is for your master thesis I suggest you bring the problem up with your advisor.