Opened 13 months ago

Closed 9 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 12 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

New commits:

446d89afloor() and ceil() for real algebraic numbers

comment:2 Changed 12 months ago by git

  • Commit changed from 446d89a1222118319c871723814c7c5272b93d99 to 1c2c1ffd8e4b0a9848f02f83b5a0b12fe478b243

Branch pushed to git repo; I updated commit sha1. New commits:

1c2c1ffAdd regression test.

comment:3 Changed 12 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 12 months ago by mmezzarobba

  • Authors set to Marc Mezzarobba

comment:5 Changed 12 months ago by git

  • Commit changed from 1c2c1ffd8e4b0a9848f02f83b5a0b12fe478b243 to a07f1e7ac809a6377476ff79c35225757eb7ee8d

Branch pushed to git repo; I updated commit sha1. New commits:

a07f1e7round() and trunc() for real algebraic numbers
13a5186trunc() for rational numbers

comment:6 Changed 12 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 11 months ago by git

  • Commit changed from a07f1e7ac809a6377476ff79c35225757eb7ee8d to 2ce91a2450a2b5389be07acf1ec8eb748a8b7bd7

Branch pushed to git repo; I updated commit sha1. New commits:

2ce91a2trunc() in AA: make default prec consistent with that used by !=

comment:8 Changed 11 months ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:9 follow-up: Changed 9 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 9 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 9 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.

Last edited 9 months ago by ppurka (previous) (diff)

comment:12 Changed 9 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:

f4887cdMerge branch 'u/mmezzarobba/ticket/15501-AA_floor_ceil' of trac.sagemath.org:sage into u/tscrim/ticket/AA_floor_ceil-15501
4bf8750Some minor review tweaks.

comment:13 Changed 9 months ago by mmezzarobba

  • Status changed from needs_review to positive_review

comment:14 Changed 9 months ago by mmezzarobba

  • Authors changed from Marc Mezzarobba to Marc Mezzarobba, Travis Scrimshaw
  • Reviewers set to Martin von Gagern, Travis Scrimshaw, Marc Mezzarobba

comment:15 Changed 9 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
Note: See TracTickets for help on using tickets.