floor(), ceil(), trunc(), round() for AA

[ppurka]

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'

Component: algebra

Author: Marc Mezzarobba, Travis Scrimshaw

Branch/Commit: 4bf8750

Reviewer: Martin von Gagern, Travis Scrimshaw, Marc Mezzarobba

Issue created by migration from https://trac.sagemath.org/ticket/15501

[mezzarobba]

Commit: 446d89a

[mezzarobba]

Branch: u/mmezzarobba/ticket/15501-AA_floor_ceil

[mezzarobba]

New commits:

[446d89a](https://github.com/sagemath/sagetrac-mirror/commit/446d89a)

floor() and ceil() for real algebraic numbers

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1c2c1ff

Add regression test.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 446d89a to 1c2c1ff

[ppurka]

comment:3

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.

[mezzarobba]

Author: Marc Mezzarobba

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a07f1e7	round() and trunc() for real algebraic numbers
13a5186	trunc() for rational numbers

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1c2c1ff to a07f1e7

[mezzarobba]

Description changed:

--- 
+++ 
@@ -1,3 +1,7 @@
+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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

2ce91a2

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a07f1e7 to 2ce91a2

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

comment:9

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.

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

comment:10

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.

[ppurka]

comment:11

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.

[tscrim]

comment:12

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.

[tscrim]

Changed commit from 2ce91a2 to 4bf8750

[tscrim]

Changed branch from u/mmezzarobba/ticket/15501-AA_floor_ceil to u/tscrim/ticket/AA_floor_ceil-15501

[mezzarobba]

Changed author from Marc Mezzarobba to Marc Mezzarobba, Travis Scrimshaw

[mezzarobba]

Reviewer: Martin von Gagern, Travis Scrimshaw, Marc Mezzarobba

[vbraun]

Changed branch from u/tscrim/ticket/AA_floor_ceil-15501 to 4bf8750