continued_fraction oddity
Harald Schilly
http://spreadsheets.google.com/ver?key=pCwvGVwSMxTzT6E2xNdo5fA&t=1232807032283000&pt=1232807012283000&diffWidget=true&s=AJVazbXBr2D7KZ6E3qJBWICjRrHj5pKG-Q&pli=1
quote:
"""
A simple call to the function with an irrational number returns a list
for the infinite continued fractions, with the last digit or two
incorrect.
For exapmle:
continued_fraction(sqrt(2))
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1]
the last two digits are incorrect
continued_fraction(sqrt(109))
[10, 2, 3, 1, 2, 4, 1, 6, 6, 1, 4, 2, 1, 3, 2, 20, 3]
the last digit (3) is incorrect
"""
Interestingly, the doctests in
http://hg.sagemath.org/sage-main/file/b0aa7ef45b3c/sage/rings/arith.py
/ continued_fraction_list(...)
clearly state that this is correct.
If i read the code correctly, the symbolic expression is evaluated
with limited precision. I think it should stated in the doctests that
it is an approximation (line #2676 -> "# if x is a
SymbolicExpression, try coercing it to a real number") - or I'm wrong
or is this a bug?
Note: Mathematica does it this way:
dIn[1]:= ContinuedFraction[Sqrt[2], 20]
Out[1]= {1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}
H
Robert Bradshaw
>
> Hi, on the public bug tracker I got this one:
> http://spreadsheets.google.com/ver?
> key=pCwvGVwSMxTzT6E2xNdo5fA&t=1232807032283000&pt=1232807012283000&dif
> fWidget=true&s=AJVazbXBr2D7KZ6E3qJBWICjRrHj5pKG-Q&pli=1
I didn't know there was another "public bug tracker," but that link
isn't working for me...
http://trac.sagemath.org/sage_trac/ticket/5107
>
> quote:
> """
> A simple call to the function with an irrational number returns a list
> for the infinite continued fractions, with the last digit or two
> incorrect.
>
> For exapmle:
>
> continued_fraction(sqrt(2))
> [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1]
>
> the last two digits are incorrect
>
> continued_fraction(sqrt(109))
> [10, 2, 3, 1, 2, 4, 1, 6, 6, 1, 4, 2, 1, 3, 2, 20, 3]
>
> the last digit (3) is incorrect
> """
>
> Interestingly, the doctests in
> http://hg.sagemath.org/sage-main/file/b0aa7ef45b3c/sage/rings/arith.py
> / continued_fraction_list(...)
> clearly state that this is correct.
>
> If i read the code correctly, the symbolic expression is evaluated
> with limited precision. I think it should stated in the doctests that
> it is an approximation (line #2676 -> "# if x is a
> SymbolicExpression, try coercing it to a real number") - or I'm wrong
> or is this a bug?
Yes, this is a bug. It looks like its not correctly taking into
account the uncertainty in the last digit, but it could be
intermediate rounding issues as well.
Interestingly enough
sage: continued_fraction(QQ(RR(sqrt(2))))
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
sage: continued_fraction(RR(sqrt(2)).exact_rational())
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1,
1, 2, 7, 1, 2, 33, 2, 7, 5, 2, 1, 1, 16, 2]
Of course ideally it could directly compute the continued fraction of
sqrt(2), but that wouldn't fix this bug.
- Robert
William Stein
<robe...@math.washington.edu> wrote:
>
> On Jan 26, 2009, at 3:44 AM, Harald Schilly wrote:
>
>>
>> Hi, on the public bug tracker I got this one:
>> http://spreadsheets.google.com/ver?
>> key=pCwvGVwSMxTzT6E2xNdo5fA&t=1232807032283000&pt=1232807012283000&dif
>> fWidget=true&s=AJVazbXBr2D7KZ6E3qJBWICjRrHj5pKG-Q&pli=1
>
> I didn't know there was another "public bug tracker," but that link
> isn't working for me...
>
> http://trac.sagemath.org/sage_trac/ticket/5107
>
>>
>> quote:
>> """
>> A simple call to the function with an irrational number returns a list
>> for the infinite continued fractions, with the last digit or two
>> incorrect.
>>
>> For exapmle:
>>
>> continued_fraction(sqrt(2))
>> [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1]
>>
>> the last two digits are incorrect
>>
>> continued_fraction(sqrt(109))
>> [10, 2, 3, 1, 2, 4, 1, 6, 6, 1, 4, 2, 1, 3, 2, 20, 3]
>>
>> the last digit (3) is incorrect
>> """
>>
>> Interestingly, the doctests in
>> http://hg.sagemath.org/sage-main/file/b0aa7ef45b3c/sage/rings/arith.py
>> / continued_fraction_list(...)
>> clearly state that this is correct.
>>
>> If i read the code correctly, the symbolic expression is evaluated
>> with limited precision. I think it should stated in the doctests that
>> it is an approximation (line #2676 -> "# if x is a
>> SymbolicExpression, try coercing it to a real number") - or I'm wrong
>> or is this a bug?
>
> Yes, this is a bug. It looks like its not correctly taking into
> account the uncertainty in the last digit, but it could be
> intermediate rounding issues as well.
continued_fraction(sqrt(2))
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1]
the last two digits are incorrect"
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1]
so I dispute the claim that the last two digits are incorrect.
>
> Interestingly enough
>
> sage: continued_fraction(QQ(RR(sqrt(2))))
> [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
>
> sage: continued_fraction(RR(sqrt(2)).exact_rational())
> [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1,
> 1, 2, 7, 1, 2, 33, 2, 7, 5, 2, 1, 1, 16, 2]
>
> Of course ideally it could directly compute the continued fraction of
> sqrt(2), but that wouldn't fix this bug.
>
> - Robert
>
>
> >
>
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
Robert Bradshaw
>
> On Mon, Jan 26, 2009 at 11:48 AM, Robert Bradshaw
> <robe...@math.washington.edu> wrote:
>>
>> On Jan 26, 2009, at 3:44 AM, Harald Schilly wrote:
>>
>>>
>>> Hi, on the public bug tracker I got this one:
>>> http://spreadsheets.google.com/ver?
>>> key=pCwvGVwSMxTzT6E2xNdo5fA&t=1232807032283000&pt=1232807012283000&d
>>> if
>>> fWidget=true&s=AJVazbXBr2D7KZ6E3qJBWICjRrHj5pKG-Q&pli=1
>>
>> I didn't know there was another "public bug tracker," but that link
>> isn't working for me...
>
> I think this is the "report a bug" link in the notebook.
Oh. Hmm... it would be nice to integrate this into trac itself.
- Robert