Opened 20 months ago
Closed 16 months ago
#15501 closed defect (fixed)
floor(), ceil(), trunc(), round() for AA
Reported by: | ppurka | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.2 |
Component: | algebra | Keywords: | |
Cc: | Merged in: | ||
Authors: | Marc Mezzarobba, Travis Scrimshaw | Reviewers: | Martin von Gagern, Travis Scrimshaw, Marc Mezzarobba |
Report Upstream: | N/A | Work issues: | |
Branch: | 4bf8750 (Commits) | Commit: | 4bf87507e9f2e6f38f2ccb26ba5c6a5496be40f6 |
Dependencies: | Stopgaps: |
Description (last modified by mmezzarobba)
Add methods floor(), ceil(), trunc(), and round() to the implementation of real algebraic numbers. Also implement trunc() for rational numbers, both for consistency and to be able to use it in the code for algebraic numbers.
ORIGINAL BUG DESCRIPTION:
From google spreadsheet which no one reads X-(
It happens that an algebraic number minus itself (b-b) is not printed as 0, but something like 0.?e-18. Usually it is not a big problem, because b - b == 0 evaluates to True. But interestingly floor(b-b) is sometimes 0, sometimes a symbolic expression, so weird things can happen.
sage: a = QQbar((-1)^(1/4)).real() sage: floor(a-a) + a --------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-337-107a1ad8256f> in <module>() ----> 1 floor(a-a) + a /Applications/sage/local/lib/python2.7/site-packages/sage/structure/element.so in sage.structure.element.RingElement.__add__ (sage/structure/element.c:13884)() /Applications/sage/local/lib/python2.7/site-packages/sage/structure/coerce.so in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:8169)() TypeError: unsupported operand parent(s) for '+': 'Symbolic Ring' and 'Algebraic Real Field'
Change History (15)
comment:1 Changed 20 months ago by mmezzarobba
- Branch set to u/mmezzarobba/ticket/15501-AA_floor_ceil
- Commit set to 446d89a1222118319c871723814c7c5272b93d99
- Status changed from new to needs_review
comment:2 Changed 20 months ago by git
- Commit changed from 446d89a1222118319c871723814c7c5272b93d99 to 1c2c1ffd8e4b0a9848f02f83b5a0b12fe478b243
Branch pushed to git repo; I updated commit sha1. New commits:
1c2c1ff | Add regression test. |
comment:3 Changed 20 months ago by ppurka
I am not really familiar with the implementation or concepts involved in the Algebraic Reals. Anyone familiar with the concepts is free to review this ticket (efficiency of implementation, etc).
I can confirm, however, that the patch works very well.
comment:4 Changed 20 months ago by mmezzarobba
comment:5 Changed 19 months ago by git
- Commit changed from 1c2c1ffd8e4b0a9848f02f83b5a0b12fe478b243 to a07f1e7ac809a6377476ff79c35225757eb7ee8d
comment:6 Changed 19 months ago by mmezzarobba
- Description modified (diff)
- Summary changed from AA should have .floor() method to floor(), ceil(), trunc(), round() for AA
comment:7 Changed 19 months ago by git
- Commit changed from a07f1e7ac809a6377476ff79c35225757eb7ee8d to 2ce91a2450a2b5389be07acf1ec8eb748a8b7bd7
Branch pushed to git repo; I updated commit sha1. New commits:
2ce91a2 | trunc() in AA: make default prec consistent with that used by != |
comment:8 Changed 18 months ago by vbraun_spam
- Milestone changed from sage-6.1 to sage-6.2
comment:9 follow-up: ↓ 11 Changed 16 months ago by gagern
Had a look at the code, not sure whether I'd officially call this a review. The diff here on trac looks broken, but after merging develop my local changes look fine. The general approach looks sound. I wonder whether we should support different rounding modes, the way rational numbers do. But one can always add that in a later commit. Since rounding mode is only an issue for actual rational numbers, this should be easy to implement outside the candidate finding method.
I also wonder whether always calling more_precision is the right thing to do. I fear there might be situations where this could lead to an infinite loop, although I don't claim to understand all the details. Nevertheless, perhaps at some point we should stop iterating and do bisection on the candidate range. That is, actually compare given integers against the algebraic number. As far as I understand it, comparison can be done exactly in finite (although possibly long) time. Since I have no clue as to when switching to that approach would be appropriate, I wonder whether interleaving things might make sense: keep low and high integer candidate bounds, and in each iteration, see whether added precision can narrow these bounds, but also use the middle of the range to bisect it. Sooner or later, one of these methods should succeed in narrowing the candidate range down to one element. I guess doing this approach would mean passing a second function to _floor_ceil which does the appropriate comparison.
comment:10 Changed 16 months ago by gagern
I guess I should have thought two more minutes before pressing Submit. Since you do call _rational_ early in the loop, you can be sure that you either detect critical integer or half-integer values, or there is some finite difference between the value of self and the nearest critical distance, so a finite number of added precision steps will be enough to make the decision. Now things look pretty good to me.
comment:11 in reply to: ↑ 9 Changed 16 months ago by ppurka
Replying to gagern:
Had a look at the code, not sure whether I'd officially call this a review.
If you are referring to my statement in comment:3, then let me clarify that I definitely did not review this ticket. The patch looked good to me and it worked well for me. But I am unfamiliar with the AA code, so I did not perform a full review.
If the patch looks ok to you, then please feel free to set it to positive review.
comment:12 Changed 16 months ago by tscrim
- Branch changed from u/mmezzarobba/ticket/15501-AA_floor_ceil to u/tscrim/ticket/AA_floor_ceil-15501
- Commit changed from 2ce91a2450a2b5389be07acf1ec8eb748a8b7bd7 to 4bf87507e9f2e6f38f2ccb26ba5c6a5496be40f6
I made a couple of review changes/fixes. So if people are happy with my changes, then we can set this to a positive review.
New commits:
f4887cd | Merge branch 'u/mmezzarobba/ticket/15501-AA_floor_ceil' of trac.sagemath.org:sage into u/tscrim/ticket/AA_floor_ceil-15501 |
4bf8750 | Some minor review tweaks. |
comment:13 Changed 16 months ago by mmezzarobba
- Status changed from needs_review to positive_review
comment:14 Changed 16 months ago by mmezzarobba
- Reviewers set to Martin von Gagern, Travis Scrimshaw, Marc Mezzarobba
comment:15 Changed 16 months ago by vbraun
- Branch changed from u/tscrim/ticket/AA_floor_ceil-15501 to 4bf87507e9f2e6f38f2ccb26ba5c6a5496be40f6
- Resolution set to fixed
- Status changed from positive_review to closed
New commits: