Meta-ticket: Towards a genuine RealField

[rwst]

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

• complex_field.py complex_number.pyx -> complex_mpfr.pyx #24483: complex numbers step 1
• modernize complex_mpfr #24489: complex numbers step 2
• modernize sage.rings.real_mpfr #24457: real numbers

Documentation, tutorials

• Thematic tutorial about real and complex numbers in Sage #15944: real number and computers

Creation of abstract classes and categories

• classes for the fields of complex and real numbers #24456: sage.rings.real_field.RealField and sage.rings.complex_field.ComplexField
• Add Numerical and Exact Fields as Category #31199 Add Numerical and Exact Fields as Category

Concrete classes

• Real transcendental extension fields #26042: Real transcendental extension fields

CC: @sagetrac-tmonteil @staroste @tscrim @videlec @jdemeyer @egourgoulhon @dimpase @yuan-zhou

Component: number fields

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

[mezzarobba]

comment:1

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

[sagetrac-tmonteil]

comment:3

Replying to @mezzarobba:

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 (Minimal bindings for optional arb package #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), RRis 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'

[mezzarobba]

comment:4

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).

[sagetrac-tmonteil]

comment:6

Replying to @mezzarobba:

• 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.