#17713: implement GoodRealField with help of continued fractions
---------------------------------+-----------------------------
Reporter: rws | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-wishlist
Component: number fields | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
---------------------------------+-----------------------------
Comment (by tmonteil):
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'
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/17713#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
