Opened 4 years ago
Closed 3 years ago
#15501 closed defect (fixed)
floor(), ceil(), trunc(), round() for AA
Reported by:  ppurka  Owned by:  

Priority:  major  Milestone:  sage6.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 )
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 (bb)
is not printed as 0, but something like 0.?e18
. Usually it is not a big problem, because b  b == 0
evaluates to True
. But interestingly floor(bb)
is sometimes 0, sometimes a symbolic expression, so weird things can happen.
sage: a = QQbar((1)^(1/4)).real() sage: floor(aa) + a  TypeError Traceback (most recent call last) <ipythoninput337107a1ad8256f> in <module>() > 1 floor(aa) + a /Applications/sage/local/lib/python2.7/sitepackages/sage/structure/element.so in sage.structure.element.RingElement.__add__ (sage/structure/element.c:13884)() /Applications/sage/local/lib/python2.7/sitepackages/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 4 years ago by
 Branch set to u/mmezzarobba/ticket/15501AA_floor_ceil
 Commit set to 446d89a1222118319c871723814c7c5272b93d99
 Status changed from new to needs_review
comment:2 Changed 4 years ago by
 Commit changed from 446d89a1222118319c871723814c7c5272b93d99 to 1c2c1ffd8e4b0a9848f02f83b5a0b12fe478b243
Branch pushed to git repo; I updated commit sha1. New commits:
1c2c1ff  Add regression test.

comment:3 Changed 4 years ago by
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 4 years ago by
comment:5 Changed 4 years ago by
 Commit changed from 1c2c1ffd8e4b0a9848f02f83b5a0b12fe478b243 to a07f1e7ac809a6377476ff79c35225757eb7ee8d
comment:6 Changed 4 years ago by
 Description modified (diff)
 Summary changed from AA should have .floor() method to floor(), ceil(), trunc(), round() for AA
comment:7 Changed 4 years ago by
 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 4 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:9 followup: ↓ 11 Changed 4 years ago by
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 4 years ago by
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 halfinteger 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 4 years ago by
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 3 years ago by
 Branch changed from u/mmezzarobba/ticket/15501AA_floor_ceil to u/tscrim/ticket/AA_floor_ceil15501
 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/15501AA_floor_ceil' of trac.sagemath.org:sage into u/tscrim/ticket/AA_floor_ceil15501

4bf8750  Some minor review tweaks.

comment:13 Changed 3 years ago by
 Status changed from needs_review to positive_review
comment:14 Changed 3 years ago by
 Reviewers set to Martin von Gagern, Travis Scrimshaw, Marc Mezzarobba
comment:15 Changed 3 years ago by
 Branch changed from u/tscrim/ticket/AA_floor_ceil15501 to 4bf87507e9f2e6f38f2ccb26ba5c6a5496be40f6
 Resolution set to fixed
 Status changed from positive_review to closed
New commits: