1 | initial version |
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 sample generation.
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.
2 | No.2 Revision |
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 sample generation.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.