ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 11 Sep 2013 12:51:55 +0200Are finite field computations slow?https://ask.sagemath.org/question/10533/are-finite-field-computations-slow/I ran the following in Sage 4.5.3 on a MacBook Pro (running OSX):
p = 5;
pow = 2;
k = GF(5 ** pow, 'z');
f(x, y) = y^3 + y + 4*x;
def count_pts():
retval = 0;
for a in k:
for b in k:
if (f(a, b) == 0):
retval = retval + 1;
return retval + 1;
count_pts()
It took around 10-20 seconds to return the correct answer of 26. With pow = 1 it terminated much more quickly. The loop is only over 625 pairs of elements of GF(25); is there some reason this program runs so slowly? (And can the performance be improved?)Tue, 10 Sep 2013 22:00:03 +0200https://ask.sagemath.org/question/10533/are-finite-field-computations-slow/Answer by ppurka for <p>I ran the following in Sage 4.5.3 on a MacBook Pro (running OSX):</p>
<pre><code>p = 5;
pow = 2;
k = GF(5 ** pow, 'z');
f(x, y) = y^3 + y + 4*x;
def count_pts():
retval = 0;
for a in k:
for b in k:
if (f(a, b) == 0):
retval = retval + 1;
return retval + 1;
count_pts()
</code></pre>
<p>It took around 10-20 seconds to return the correct answer of 26. With pow = 1 it terminated much more quickly. The loop is only over 625 pairs of elements of GF(25); is there some reason this program runs so slowly? (And can the performance be improved?)</p>
https://ask.sagemath.org/question/10533/are-finite-field-computations-slow/?answer=15442#post-id-15442You are not using it the correct way. You defined `f(x,y)` over the symbolic ring but then you are doing the computations `f(a, b)` over the finite field. So, at every step it has to coerce everything to the finite field. You should be using the `PolynomialRing` to get your variables and constants coerced to the finite field at the very outset.
Try the following code. It is fast.
f(x,y) = y^3 + y + 4*x
print "Original polynomial's base ring:", f.base_ring()
k = GF(25, 'a')
F.<x,y> = PolynomialRing(k) # x,y are not symbolic variables now
f = y^3 + y + 4*x
print "New base ring:", f.base_ring()
count = 0
for a in k:
for b in k:
if not f.subs(x=a, y=b):
count += 1
print count
The output of above:
Original polynomial's base ring: Symbolic Ring
New base ring: Finite Field in a of size 5^2
25Tue, 10 Sep 2013 22:52:03 +0200https://ask.sagemath.org/question/10533/are-finite-field-computations-slow/?answer=15442#post-id-15442Comment by nbruin for <p>You are not using it the correct way. You defined <code>f(x,y)</code> over the symbolic ring but then you are doing the computations <code>f(a, b)</code> over the finite field. So, at every step it has to coerce everything to the finite field. You should be using the <code>PolynomialRing</code> to get your variables and constants coerced to the finite field at the very outset.</p>
<p>Try the following code. It is fast.</p>
<pre><code>f(x,y) = y^3 + y + 4*x
print "Original polynomial's base ring:", f.base_ring()
k = GF(25, 'a')
F.<x,y> = PolynomialRing(k) # x,y are not symbolic variables now
f = y^3 + y + 4*x
print "New base ring:", f.base_ring()
count = 0
for a in k:
for b in k:
if not f.subs(x=a, y=b):
count += 1
print count
</code></pre>
<p>The output of above:</p>
<pre><code>Original polynomial's base ring: Symbolic Ring
New base ring: Finite Field in a of size 5^2
25
</code></pre>
https://ask.sagemath.org/question/10533/are-finite-field-computations-slow/?comment=17023#post-id-17023(see separate answer)Wed, 11 Sep 2013 04:17:30 +0200https://ask.sagemath.org/question/10533/are-finite-field-computations-slow/?comment=17023#post-id-17023Answer by nbruin for <p>I ran the following in Sage 4.5.3 on a MacBook Pro (running OSX):</p>
<pre><code>p = 5;
pow = 2;
k = GF(5 ** pow, 'z');
f(x, y) = y^3 + y + 4*x;
def count_pts():
retval = 0;
for a in k:
for b in k:
if (f(a, b) == 0):
retval = retval + 1;
return retval + 1;
count_pts()
</code></pre>
<p>It took around 10-20 seconds to return the correct answer of 26. With pow = 1 it terminated much more quickly. The loop is only over 625 pairs of elements of GF(25); is there some reason this program runs so slowly? (And can the performance be improved?)</p>
https://ask.sagemath.org/question/10533/are-finite-field-computations-slow/?answer=15443#post-id-15443Not an answer, but it doesn't fit in a comment box and relevant, I think. With:
def test1():
count = 0
for a in k:
for b in k:
if not f.subs(x=a, y=b):
count += 1
return count
def test2():
count = 0
for a in k:
for b in k:
if not f(a, b):
count += 1
return count
def test3():
count = 0
for a in k:
for b in k:
if not (b^3+b+4*a):
count += 1
return count
we get
sage: timeit('test1()')
25 loops, best of 3: 24.6 ms per loop
sage: timeit('test2()')
5 loops, best of 3: 64.1 ms per loop
sage: timeit('test3()')
125 loops, best of 3: 2.73 ms per loop
so, surprisingly, subs is quite a bit faster than "polynomial evaluation", and unsurprisingly writing out the expression explicitly is of course even faster than either.
The subs method gives back a result in a ring that's a little too large for the purposes, though (this is as documented):
sage: parent(f.subs(x=k(1),y=k(1)))
Multivariate Polynomial Ring in x, y over Finite Field in a of size 5^2
sage: parent(f(k(1),k(1)))
Finite Field in a of size 5^2
Wed, 11 Sep 2013 04:21:53 +0200https://ask.sagemath.org/question/10533/are-finite-field-computations-slow/?answer=15443#post-id-15443Comment by nbruin for <p>Not an answer, but it doesn't fit in a comment box and relevant, I think. With:</p>
<pre><code>def test1():
count = 0
for a in k:
for b in k:
if not f.subs(x=a, y=b):
count += 1
return count
def test2():
count = 0
for a in k:
for b in k:
if not f(a, b):
count += 1
return count
def test3():
count = 0
for a in k:
for b in k:
if not (b^3+b+4*a):
count += 1
return count
</code></pre>
<p>we get</p>
<pre><code>sage: timeit('test1()')
25 loops, best of 3: 24.6 ms per loop
sage: timeit('test2()')
5 loops, best of 3: 64.1 ms per loop
sage: timeit('test3()')
125 loops, best of 3: 2.73 ms per loop
</code></pre>
<p>so, surprisingly, subs is quite a bit faster than "polynomial evaluation", and unsurprisingly writing out the expression explicitly is of course even faster than either.</p>
<p>The subs method gives back a result in a ring that's a little too large for the purposes, though (this is as documented):</p>
<pre><code>sage: parent(f.subs(x=k(1),y=k(1)))
Multivariate Polynomial Ring in x, y over Finite Field in a of size 5^2
sage: parent(f(k(1),k(1)))
Finite Field in a of size 5^2
</code></pre>
https://ask.sagemath.org/question/10533/are-finite-field-computations-slow/?comment=17019#post-id-17019Yes, there is a good reason for that. For polynomials, there is an explicit
order of the variables, so in R.<x,y> we have that f(a,b) evaluates at x=a,y=b
and in S.<y,x> we have that g(a,b) evaluates at y=a, x=b. Since there is no room
for ambiguity we can safely use mathematical notation.
In SR there is no such implicit variable order (it's not even completely evident
which variables do occur in an expression: is F= 0.0*x+1.0*y in one or two
variables? There is a "callable" form of symbolic expressions, but those are
different from normal SR elements.
Finally, the fact that for (at least some) polynomials, f.subs(...) works and
produces (by default at least) an element in the same symbolic ring is also in
step with what happens in SR. The fact that it's faster than f(...) in this
particular situation is a bit uncomfortable. It might be because these are
libsingular polynomials, so operations that take place entirely in the library
can be made a little more efficient. Also, perhaps f.__call__ can be improved.
Wed, 11 Sep 2013 12:51:55 +0200https://ask.sagemath.org/question/10533/are-finite-field-computations-slow/?comment=17019#post-id-17019Comment by ppurka for <p>Not an answer, but it doesn't fit in a comment box and relevant, I think. With:</p>
<pre><code>def test1():
count = 0
for a in k:
for b in k:
if not f.subs(x=a, y=b):
count += 1
return count
def test2():
count = 0
for a in k:
for b in k:
if not f(a, b):
count += 1
return count
def test3():
count = 0
for a in k:
for b in k:
if not (b^3+b+4*a):
count += 1
return count
</code></pre>
<p>we get</p>
<pre><code>sage: timeit('test1()')
25 loops, best of 3: 24.6 ms per loop
sage: timeit('test2()')
5 loops, best of 3: 64.1 ms per loop
sage: timeit('test3()')
125 loops, best of 3: 2.73 ms per loop
</code></pre>
<p>so, surprisingly, subs is quite a bit faster than "polynomial evaluation", and unsurprisingly writing out the expression explicitly is of course even faster than either.</p>
<p>The subs method gives back a result in a ring that's a little too large for the purposes, though (this is as documented):</p>
<pre><code>sage: parent(f.subs(x=k(1),y=k(1)))
Multivariate Polynomial Ring in x, y over Finite Field in a of size 5^2
sage: parent(f(k(1),k(1)))
Finite Field in a of size 5^2
</code></pre>
https://ask.sagemath.org/question/10533/are-finite-field-computations-slow/?comment=17021#post-id-17021This is quite confusing and inconsistent. For symbolic rings it is advised to use `subs`, and then when it comes to polynomial rings one can evaluate just like that?
sage: f(x, y) = x^2 + y # symbolic function
sage: f(1, 2)
3
sage: g = x^2 + y # symbolic expression
sage: g(1, 2)
... DeprecationWarning: Substitution using function-call syntax and unnamed arguments is deprecated and will be removed from a future release of Sage; you can use named arguments instead, like EXPR(x=..., y=...)
See http://trac.sagemath.org/5930 for details.
exec code_obj in self.user_global_ns, self.user_ns
3
sage: F.<x,y> = PolynomialRing(RR)
sage: h = x^2 + y # polynomial
sage: h(1, 2)
3.00000000000000Wed, 11 Sep 2013 08:16:31 +0200https://ask.sagemath.org/question/10533/are-finite-field-computations-slow/?comment=17021#post-id-17021