Opened 5 years ago
Last modified 2 years ago
#17713 new task
Towards a genuine RealField
Reported by: | rws | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-wishlist |
Component: | number fields | Keywords: | |
Cc: | tmonteil, sstarosta, tscrim, vdelecroix, jdemeyer, egourgoulhon | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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
) usingdouble
/ComplexDoubleField()
(CDF
)RealField(prec)
(RR
) usingmpfr_t
/ComplexField(prec)
(CC
)MPComplexField(prec)
usingmpc_t
RealIntervalField(prec)
(RIF
) usingmpfi_t
/ComplexIntervalField(prec)
(CIF
)RealBallField(prec)
(RBF
) usingarb_t
/ComplexBallField(prec)
(CBF
) usingacb_t
And the exact or symbolic ones
RationalField()
(QQ
) usingmpq_t
AlgebraicRealField()
(AA
) /AlgebraicField()
(QQbar
)NumberField(poly)
andQuadraticField(n)
SymbolicRing()
(SR
) - mostly unreliable concering comparison, equality, etc
See also the discussion in #14567.
Concrete tickets
Cleaning real/complex floating-point
Documentation, tutorials
- #15944: real number and computers
Creation of abstract classes
- #24456:
sage.rings.real_field.RealField
andsage.rings.complex_field.ComplexField
Change History (11)
comment:1 Changed 5 years ago by
comment:2 Changed 5 years ago by
- Milestone changed from sage-6.5 to sage-wishlist
comment:3 Changed 5 years ago by
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 overQQ
(all computations are done inQQ
, only the representation changes), so i am in favor to either removeCFF
sinceQQ
has now a.continued_fraction()
method which does the same job, or add a.repr_as_cf
flag inQQ
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 itRFF
("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 ofSR
which is an attracting dead end for coercion, so that currentlypi+0.1
is symbolic while it should be numeric (loss of precision). An advantage is thatRSF
will be as high asAA
in the coercion hierarchy andRSF
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, asNN
,ZZ
,QQ
,AA
correspond to genuine rings (not approximations), the newRR
can be temporarly namedGRR
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 theR*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 bothAA
andRSF
.a + log(2)
is stored as its representation inRSF
.- if
b
is an algebraic number of high degree which does not admit a representation by radicals, thena + b
is stored as its representaion inAA
. a + b + log(2)
is stored as its representaion in RLF.a + b + log(2) + RR(RIF(0.1))
is stored as its representaion inRIF
.a + RR(RDF(0.1))
is stored as its representaion inRDF
.
A coercion between RR
and a particular representation falls into some representation (RR
is not absorbing (while SR
is)):
a + RIF(2)
belongs toRIF
log(RR(2)) + AA(2)
belongs toRR
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 namedRR
) by default, while it is both inexact and much slower thanRDF
. 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
orInfinity
should belong toRFF
(no one complained forRDF
, the problem comes from the fact that people expect the currentRR
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).
- given a Sage object, you can ask whether it is real by typing:
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'
comment:4 follow-up: ↓ 6 Changed 5 years ago by
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 yourGRR
. Why not just improveRLF
? Also, what would be the benefits of storing multiple representatives of a real number? Same question withRCF
. - 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 ofSR
, 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
(orRFP
) for floating-point numbers andIR
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 intoRR
. - The problem with
InfinityRing(NaN)
could simply be solved by adding aNaN
element toInfinityRing
. 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 anRRbar
, just aTwoPointCompactification(RR)
and a corresponding functor that the coercion system could apply to decide that the universe of[RR(1), -infinity]
isTwoPointCompactification(RR)
.
comment:5 Changed 5 years ago by
- Cc sstarosta added
comment:6 in reply to: ↑ 4 Changed 4 years ago by
Replying to mmezzarobba:
- I still don't really understand the difference you are envisioninig between
RLF
and yourGRR
. Why not just improveRLF
?
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 ofSR
, 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
(orRFP
) for floating-point numbers andIR
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 intoRR
.
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 aNaN
element toInfinityRing
. 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 aTwoPointCompactification(RR)
and a corresponding functor that the coercion system could apply to decide that the universe of[RR(1), -infinity]
isTwoPointCompactification(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.
comment:7 Changed 2 years ago by
- Description modified (diff)
- Summary changed from implement GoodRealField with help of continued fractions to Towards a genuine RealField
- Type changed from enhancement to task
comment:8 Changed 2 years ago by
- Cc tscrim vdelecroix jdemeyer egourgoulhon added
comment:9 Changed 2 years ago by
- Description modified (diff)
comment:10 Changed 2 years ago by
- Description modified (diff)
comment:11 Changed 2 years ago by
- Description modified (diff)
Thierry, could you elaborate on what you have in mind? It is not clear to me from the comments on the other ticket.