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.Mon, 28 Dec 2020 18:13:29 +0100Translating a GAP-output for Sagehttps://ask.sagemath.org/question/54967/translating-a-gap-output-for-sage/I made the following code in GAP to generate all monic irreducible polynomials of degree n with coefficients 1,-1 or 0 and non-zero constant term:
n:=7;d:=n-1;x:=Indeterminate(Rationals,1);U:=Tuples([-1,1,0],n);UU:=Filtered(U,x->(x[1]=0)=false and x[n]=1);W:=[];for i in UU do Append(W,[UnivariatePolynomial(Rationals,i,1)]);od;WW:=Filtered(W,x->IsIrreducible(x)=true);WW;
Now I wanted to use the resulting list WW in Sage to do operations only Sage can do. But how do I get WW now in Sage?
It seems very complicated and using https://sagecell.sagemath.org/ (where the language is set to "GAP") produces
no output, while the output is displayed without any problems when I use a terminal for GAP.
Is there an easy solution for my problem? (other than programming it in Sage, which would also be interesting but it seems it is easier to deal with the generation of polynomials via GAP)Mon, 28 Dec 2020 00:33:04 +0100https://ask.sagemath.org/question/54967/translating-a-gap-output-for-sage/Comment by slelievre for <p>I made the following code in GAP to generate all monic irreducible polynomials of degree n with coefficients 1,-1 or 0 and non-zero constant term:</p>
<pre><code>n:=7;d:=n-1;x:=Indeterminate(Rationals,1);U:=Tuples([-1,1,0],n);UU:=Filtered(U,x->(x[1]=0)=false and x[n]=1);W:=[];for i in UU do Append(W,[UnivariatePolynomial(Rationals,i,1)]);od;WW:=Filtered(W,x->IsIrreducible(x)=true);WW;
</code></pre>
<p>Now I wanted to use the resulting list WW in Sage to do operations only Sage can do. But how do I get WW now in Sage?
It seems very complicated and using <a href="https://sagecell.sagemath.org/">https://sagecell.sagemath.org/</a> (where the language is set to "GAP") produces
no output, while the output is displayed without any problems when I use a terminal for GAP.</p>
<p>Is there an easy solution for my problem? (other than programming it in Sage, which would also be interesting but it seems it is easier to deal with the generation of polynomials via GAP)</p>
https://ask.sagemath.org/question/54967/translating-a-gap-output-for-sage/?comment=54969#post-id-54969Suggestion: always make your question as simple as possible.
Here you could ask with `n := 3` or `n := 2` as the simplest illustrating examples.Mon, 28 Dec 2020 05:20:43 +0100https://ask.sagemath.org/question/54967/translating-a-gap-output-for-sage/?comment=54969#post-id-54969Answer by slelievre for <p>I made the following code in GAP to generate all monic irreducible polynomials of degree n with coefficients 1,-1 or 0 and non-zero constant term:</p>
<pre><code>n:=7;d:=n-1;x:=Indeterminate(Rationals,1);U:=Tuples([-1,1,0],n);UU:=Filtered(U,x->(x[1]=0)=false and x[n]=1);W:=[];for i in UU do Append(W,[UnivariatePolynomial(Rationals,i,1)]);od;WW:=Filtered(W,x->IsIrreducible(x)=true);WW;
</code></pre>
<p>Now I wanted to use the resulting list WW in Sage to do operations only Sage can do. But how do I get WW now in Sage?
It seems very complicated and using <a href="https://sagecell.sagemath.org/">https://sagecell.sagemath.org/</a> (where the language is set to "GAP") produces
no output, while the output is displayed without any problems when I use a terminal for GAP.</p>
<p>Is there an easy solution for my problem? (other than programming it in Sage, which would also be interesting but it seems it is easier to deal with the generation of polynomials via GAP)</p>
https://ask.sagemath.org/question/54967/translating-a-gap-output-for-sage/?answer=54970#post-id-54970This answer is threefold:
- first follow the instructions and stick to using GAP
- then propose a generator written in Sage
- finally compare the two generators
## Call GAP from Sage via libGAP
We run the requested GAP commands via libGAP.
Tiny fixes and simplifications:
- degree $n$ polynomials have $n + 1$ coefficients
- remove some unneeded bits
Version (a) uses the code in the question with tiny simplifications:
def poly_list_a(n):
r"""
Return a list of ZZ-irreducible monic polynomials of this degree
with coefficients 0, 1 or -1 and nonzero constant coefficient.
"""
commands = f"""
n := {n + 1}
d := n - 1
U := Tuples([-1, 1, 0], n)
UU := Filtered(U, x -> (x[1] = 0) = false and x[n] = 1)
W := []
for i in UU do Append(W, [UnivariatePolynomial(Rationals, i)]); od
WW := Filtered(W, x -> IsIrreducible(x) = true)
"""[1:-1]
for command in commands.split('\n'):
if command:
_ = libgap.eval(command)
return libgap.eval("WW").sage()
Version (b) tries to be a bit faster by not generating all tuples:
def poly_list_b(n):
r"""
Return a list of ZZ-irreducible monic polynomials of this degree
with coefficients 0, 1 or -1 and nonzero constant coefficient.
"""
commands = f"""
n := {n}
d := n - 1
T := Tuples([-1, 1, 0], d)
P := []
for t in T do Append(P, Filtered(List([-1, 1], c -> UnivariatePolynomial(Integers, Concatenation([c], t, [1]))), IsIrreducible)); od
"""[1:-1]
for command in commands.split('\n'):
if command:
_ = libgap.eval(command)
return libgap.eval("P").sage()
Version (c) condenses the code quite a bit more:
def poly_list_c(n):
r"""
Return a list of ZZ-irreducible monic polynomials of this degree
with coefficients 0, 1 or -1 and nonzero constant coefficient.
"""
commands = f"""
n := {n}
T := Cartesian([[-1], [1]], Tuples([-1, 1, 0], n - 1), [[1]])
P := Filtered(List(T, t -> UnivariatePolynomial(Integers, Concatenation(t))), IsIrreducible)
"""[1:-1]
for command in commands.split('\n'):
if command:
_ = libgap.eval(command)
return libgap.eval("P").sage()
Usage:
sage: poly_list = poly_list_c # pick a or b or c
sage: print('\n'.join(str(p) for p in poly_list(1)))
x - 1
x + 1
sage: print('\n'.join(str(p) for p in poly_list(2)))
x^2 - x - 1
x^2 + x - 1
x^2 - x + 1
x^2 + 1
x^2 + x + 1
## Sage code for a similar generator
Here we propose a generator written directly in Sage.
This calls other software too, but avoids mixing code
in several languages at the user level.
We use the built-in generator for polynomials of given maximal degree
over the finite field with three elements, and convert its polynomials
to polynomials over `ZZ` with a little trick.
Transforming a polynomial to a dictionary skips `0` coefficients;
the `1` and `2` coefficients can be mapped to `1` and `-1` by
the map `x -> 3 - 2*x` (after converting from `GF(3)` to `ZZ`).
def polys(n):
r"""
Generator for ZZ-irreducible monic polynomials of this degree
with coefficients 0, 1 or -1 and nonzero constant coefficient.
INPUT:
- ``nn`` -- a positive integer (the degree)
EXAMPLES::
sage: print('\n'.join(str(p) for p in polys(1)))
x + 1
x - 1
sage: print('\n'.join(str(p) for p in polys(2)))
x^2 + 1
x^2 - 1
x^2 + x + 1
x^2 + x - 1
x^2 - x + 1
x^2 - x - 1
TESTS::
sage: print('\n'.join(str(p) for p in polys(0)))
Traceback (most recent call last):
...
ValueError: Expected positive integer, got: 0
"""
import numbers
if not isinstance(n, numbers.Integral) or n < 1:
raise ValueError(f"Expected positive integer, got: {n}")
Zx = ZZ['x']
for p in GF(3)['x'].polynomials(max_degree=n - 2):
coeffs = {k + 1: 3 - 2*ZZ(c) for k, c in p.dict().items()}
coeffs[n] = 1
q = Zx(coeffs)
for p in [q + 1, q - 1]:
if p.is_irreducible():
yield p
Usage:
sage: print('\n'.join(str(p) for p in polys(1)))
x + 1
x - 1
sage: print('\n'.join(str(p) for p in polys(2)))
x^2 + 1
x^2 + x + 1
x^2 + x - 1
x^2 - x + 1
x^2 - x - 1
## Comparison
The good thing is both methods give the same polynomials:
sage: all(set(polys(n)) == set(poly_list(n)) for n in range(1, 8))
True
The `poly_list_a` function is a bit wasteful by removing tuples
starting by `0` or not ending by `1` only after generating them,
so it uses 2 out of 9 of the tuples it generates.
This is fixed in `poly_list_b` and `poly_list_c`.
The gain is not spectacular since irreducibility tests dominate.
The serious drawback in `poly_list_*` is generating the
whole list of polynomials rather than generating
the polynomials one by one.
To test the speed of the various functions, we run through
all the polynomials they give and do something fast with
each polyomial, i.e. check that it is nonzero.
For n = 5, here are the timings:
sage: timeit('all(poly_list_a(5))')
5 loops, best of 3: 449 ms per loop
sage: timeit('all(poly_list_b(5))')
5 loops, best of 3: 420 ms per loop
sage: timeit('all(poly_list_c(5))')
5 loops, best of 3: 409 ms per loop
sage: timeit('all(polys(5))')
5 loops, best of 3: 55.4 ms per loop
The generator programmed in Sage is much faster;
not sure what dominates in the speed difference:
- the overhead of calling libgap
- the overhead of storing a list
- other factors?
The GAP code might possibly be improved, e.g. by using
GAP iterators but my GAP skills are limited.
Mon, 28 Dec 2020 08:59:43 +0100https://ask.sagemath.org/question/54967/translating-a-gap-output-for-sage/?answer=54970#post-id-54970Comment by klaaa for <p>This answer is threefold:</p>
<ul>
<li>first follow the instructions and stick to using GAP</li>
<li>then propose a generator written in Sage</li>
<li>finally compare the two generators</li>
</ul>
<h2>Call GAP from Sage via libGAP</h2>
<p>We run the requested GAP commands via libGAP.</p>
<p>Tiny fixes and simplifications:</p>
<ul>
<li>degree $n$ polynomials have $n + 1$ coefficients</li>
<li>remove some unneeded bits</li>
</ul>
<p>Version (a) uses the code in the question with tiny simplifications:</p>
<pre><code>def poly_list_a(n):
r"""
Return a list of ZZ-irreducible monic polynomials of this degree
with coefficients 0, 1 or -1 and nonzero constant coefficient.
"""
commands = f"""
n := {n + 1}
d := n - 1
U := Tuples([-1, 1, 0], n)
UU := Filtered(U, x -> (x[1] = 0) = false and x[n] = 1)
W := []
for i in UU do Append(W, [UnivariatePolynomial(Rationals, i)]); od
WW := Filtered(W, x -> IsIrreducible(x) = true)
"""[1:-1]
for command in commands.split('\n'):
if command:
_ = libgap.eval(command)
return libgap.eval("WW").sage()
</code></pre>
<p>Version (b) tries to be a bit faster by not generating all tuples:</p>
<pre><code>def poly_list_b(n):
r"""
Return a list of ZZ-irreducible monic polynomials of this degree
with coefficients 0, 1 or -1 and nonzero constant coefficient.
"""
commands = f"""
n := {n}
d := n - 1
T := Tuples([-1, 1, 0], d)
P := []
for t in T do Append(P, Filtered(List([-1, 1], c -> UnivariatePolynomial(Integers, Concatenation([c], t, [1]))), IsIrreducible)); od
"""[1:-1]
for command in commands.split('\n'):
if command:
_ = libgap.eval(command)
return libgap.eval("P").sage()
</code></pre>
<p>Version (c) condenses the code quite a bit more:</p>
<pre><code>def poly_list_c(n):
r"""
Return a list of ZZ-irreducible monic polynomials of this degree
with coefficients 0, 1 or -1 and nonzero constant coefficient.
"""
commands = f"""
n := {n}
T := Cartesian([[-1], [1]], Tuples([-1, 1, 0], n - 1), [[1]])
P := Filtered(List(T, t -> UnivariatePolynomial(Integers, Concatenation(t))), IsIrreducible)
"""[1:-1]
for command in commands.split('\n'):
if command:
_ = libgap.eval(command)
return libgap.eval("P").sage()
</code></pre>
<p>Usage:</p>
<pre><code>sage: poly_list = poly_list_c # pick a or b or c
sage: print('\n'.join(str(p) for p in poly_list(1)))
x - 1
x + 1
sage: print('\n'.join(str(p) for p in poly_list(2)))
x^2 - x - 1
x^2 + x - 1
x^2 - x + 1
x^2 + 1
x^2 + x + 1
</code></pre>
<h2>Sage code for a similar generator</h2>
<p>Here we propose a generator written directly in Sage.</p>
<p>This calls other software too, but avoids mixing code
in several languages at the user level.</p>
<p>We use the built-in generator for polynomials of given maximal degree
over the finite field with three elements, and convert its polynomials
to polynomials over <code>ZZ</code> with a little trick.</p>
<p>Transforming a polynomial to a dictionary skips <code>0</code> coefficients;
the <code>1</code> and <code>2</code> coefficients can be mapped to <code>1</code> and <code>-1</code> by
the map <code>x -> 3 - 2*x</code> (after converting from <code>GF(3)</code> to <code>ZZ</code>).</p>
<pre><code>def polys(n):
r"""
Generator for ZZ-irreducible monic polynomials of this degree
with coefficients 0, 1 or -1 and nonzero constant coefficient.
INPUT:
- ``nn`` -- a positive integer (the degree)
EXAMPLES::
sage: print('\n'.join(str(p) for p in polys(1)))
x + 1
x - 1
sage: print('\n'.join(str(p) for p in polys(2)))
x^2 + 1
x^2 - 1
x^2 + x + 1
x^2 + x - 1
x^2 - x + 1
x^2 - x - 1
TESTS::
sage: print('\n'.join(str(p) for p in polys(0)))
Traceback (most recent call last):
...
ValueError: Expected positive integer, got: 0
"""
import numbers
if not isinstance(n, numbers.Integral) or n < 1:
raise ValueError(f"Expected positive integer, got: {n}")
Zx = ZZ['x']
for p in GF(3)['x'].polynomials(max_degree=n - 2):
coeffs = {k + 1: 3 - 2*ZZ(c) for k, c in p.dict().items()}
coeffs[n] = 1
q = Zx(coeffs)
for p in [q + 1, q - 1]:
if p.is_irreducible():
yield p
</code></pre>
<p>Usage:</p>
<pre><code>sage: print('\n'.join(str(p) for p in polys(1)))
x + 1
x - 1
sage: print('\n'.join(str(p) for p in polys(2)))
x^2 + 1
x^2 + x + 1
x^2 + x - 1
x^2 - x + 1
x^2 - x - 1
</code></pre>
<h2>Comparison</h2>
<p>The good thing is both methods give the same polynomials:</p>
<pre><code>sage: all(set(polys(n)) == set(poly_list(n)) for n in range(1, 8))
True
</code></pre>
<p>The <code>poly_list_a</code> function is a bit wasteful by removing tuples
starting by <code>0</code> or not ending by <code>1</code> only after generating them,
so it uses 2 out of 9 of the tuples it generates.</p>
<p>This is fixed in <code>poly_list_b</code> and <code>poly_list_c</code>.
The gain is not spectacular since irreducibility tests dominate.</p>
<p>The serious drawback in <code>poly_list_*</code> is generating the
whole list of polynomials rather than generating
the polynomials one by one.</p>
<p>To test the speed of the various functions, we run through
all the polynomials they give and do something fast with
each polyomial, i.e. check that it is nonzero.</p>
<p>For n = 5, here are the timings:</p>
<pre><code>sage: timeit('all(poly_list_a(5))')
5 loops, best of 3: 449 ms per loop
sage: timeit('all(poly_list_b(5))')
5 loops, best of 3: 420 ms per loop
sage: timeit('all(poly_list_c(5))')
5 loops, best of 3: 409 ms per loop
sage: timeit('all(polys(5))')
5 loops, best of 3: 55.4 ms per loop
</code></pre>
<p>The generator programmed in Sage is much faster;
not sure what dominates in the speed difference:</p>
<ul>
<li>the overhead of calling libgap</li>
<li>the overhead of storing a list</li>
<li>other factors?</li>
</ul>
<p>The GAP code might possibly be improved, e.g. by using
GAP iterators but my GAP skills are limited.</p>
https://ask.sagemath.org/question/54967/translating-a-gap-output-for-sage/?comment=54973#post-id-54973Thank you very much for this detailed answer!Mon, 28 Dec 2020 18:13:29 +0100https://ask.sagemath.org/question/54967/translating-a-gap-output-for-sage/?comment=54973#post-id-54973