#9540: Testing whether a Gaussian integer is in ZZ is extremely slow
-------------------------------------+--------------------------
Reporter: fredrik.johansson | Owner: AlexGhitza
Type: defect | Status: new
Priority: major | Milestone:
Component: basic arithmetic | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
-------------------------------------+--------------------------
Comment (by tscrim):
`ZZ.__contains__` is the default `Parent.__contains__`, and as such,
checks by seeing if `z` can convert into itself. However, what is
interesting is the difference between `y` and `z`. Both have a Python
`_integer_` in a Cython file. I am wondering if it has to do with the
difference in the conversion maps between their respective parents:
{{{
sage: ZZ.convert_map_from(y.parent())
Generic map:
From: Rational Field
To: Integer Ring
sage: ZZ.convert_map_from(z.parent())
Conversion via _integer_ method map:
From: Number Field in I with defining polynomial x^2 + 1
To: Integer Ring
}}}
However, there are a lot more computations done for `z` than for `y`:
{{{
sage: %prun y in ZZ
2 function calls in 0.000 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 {method 'disable' of
'_lsprof.Profiler' objects}
sage: %prun z in ZZ
32 function calls in 0.000 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <string>:1(<module>)
1 0.000 0.000 0.000 0.000
polynomial_ring.py:299(_element_constructor_)
1 0.000 0.000 0.000 0.000
polynomial_ring_constructor.py:50(PolynomialRing)
1 0.000 0.000 0.000 0.000 rings.py:708(__getitem__)
1 0.000 0.000 0.000 0.000 number_field.py:4871(gen)
2 0.000 0.000 0.000 0.000 re.py:230(_compile)
1 0.000 0.000 0.000 0.000
{sage.structure.category_object.normalize_names}
1 0.000 0.000 0.000 0.000 rings.py:827(normalize_arg)
1 0.000 0.000 0.000 0.000
polynomial_ring_constructor.py:497(_single_variate)
2 0.000 0.000 0.000 0.000 {method 'sub' of
'_sre.SRE_Pattern' objects}
1 0.000 0.000 0.000 0.000
polynomial_ring_constructor.py:482(_get_from_cache)
2 0.000 0.000 0.000 0.000 re.py:148(sub)
10 0.000 0.000 0.000 0.000 {isinstance}
1 0.000 0.000 0.000 0.000
rational_field.py:233(_repr_option)
2 0.000 0.000 0.000 0.000
{sage.structure.element.is_Element}
1 0.000 0.000 0.000 0.000 {sage.rings.ring.is_Ring}
1 0.000 0.000 0.000 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'split' of 'str'
objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of
'_lsprof.Profiler' objects}
}}}
Note: the first time this is run, there are more computations for both of
them likely due to creating the conversion and checking if there is a
coercion. In a fresh session:
{{{
sage: y = 3/5
sage: z = (5+I).pyobject()
sage: %time y in ZZ
CPU times: user 171 µs, sys: 30 µs, total: 201 µs
Wall time: 195 µs
False
sage: %time z in ZZ
CPU times: user 1.02 ms, sys: 0 ns, total: 1.02 ms
Wall time: 485 µs
False
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/9540#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
