#14567: Refactor continued fractions
-------------------------------------+-------------------------------------
Reporter: vdelecroix | Owner: vdelecroix
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.2
Component: number theory | Resolution:
Keywords: continued | Merged in:
fractions, numerical | Reviewers: Ralf Stephan, Thierry
approximation | Monteil
Authors: Vincent Delecroix | Work issues:
Report Upstream: N/A | Commit:
Branch: | fb96ac7c8eae9834e3513c2fbd9abd450faa58c0
u/rws/ticket/14567 | Stopgaps:
Dependencies: #13213, #13256, |
#14563 |
-------------------------------------+-------------------------------------
Changes (by tmonteil):
* reviewer: Ralf Stephan => Ralf Stephan, Thierry Monteil
Comment:
This review is not polished, but i provide it as is, so that we can
discuss. I also uploaded a (beginning of a) patch containing minor
modifications, even if this corresponds to the old workflow.
----
`CFF` is not fully autonomous and behaves like an overlay over other Sage
fields, thus sacrificing reliability over expressivity.
{{{
sage: a = CFF(0.1)
sage: a.value()
1/10
}}}
vs
{{{
sage: a = CFF(0.1+sqrt(2))
sage: a.value()
sqrt(2) + 0.100000000000000
}}}
Hence the mess:
{{{
sage: a = CFF(0.1+sqrt(2))
sage: b = CFF(0.1) + CFF(sqrt(2))
sage: a == b
True
}}}
but
{{{
sage: a
[1; 1, 1, 17, 11, 3, 1, 8, 2, 1, 2, 2, 281, 1, 10, 3, 2, 3, 21, 5, ...]
sage: b
[1; (1, 1, 17, 11, 3, 1, 8, 2, 1, 2, 2, 282, 2, 2, 1, 2, 8, 1, 3, 11, 17,
1, 1, 2, 3, 5, 2, 10, 1, 5, 1, 69, 1, 5, 1, 10, 2, 5, 3, 2)*]
}}}
I have not much problems with this overlay design as long as it is clearly
stated and consistent.
Note that this behaviour is not uniform, since `CFF(a).value()` is
sometimes not
equal to `a`, but this is not clear when.
{{{
- << Return the value of "self" (the number from which it was built). >>
- << Return the value of "self" as a quadratic number (with square free
discriminant). >>
}}}
This is not the role of `CFF` to canonicalize Sage real numbers, though
one
could imagine such a class/function `GoodRealField`.
{{{
sage: CFF(sqrt(2))
[1; (2)*]
sage: CFF(sqrt(2)).value()
sqrt2
sage: CFF(0.1)
[0; 10]
sage: CFF(0.1).value()
1/10
sage: CFF(pi)
[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, ...]
sage: CFF(pi).value()
pi
sage: (2^(1/3)).parent()
Symbolic Ring
sage: CFF(2^(1/3)).value().parent()
Algebraic Real Field
}}}
Another consequence of the overlay structure is that the inverse of a
continued fraction is not as expected (the inverse should only shift the
sequence of partial quotients):
{{{
sage: a = CFF(pi+0.1) ; a
[3; 4, 7, 5, 2, 3, 2, 1, 1, 1, 4, 1, 4, 33, 4, 2, 6, 10, 3, 1, ...]
sage: ~a
[0; 3, 4, 7, 5, 2, 3, 2, 1, 1, 1, 4, 1, 4, 33, 4, 4, 1, 1, 1, ...]
}}}
I do understand that this may be a transitional behaviour. But how to tell
that to sage users ?
I see two ways:
- be always an "overlay field"
- restrict the code to words (cf your issue 6) you really handle
(rationals
and quadratic irrationals, corresponding to finite and ultimately
periodic
words) ?
Perhaps a solution is to have two very distinct classes (with conversions)
?
-----
Another issue is:
{{{
sage: CFF.is_exact()
True
}}}
I disagree with that statement, since there are approximate elements in
CFF,
for example `CFF(pi+0.1)`.
-----
Problems with `SR`:
{{{
sage: sqrt(2) == QQbar(sqrt(2))
True
sage: CFF(sqrt(2)) == CFF(QQbar(sqrt(2)))
Wait for a long time...
sage: CFF(sqrt(2)).value().parent()
Number Field in sqrt2 with defining polynomial x^2 - 2
sage: CFF(sqrt(2)).value() == CFF(QQbar(sqrt(2))).value()
False
}}}
Transitivity of equality:
{{{
sage: bool(CFF(sqrt(2)).value() == sqrt(2))
True
sage: bool(sqrt(2)) == sqrt(QQbar(2))
True
sage: CFF(sqrt(2)).value() == sqrt(QQbar(2))
False
}}}
----
in `_element_constructor_()`
{{{
- ``nterms`` -- integer (optional)
??? is that an old remaining thing ?
- ``check`` -- boolean (optional) -- whether or not we check the
"the" what ?
}}}
----
When you test whether an element of `SR` is a real number, you use
`RIF(x)`.
Why not using `x.is_real()` (and make this method more reliable if needed)
?
----
Another problem:
{{{
sage: a = RDF(0.1)
sage: CFF(a)
[0]
}}}
The reason is :
{{{
sage: (1/RIF(RDF(0.1))).unique_floor()
ValueError: interval does not have a unique floor
}}}
----
In the doc: "It is quite remarkable that".
Add : "- any real number admits a unique continued fraction expansion"
----
"It is also possible to create a continued fraction from a list of
digits::"
I would propose : "from a list of numbers corresponding to its partial
quotients."
"For quadratic numbers, the syntax is quite similar and the digits are
represented as a pair of tuples, the preperiod and the period::"
Again, "digits" vs "partial quotients"
-----
Another problem:
{{{
sage: cf = CFF([(1,2,3),(1,2,4)]); cf.value()
-1/86*sqrt229 + 139/86
sage: sqrt229
....
NameError: name 'sqrt229' is not defined
}}}
`CFF` outputs an element of a quadratic field that can not be used
furthermore. Of course, one can get it back with `cf.parent().gen()`.
Perhaps
inject those variables ?
----
"two_last_convergents" -> "last_two_convergents"
----
`_pn` and `_qn` looks good for internal variables, but i would suggest to
replace `pn()` and `qn()` methods by `numerator()` and `denominator()` to
stay
consistent with rationals.
----
In the `_mpfr_` method: "It is guaranteed that the result is exact"
Floating point number are not exact, perhaps "accurate" is a better word ?
--
Ticket URL: <http://trac.sagemath.org/ticket/14567#comment:33>
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/groups/opt_out.
