Opened 10 years ago
Closed 7 years ago
#7160 closed defect (fixed)
comparison with quadratic number field elements
Reported by: | mhansen | Owned by: | davidloeffler |
---|---|---|---|
Priority: | major | Milestone: | sage-5.11 |
Component: | number fields | Keywords: | sd35 |
Cc: | vdelecroix | Merged in: | sage-5.11.beta0 |
Authors: | Vincent Delecroix | Reviewers: | Burcin Erocal |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #13213 | Stopgaps: |
Description (last modified by )
sage: I^2 -1 sage: bool(I^2 < 0) True sage: bool(I^2 > 0) True
Apply:
Attachments (5)
Change History (33)
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
comment:3 Changed 10 years ago by
- Status changed from needs_review to needs_work
I think this is confusing: you have an ordering of elements of a real or imaginary quadratic field which is based on some kind of lexicographic ordering on the representation of the elements rather than anything mathematical. Presumably this is so lists, etc, can be sorted in a pythonic way. But I find this bizarre:
sage: K.<i> = QuadraticField(-1) sage: i>0 True
and this raises a strange error:
sage: K.<a> = NumberField(x^2+x-10) sage: a < -a --------------------------------------------------------------------------- SystemError Traceback (most recent call last) /home/john/.sage/temp/ubuntu/790/_home_john__sage_init_sage_0.py in <module>() SystemError: error return without exception set sage: Type(K) --------------------------------------------------------------------------- NameError Traceback (most recent call last) /home/john/.sage/temp/ubuntu/790/_home_john__sage_init_sage_0.py in <module>() NameError: name 'Type' is not defined sage: type(K) <class 'sage.rings.number_field.number_field.NumberField_quadratic'>
comment:4 Changed 9 years ago by
- Report Upstream set to N/A
Apparently related to #6132 and #10064, see this sage-devel discussion.
comment:5 Changed 8 years ago by
- Status changed from needs_work to needs_review
I've put up a new patch which is minimally invasive and fixes the issue.
comment:6 Changed 8 years ago by
Does this result in any interesting speed regressions when doing things with I?
comment:7 follow-up: ↓ 9 Changed 8 years ago by
- Typo: " comparision" in sage/rings/number_field/number_field_element_quadratic.pyx.
- This code raises a big red flag for me:
1704 from sage.rings.all import RR 1705 r = RR(right) 1706 l = RR(embedding(left)) 1707 return cmp(l, r)
My concern is that you're comparing to double (=53 bits) precision, which is totally arbitrary. What if there is an embedding and cmp(left, right) requires 54 bits of precision to sort out? I could probably with some work construct a nasty example of this, where the above code just gives totally the wrong answer. I guess we need to (1) compute to precision of the embedding, and (2) if cmp(l,r)==0, then check something more?
- Where is "self._element_class" actually used? I guess by the coercion model, but it's hard to see how from this patch, exactly.
- I feel like this is too much code that gets around a fundamental problem or bug in number field elements in the case of the reported problem, but leaves the underlying bug unfixed. Note that *before* applying your patch:
sage: bool(I^2 < 0) True sage: (I^2).pyobject() < 0 False
It seems to me that the output of both lines above should be the same, right, but I bet pynac is evaluating the first comparison and not even going to the pyobject level. Similarly:
sage: bool(I^2 < SR(0)) True sage: (I^2).pyobject() < SR(0).pyobject() False
This is because in Sage we currently have:
sage: K.<I> = QuadraticField(-1) sage: I^2 < 0 False sage: I^2 -1
This is, as Cremona pointed out, due to the arbitrary lexicographic ordering rather than using the one we get on the intersection of K and R inside embedding(K).
So... it seems to me that the real problem is that the arbitrary ordering is lame. What you've done is implemented a natural fix in one very, very special case. Maybe that's the intention, and maybe you had something more general before? I don't know, since you changed the patch.
I'm guessing your more general patch changed comparison for all elements to:
(1) check if there is an embedding of the parent(s), and (2) if so, use that to induce an embedding on *the* real subfield of the field(s). That would be natural.
So all of the above, is just me understanding why you are doing what you're doing. It might make sense to add something like this to the documentation.
comment:8 Changed 8 years ago by
Note: With sage-4.8.alpha5 and this patch, all tests in devel/sage/sage pass.
comment:9 in reply to: ↑ 7 Changed 8 years ago by
Replying to was:
- This code raises a big red flag for me:
1704 from sage.rings.all import RR 1705 r = RR(right) 1706 l = RR(embedding(left)) 1707 return cmp(l, r)
My concern is that you're comparing to double (=53 bits) precision, which is totally arbitrary. What if there is an embedding and cmp(left, right) requires 54 bits of precision to sort out? I could probably with some work construct a nasty example of this, where the above code just gives totally the wrong answer. I guess we need to (1) compute to precision of the embedding, and (2) if cmp(l,r)==0, then check something more?
Isn't this what we have the QQbar class for?
Changed 8 years ago by
comment:10 Changed 8 years ago by
I've added a new patch which should be better. It turns out just using the embedding directly should be fine.
comment:11 Changed 8 years ago by
- Keywords sd35 added
Changed 8 years ago by
comment:12 Changed 8 years ago by
- Milestone changed from sage-4.8 to sage-5.0
Replying to was:
- I feel like this is too much code that gets around a fundamental problem or bug in number field elements in the case of the reported problem, but leaves the underlying bug unfixed. Note that *before* applying your patch:
sage: bool(I^2 < 0) True sage: (I^2).pyobject() < 0 False
It seems to me that the output of both lines above should be the same, right, but I bet pynac is evaluating the first comparison and not even going to the pyobject level.
The first comparison is done in the test_relation()
method of sage.symbolic.expression.Expression
. This converts both sides of the relation to CIF
and performs the comparison there.
Similarly:
sage: bool(I^2 < SR(0)) True sage: (I^2).pyobject() < SR(0).pyobject() FalseThis is because in Sage we currently have:
sage: K.<I> = QuadraticField(-1) sage: I^2 < 0 False sage: I^2 -1This is, as Cremona pointed out, due to the arbitrary lexicographic ordering rather than using the one we get on the intersection of K and R inside embedding(K).
So... it seems to me that the real problem is that the arbitrary ordering is lame. What you've done is implemented a natural fix in one very, very special case. Maybe that's the intention, and maybe you had something more general before? I don't know, since you changed the patch.
Note that this lame ordering is causing problems all over symbolics since is_positive()
checks fail. See #10849, #10062, #10064 for examples.
I'm guessing your more general patch changed comparison for all elements to:
(1) check if there is an embedding of the parent(s), and (2) if so, use that to induce an embedding on *the* real subfield of the field(s). That would be natural.
I attached a new patch at attachment:trac_7160-quadratic_number_field_element_comparison.patch, based on Mike's last patch attachment:trac_7160.patch. This changes the comparison function of quadratic number field elements to always use the embedding into CC
.
Timings with the patch:
sage: K.<sqrt2> = QuadraticField(2) sage: t = K.random_element(); t -2*sqrt2 - 35 sage: u = K.random_element(); u -1 sage: %timeit res = cmp(t,u) 625 loops, best of 3: 659 µs per loop sage: u = K.random_element(); u -2*sqrt2 - 1 sage: %timeit res = cmp(t,u) 625 loops, best of 3: 807 µs per loop
Without the patch:
sage: K.<sqrt2> = QuadraticField(2) sage: t = -2*sqrt2 - 35 sage: u = K(-1) sage: %timeit res = cmp(t,u) 625 loops, best of 3: 419 ns per loop sage: u = -2*sqrt2 - 1 sage: %timeit res = cmp(t,u) 625 loops, best of 3: 419 ns per loop
So there is a significant slow down.
There are two failing doctests I need help with:
sage -t devel/sage/sage/schemes/elliptic_curves/ell_curve_isogeny.py ********************************************************************** File "/home/burcin/sage/sage-5.0.prealpha0/devel/sage-main/sage/schemes/elliptic_curves/ell_curve_isogeny.py", line 4361: sage: _[0].rational_maps() Expected: (((-4/25*i - 3/25)*x^5 + (-4/5*i + 2/5)*x^3 + x)/(x^4 + (-4/5*i + 2/5)*x^2 + (-4/25*i - 3/25)), ((2/125*i - 11/125)*x^6*y + (64/125*i + 23/125)*x^4*y + (162/125*i - 141/125)*x^2*y + (-4/25*i - 3/25)*y)/(x^6 + (-6/5*i + 3/5)*x^4 + (-12/25*i - 9/25)*x^2 + (2/125*i - 11/125))) Got: (((4/25*i + 3/25)*x^5 + (4/5*i - 2/5)*x^3 - x)/(x^4 + (-4/5*i + 2/5)*x^2 + (-4/25*i - 3/25)), ((11/125*i + 2/125)*x^6*y + (-23/125*i + 64/125)*x^4*y + (141/125*i + 162/125)*x^2*y + (3/25*i - 4/25)*y)/(x^6 + (-6/5*i + 3/5)*x^4 + (-12/25*i - 9/25)*x^2 + (2/125*i - 11/125))) ********************************************************************** File "/home/burcin/sage/sage-5.0.prealpha0/devel/sage-main/sage/schemes/elliptic_curves/ell_curve_isogeny.py", line 4622: sage: isogenies_13_0(E)[0].rational_maps() Expected: (((-4/169*r - 11/169)*x^13 + (-128/13*r - 456/13)*x^10 + (-1224/13*r - 2664/13)*x^7 + (-2208/13*r + 5472/13)*x^4 + (1152/13*r - 8064/13)*x)/(x^12 + (4*r - 36)*x^9 + (-1080/13*r + 3816/13)*x^6 + (2112/13*r + 5184/13)*x^3 + (17280/169*r - 1152/169)), ((18/2197*r - 35/2197)*x^18*y + (-23142/2197*r + 35478/2197)*x^15*y + (-1127520/2197*r + 1559664/2197)*x^12*y + (87744/2197*r + 5992704/2197)*x^9*y + (-6625152/2197*r + 9085824/2197)*x^6*y + (28919808/2197*r - 2239488/2197)*x^3*y + (-1990656/2197*r + 3870720/2197)*y)/(x^18 + (6*r - 54)*x^15 + (-3024/13*r + 11808/13)*x^12 + (31296/13*r - 51840/13)*x^9 + (-487296/169*r - 2070144/169)*x^6 + (-940032/169*r - 248832/169)*x^3 + (-1990656/2197*r + 3870720/2197))) Got: (((7/338*r + 23/338)*x^13 + (-164/13*r - 420/13)*x^10 + (720/13*r + 3168/13)*x^7 + (3840/13*r - 576/13)*x^4 + (4608/13*r + 2304/13)*x)/(x^12 + (4*r + 36)*x^9 + (1080/13*r + 3816/13)*x^6 + (2112/13*r - 5184/13)*x^3 + (-17280/169*r - 1152/169)), ((18/2197*r + 35/2197)*x^18*y + (23142/2197*r + 35478/2197)*x^15*y + (-1127520/2197*r - 1559664/2197)*x^12*y + (-87744/2197*r + 5992704/2197)*x^9*y + (-6625152/2197*r - 9085824/2197)*x^6*y + (-28919808/2197*r - 2239488/2197)*x^3*y + (-1990656/2197*r - 3870720/2197)*y)/(x^18 + (6*r + 54)*x^15 + (3024/13*r + 11808/13)*x^12 + (31296/13*r + 51840/13)*x^9 + (487296/169*r - 2070144/169)*x^6 + (-940032/169*r + 248832/169)*x^3 + (1990656/2197*r + 3870720/2197)))
comment:13 Changed 8 years ago by
- Status changed from needs_review to needs_work
- Work issues set to needs rebase
This patch doesn't apply to 5.0.beta11 -- see patchbot logs.
comment:14 Changed 8 years ago by
I rebased the patch to beta11.
comment:15 Changed 8 years ago by
- Status changed from needs_work to needs_review
- Work issues needs rebase deleted
This applies cleanly on beta13, I believe it needs review again?
comment:16 Changed 8 years ago by
comment:17 Changed 8 years ago by
- Status changed from needs_review to needs_work
- Work issues set to doctest failures
comment:18 follow-up: ↓ 20 Changed 7 years ago by
Hi,
I made a sort of duplicate with #13213. My aim was to use the natural order of RR in the case of real embedding. For quadratic field it is quite easy and fast. In the same patch, I aim to implement other functions related to the real embedding (is_positive, floor, ceil, abs, ...).
On the other hand, the difference of timings with my patch have an order of magnitude of x10 and not of x1000.
Should I close my ticket ? What to do with my patch ?
comment:19 Changed 7 years ago by
- Cc vdelecroix added
comment:20 in reply to: ↑ 18 Changed 7 years ago by
Hi Vincent,
thanks a lot for taking a look at this long standing problem.
Replying to vdelecroix:
I made a sort of duplicate with #13213. My aim was to use the natural order of RR in the case of real embedding. For quadratic field it is quite easy and fast. In the same patch, I aim to implement other functions related to the real embedding (is_positive, floor, ceil, abs, ...).
Fixing the comparison of quadratic number fields elements and implementing floor
, ceil
, etc. should be in separate patches.
On the other hand, the difference of timings with my patch have an order of magnitude of x10 and not of x1000.
Should I close my ticket ? What to do with my patch ?
Since your patch performs much better, we can move ahead using that. I will try to review your patch on #13213.
Once the patches in this ticket are rebased on your patch, we can close this as a duplicate.
comment:21 follow-up: ↓ 22 Changed 7 years ago by
Now #13213 is in positive review (and performances much better than what I expected at the begining)! Should we add a doctest related to the example in the description of the ticket or do we simply close it as a duplicate ?
comment:22 in reply to: ↑ 21 Changed 7 years ago by
Now #13213 is in positive review (and performances much better than what I expected at the begining)! Should we add a doctest related to the example in the description of the ticket or do we simply close it as a duplicate ?
If there are nearly identical examples to these in #13213, then I think that's okay; if there is nothing like this there, we should add a trivial patch. to check it's improved. I'm not going to look through that whole patch to find ones like this but presumably you know whether there is one like that, as the author :)
Changed 7 years ago by
comment:23 Changed 7 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
There are no example which deals with the symbolic ring... that's why I suggested to add some doctest here. See the proposition in the patch. Nevertheless, I found stupid the following behavior (or at least confusing)
sage: I**2 == -1 -1 == -1 sage: (I+4)**4 > 0 -4 > 0
apply trac_7160-doctest.patch
comment:24 Changed 7 years ago by
- Dependencies set to #13213
comment:25 Changed 7 years ago by
- Summary changed from comparison with quadratic number field elements needs work to comparison with quadratic number field elements
Now #13213 is positive review. I guess we may close that ticket ?
comment:26 Changed 7 years ago by
- Description modified (diff)
- Reviewers set to Burcin Erocal
- Status changed from needs_review to positive_review
I attached a new patch which fixes the commit message and missing :
before the trac link in the documentation. This is good to go.
Thanks!
comment:27 Changed 7 years ago by
- Milestone changed from sage-5.10 to sage-5.11
- Work issues doctest failures deleted
comment:28 Changed 7 years ago by
- Merged in set to sage-5.11.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
This is basically the same as #6132.