Meta-ticket: Towards a genuine RealField

[rws]

One Ring to rule them all.

This task ticket aims at discussing and reorganizing the ways to implement an abstraction of the field of real numbers (resp. complex numbers), as well as its interaction with its representations (algebraic, numerical, symbolic, ...).

The current approximative representations of real numbers (see also #15944) are

• RealDoubleField() (RDF) using double / ComplexDoubleField() (CDF)
• RealField(prec) (RR) using mpfr_t / ComplexField(prec) (CC)
• MPComplexField(prec) using mpc_t
• RealIntervalField(prec) (RIF) using mpfi_t / ComplexIntervalField(prec) (CIF)
• RealBallField(prec) (RBF) using arb_t / ComplexBallField(prec) (CBF) using acb_t

And the exact or symbolic ones

• RationalField() (QQ) using mpq_t
• AlgebraicRealField() (AA) / AlgebraicField() (QQbar)
• NumberField(poly) and QuadraticField(n)
• SymbolicRing() (SR) - mostly unreliable concering comparison, equality, etc

See also the discussion in #14567.

---

Concrete tickets

Cleaning real/complex floating-point

• #24483: complex numbers step 1
• #24489: complex numbers step 2
• #24457: real numbers

Documentation, tutorials

• #15944: real number and computers

Creation of abstract classes and categories

• #24456: sage.rings.real_field.RealField and sage.rings.complex_field.ComplexField
• #31199 Add Numerical and Exact Fields as Category

Concrete classes

• #26042: Real transcendental extension fields

[mmezzarobba]

Thierry, could you elaborate on what you have in mind? It is not clear to me from the comments on the other ticket.

[tmonteil]

Replying to mmezzarobba:

Thierry, could you elaborate on what you have in mind? It is not clear to me from the comments on the other ticket.

I had more to review on #14567 but it had to be merged at some point (my previous review was already big).

What i have in mind about the quoted sentence is related to what was discussed at ​https://groups.google.com/forum/#!msg/sage-devel/0vAo1AnPVOU/ZAg2U2dKeioJ ​http://thread.gmane.org/gmane.comp.mathematics.sage.devel/70858

More precisely (this is only an early draft):

• Deprecate CFF (Continued Fraction Field) because it is only a representation overlay over QQ (all computations are done in QQ, only the representation changes), so i am in favor to either remove CFF since QQ has now a .continued_fraction() method which does the same job, or add a .repr_as_cf flag in QQ to change the representation of rationals and see them as (finite) continued fractions (this can be useful if we want to see continued fractions along a computation involving rationals, so that we do not have to call the .continued_fraction() each time).

• Put RR at the same naming level than the other approximations of the real field (RDF, RIF, RBF (#17194), RLF,...), i.e. rename it RFF ("Real Floating Field"). Currently, claiming that this is the right default approximation causes a lot of misunderstandings (both on the user and the devel side). An improved version of this item could be to even replace the word "Field" by "Numbers" (RDN, RIN, RBN, RLN, RFN, ...) or "Approximation" (RDA, RIA, RBA, RLA, RFA, ...).

• Create a RSF ("Real Symbolic Field") of symbolic expressions representing real numbers. Indeed, those are currently part of SR which is an attracting dead end for coercion, so that currently pi+0.1 is symbolic while it should be numeric (loss of precision). An advantage is that RSF will be as high as AA in the coercion hierarchy and RSF will be an exact field. So:

  pi + log(2) in RSF
  pi + log(2) + 0.1 in RFF
  pi + log(2) + 0.1 + cos(x) in SR (dead end)
  

• Now, since the name RR is freed, we can let it represent the genuine real field, as NN, ZZ, QQ, AA correspond to genuine rings (not approximations), the new RR can be temporarly named GRR for deprecation time if needed ("Genuine Real Field"). So, we will have an object to serve as an abstraction of the field of real numbers, in particular, it could host methods for telling whether an element is a real number, whether a parent is an approximation of the real field (RDF, RIF, RLF,...). There will be a semantic difference with the R*F approximations, for example on could make the distinction between .is_field() and `.is_approximate_field() (+ update category framework accordingly), RR is a field, RDF is almost a field, so that we both have the mathematical information, and the computational one (you have the right to use this faster algorithm because you can divide)).

But this abstract field could also work as an overlay over the existing representations, and therefore be the parent of some elements.

The name "overlay" could be understood as follows (this preliminary proposal should of course be collectively improved): by default, an element of RR (the genuine real field) is stored as the set of the maximal elements (for the coercion) of its available representatives.

For example:

• a = sqrt(2) + sqrt(3) is stored as its representations in both AA and RSF.
• a + log(2) is stored as its representation in RSF.
• if b is an algebraic number of high degree which does not admit a representation by radicals, then a + b is stored as its representaion in AA.
• a + b + log(2) is stored as its representaion in RLF.
• a + b + log(2) + RR(RIF(0.1)) is stored as its representaion in RIF.
• a + RR(RDF(0.1)) is stored as its representaion in RDF.

A coercion between RR and a particular representation falls into some representation (RR is not absorbing (while SR is)):

• a + RIF(2) belongs to RIF
• log(RR(2)) + AA(2) belongs to RR

So, in the coercion DAG, RR is below QQ and AA, but above all the R*F.

Along a computation, the set of representatives can grow, for example, if we do some numerical computations involving a, a can also cache some of its numerical reprentations to ease further computations.

A possibility could be to have a ._tight flag in RR to use more information than the raw coercion described above. For example, the coercion between AA and RIF falls into RIF, but one could ask RR to consider that RR(sqrt(2)) + RR(RIF(2)) keeps a representative in AA since both endpoints of RIF(2) are equal (so we are guaranteed that this is the integer 2). In R*F, this does not make sense since we want the coercion to work independently of the elements (it is decided at the parent level), but within RR, we could want to lose as few information as possible (why not, we are within a single parent). Also, with _tight flag on, a = RR(pi/5) is represented as RSF, but cos(a) is represented as RSF and AA. I guess the default should be the one provided by coercion of representatives (less powerful, but faster and easier to predict).

RR could have a ._repr flag, where we could have symbolic representation, scientific notation, continued fractions,... the .__repr__() method of RR elements could use colors to indicate how exact/secure is its current representation (there is a difference between RR(sqrt(2)) (exact), RR(RIF(0.1)) (inexact but secure) and RR(RDF(0.1))) (inexact and insecure).

Of course, all this should be extended to complex numbers as well (though we will encounter problems with CSF since SR currently lacks semantics about ramifications (e.g. cube roots or logs) while we have to ensure reliability with that respect since CSF is pretty high in the coercion hierarchy).

As positive effects:

• Necommers will stop using RFF (currently named RR) by default, while it is both inexact and much slower than RDF. They will understand the difference between a real number and its possible representatives (symbolic, algebraic, numeric).

• There will not be meaningless discussions on sage-devel on whether NaN or Infinity should belong to RFF (no one complained for RDF, the problem comes from the fact that people expect the current RR to be the genuine real field, while it is only one of its approximation).

• This will host all methods related to the mathematical notion of real numbers, independently of its reprentation, for example:
  • given a Sage object, you can ask whether it is real by typing:

    sage: 0.2 in RR
    True
    sage: pi in RR
    True
    sage: infinity in RR
    False
    sage: NaN in RR
    False
    

  • we make the distinction between mathematical aspect and computational one:

    sage: RR.is_field()
    True
    sage: RDF.is_field()
    False
    sage: RDF.is_field_approximation()
    True
    sage: %timeit det(random_matrix(RDF,100))
    2 ns (i used the fast algorithm because i could divide)
    sage: RR.cardinality()
    +Infinity                 # or 2^aleph_0 if defined
    sage: RDF.cardinality()
    18446744073709551615      # or some correct number
    

  • this is a good place to host the method answering "Checking whether a Parent models the real field", see : ​https://groups.google.com/forum/#!topic/sage-devel/m822J7mYA0Q ​http://thread.gmane.org/gmane.comp.mathematics.sage.devel/76733

    sage: RR.is_modeled_by(RLF)
    True
    sage: RR.is_modeled_by(CDF)
    False
    sagel RR.is_modeled_by(GF(2))
    False
    

  • perhaps RR could ease the preparsing issue about user inputs that are context dependent such as '0.1' or '1e-20' to defer the choice of a representation until it is coerced as discussed on sage-devel (i have no opinion on that subject though, since i do not use real litterals much).

​http://article.gmane.org/gmane.comp.mathematics.sage.devel/101/match=real+literals ​http://article.gmane.org/gmane.comp.mathematics.sage.devel/3427/match=real+literals ​http://article.gmane.org/gmane.comp.mathematics.sage.devel/12326/match=real+literals ​http://article.gmane.org/gmane.comp.mathematics.sage.devel/13839/match=real+literals ​http://article.gmane.org/gmane.comp.mathematics.sage.devel/16578/match=real+literals ​http://article.gmane.org/gmane.comp.mathematics.sage.devel/62514/match=real+literals ​http://thread.gmane.org/gmane.comp.mathematics.sage.devel/69699/match=real+literals

sage: 0.1 + 1/3
13/30
sage: 0.1 + RDF(0.1)
0.200000000000000
sage: 0.1 + RealFloatingField(1000)(0.1)
0.200000000000000000000000000000000000000000...

For dealing with infinities, we could add (mathematical) one-point (resp two-points) compactification RRhat (resp. RRbar), CChat (Riemann sphere), which have more mathematical meaning than the InfinityRing, that currently behaves as follows:

sage: 2 in InfinityRing
True
sage: pi in InfinityRing
False
sage: InfinityRing(NaN) == InfinityRing(-1)
True

While we are at it, i would like to work on a well defined conversion from AA to RSF using Galois theory, which seems to be on the road now, see #17516.

Once all this is done, we could imagine to also create a RCF ("Real Constructive Field") of numbers that can be approximated with a Turing machine to arbitrary good precision (it would be created by an iterator or a function that, given a precision returns a rational within the interval).

Remark: note that under the hood, RLF seems to also have a kind of overlay mechanism, but it is not very handy, nor transparent to the user, nor mathematically meaningful. Also, it is not able to store more than one representative, while RSF and AA are not comparable in the hierarchy of coercion.

sage: a = RLF(pi+cos(2))
sage: b = RLF(AA(sqrt(2)))
sage: a._value.parent()
Symbolic Ring
sage: b._value.parent()
Algebraic Real Field
sage: c = a+b
sage: c._value
AttributeError
sage: c._op
<built-in function add>
sage: a._op
AttributeError
sage: r = RLF(2)
sage: s = r.sqrt()
sage: s._value
AttributeError
sage: s._op
'sqrt'

[mmezzarobba]

Thanks for your explanations! Just some quick comments and questions (I don't think I will have time to think about all that in detail soon).

• I still don't really understand the difference you are envisioninig between RLF and your GRR. Why not just improve RLF? Also, what would be the benefits of storing multiple representatives of a real number? Same question with RCF.
• I also don't see what this all has to do with continued fractions.
• As far as I understand the intention of SR (well, not all of SR, but things like elementary and special functions, limits, etc.) is to sort-of-model complex variable calculus, and the problems with branch cuts of analytic functions are bugs.
• There seems to be a weak consensus that an algebraic structure name ”Foo“ in Sage (esp. in parent and category names) means ”Effective Foo”. None of your real fields (even the exact ones) are ”Fields“ in this sense, since the zero test is undecidable.
• Regarding names, I think I like FPR (or RFP) for floating-point numbers and IR for intervals better than what you suggest.
• Using in RR to test if something ”is real“ still wouldn't be a good idea in many cases, since there certainly would still be parents with some ”real“ elements that wouldn't coerce into RR.
• The problem with InfinityRing(NaN) could simply be solved by adding a NaN element to InfinityRing. This makes sense with the current model. Defining a compactification mechanism may also be a good idea, but then I guess compactifications should be generic constructions that take any suitable parent and extend it with one or two points at infinity. In other words, I doubt we need an RRbar, just a TwoPointCompactification(RR) and a corresponding functor that the coercion system could apply to decide that the universe of [RR(1), -infinity] is TwoPointCompactification(RR).

[tmonteil]

Replying to mmezzarobba:

• I still don't really understand the difference you are envisioninig between RLF and your GRR. Why not just improve RLF?

Mainly because there are some non-lazy representations of real numbers. Here "lazy" is related to a representation of real numbers as iterators, and the current implementation deals about that facet, i do not see the point in thinking of the real number 1/3 as 0.3333333... by default. I have nothing against improving RLF though, but i think we have to give a separate name to an abstraction of the genuine real field as a mathematical object (that could also carry some categorial information, the fact that is indeed a field, and so on), if only to make the notion of representation clear.

Also, what would be the benefits of storing multiple representatives of a real number?

I am not sure about this point, this is only a proposal! Somehow, the existing repesentations of real numbers do not form a linear order for the coercion, so when a real number can be reresented in two such representations, there is a loss to choose one of them or to use the common parent. Probably only practice would decide whether this is a good idea, this should be experimented.

Same question with RCF.

The field of effective numbers is well defined, i am not specialist, but there are both some theoretical results about this and even some implementations, so, if someone feel to put this in Sage, i do not see the problem. Actually, i write say RRF for "real recursive field".

• I also don't see what this all has to do with continued fractions.

As for me, nothing. I did not chose the title of this ticket, but i guess this is because some discussion happen in a continued fraction ticket.

• As far as I understand the intention of SR (well, not all of SR, but things like elementary and special functions, limits, etc.) is to sort-of-model complex variable calculus, and the problems with branch cuts of analytic functions are bugs.

Indeed! Unfortunately numbers like sqrt(pi) belong to this big object, and are interesting as real numbers. The idea is to extract such variable-free expressions to a smaller class of "real symbolic numbers" (with trivial inclusion in both GRR and SR).

Condidering branch problems as bugs (i agree!) does not provide an estimate on the time to fix them, especially since we rely on external libraries for this.

• There seems to be a weak consensus that an algebraic structure name ”Foo“ in Sage (esp. in parent and category names) means ”Effective Foo”. None of your real fields (even the exact ones) are ”Fields“ in this sense, since the zero test is undecidable.

Indeed. I agree that such property should be made explicit in each representation (similar to is_exact). However, as long as some not effective (in your sense) representations are useful, i do not see the point not to consider them.

• Regarding names, I think I like FPR (or RFP) for floating-point numbers and IR for intervals better than what you suggest.

I agree with that (i wrote "An improved version of this item could be to even replace the word "Field" by "Numbers" (RDN, RIN, RBN, RLN, RFN, ...) or "Approximation" (RDA, RIA, RBA, RLA, RFA, ...)."). Changing only RR to RFF was a less disruptive proposal, i am not sure until which point we can reach a consensus (i am not even convinced that there will eventually be a consensus to rename RR to be consistent with its actual nature).

• Using in RR to test if something ”is real“ still wouldn't be a good idea in many cases, since there certainly would still be parents with some ”real“ elements that wouldn't coerce into RR.

This is one reason to isolate RSF from SR, because the coercion order will be RSF > RR > SR.

• The problem with InfinityRing(NaN) could simply be solved by adding a NaN element to InfinityRing. This makes sense with the current model. Defining a compactification mechanism may also be a good idea, but then I guess compactifications should be generic constructions that take any suitable parent and extend it with one or two points at infinity.

Yes.

In other words, I doubt we need an RRbar, just a TwoPointCompactification(RR) and a corresponding functor that the coercion system could apply to decide that the universe of [RR(1), -infinity] is TwoPointCompactification(RR).

Well, this is nothing but a shortcut, as well as RDF is a shortcut of RealDoubleField(). I have no strong opinion on whether it should be included into the namespace.