efficient algorithm to compute continued fraction of a sum of continued fractions #19120

staroste · 2015-09-01T12:03:07Z

Implement a method which, taking continued fraction x as an input, computes the continued fraction of (ax+b)/(cx+d) using Gosper's algorithm. Call this method with proper arguments upon

sage: 3*x
sage: x+1

(overlaps with the following TODO item of sage/rings/continued_fraction.py:
Add Gosper’s algorithm to compute the continued fraction of (ax + b)/(cx + d) knowing the one of x (see Gosper (1972, http://www.inwap.com/pdp10/hbaker/hakmem/cf.html), Knuth (1998, TAOCP vol 2, Exercise 4.5.3.15), Fowler (1999). See also Liardet, P. and Stambul, P. “Algebraic Computation with Continued Fractions.” J. Number Th. 73, 92-121, 1998.)

CC: @videlec @staroste

Component: number theory

Keywords: continued_fraction

Author: Miroslav Kovar

Branch/Commit: 8cafbb4

Reviewer: Vincent Delecroix, Frédéric Chapoton

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

The text was updated successfully, but these errors were encountered:

sagetrac-mirgee · 2016-04-29T09:33:52Z

Branch: u/mirgee/my_sage_1

sagetrac-git · 2016-04-29T09:39:40Z

Commit: 3fcc597

sagetrac-git · 2016-04-29T09:39:40Z

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

`171498b`	`Solved the big bug with the negative value of infinite continued fraction! :)`
`7836c3e`	`Don't know what changed. Backing up.`
`7c6b445`	`Added a few lines to check for problem with singularity.`
`56c76e2`	`Latest version... Don't know what changed :)`
`3ab71ab`	`Done some code refactoring, tried to make the code simpler and more readable. I hope I didn't break it.`
`2bd5194`	`Of course I broke something. Bug for infinite fractions fixed and code shortened.`
`0dece4c`	`Added a test and fixed associated bugs (hopefully).`
`e246b63`	`Added a test and fixed associated bugs (hopefully).`
`f9714f8`	`Added check for arguments' validity.`
`3fcc597`	`Moved Gosper iterator.`

sagetrac-git · 2016-04-29T11:07:49Z

Changed commit from 3fcc597 to 51f21d5

sagetrac-git · 2016-04-29T11:07:49Z

Branch pushed to git repo; I updated commit sha1. New commits:

`51f21d5`	`Better check coefficients using Integer.`

videlec · 2016-04-29T18:11:48Z

comment:4

Hello,

Some remarks:

You would better edit the description of this ticket to explain what you want to do.
Your branch does not merge cleanly with the last beta. The reason is that you added a line in lazy_list.pyx: from sage.rings.all import Infinity. It is always better to base your work on the latest available version of the source code. You can consult the developer manual.
The commit message should reflect what is inside the commit. Not your mood at the time you did the commit.
The file with gosper algorithm should not be in sage/misc/. Put it in the same directory as continued_fraction.py. And you would better call it continued_fraction_gosper.py.
In continued_fraction.py you added the following in the comparison code

@@ -530,6 +530,8 @@ class ContinuedFraction_base(SageObject):
             if a == ZZ_0 and b == ZZ_0 and i:  # rational case
                 return 0
             i += 1
+            if i == 300:
+                return 0

I understand why you did it but it is definitely not a solution. What you can do is to raise a RuntimeError after a certain limit.

All methods must be documented as explained in details in the developer manual.

Vincent

videlec · 2016-04-29T19:16:30Z

comment:5

And last but not the least: it would be very nice to have Gosper algorithm within Sage!!

sagetrac-mirgee · 2016-04-30T08:35:06Z

comment:6

Hi,

thanks for the great input.

As for 5.: We need a way to compare instances of _infinite, and even though this is not a valid test, if enough terms are the same, the two continued fractions could be regarded as equal for most practical purposes. Another option would be to compare values, as in _real, but the problem is that

value() method is by documentation optional,
in case of _infinite, this would delegate the computation of value to RLF, which itself may use comparison,
this solution would effectively do the same thing - compute the value of the operands with certain precision and then compare the intervals.

What do you think?

sagetrac-git · 2016-04-30T09:21:09Z

Changed commit from 51f21d5 to fa1173a

sagetrac-git · 2016-04-30T09:21:09Z

Branch pushed to git repo; I updated commit sha1. New commits:

`fa1173a`	`Moved and renamed the continued_fraction_gosper. Added some documentation.`

videlec · 2016-04-30T15:34:46Z

comment:10

Replying to @sagetrac-mirgee:

Hi,

thanks for the great input.

As for 5.: We need a way to compare instances of _infinite, and even though this is not a valid test, if enough terms are the same, the two continued fractions could be regarded as equal for most practical purposes. Another option would be to compare values, as in _real, but the problem is that

value() method is by documentation optional,

in case of _infinite, this would delegate the computation of value to RLF, which itself may use comparison,

this solution would effectively do the same thing - compute the value of the operands with certain precision and then compare the intervals.

What do you think?

Everything would be better than an silent approximate comparison. If equality can not be decided just raise an error (see Python exceptions). I think that in that case an ArithmeticError would make sense.

If you want to check equality up to some precision, you should do

sage: abs(cf1 - cf2) < 2**-100

or

sage: R = RealIntervalField(256)
sage: R(cf1).overlaps(R(cf2))

videlec · 2016-04-30T15:46:33Z

comment:11

For the sake of this ticket I would not implement something like 1+cf or 3*cf which needs some work. Having a method apply_homography would be enough for a first ticket. In order to include this first part in Sage you need to

make it compatible with the last version of Sage source code (see 2. in [comment:4]). By the way why did you make this change in lazy_list.pyx?
add doctests to each method or function

sagetrac-mirgee · 2016-04-30T16:52:12Z

comment:12

The change in lazy_list() is unnecessary and can be deleted. Personally I don't think it is necessary to add doctests for the simple helper functions, but I will comply with the standards and add them, no problem. I will also look into the the comparison.

sagetrac-git · 2016-05-03T17:03:46Z

Branch pushed to git repo; I updated commit sha1. New commits:

`fa492af`	`Added more doctests in continued_fraction_gosper.py.`
`fea8eb9`	`Removed unnecessary comments.`

sagetrac-git · 2016-05-03T17:03:46Z

Changed commit from fa1173a to fea8eb9

sagetrac-git · 2016-05-04T09:17:50Z

Changed commit from fea8eb9 to 92b8aa0

sagetrac-git · 2016-05-04T09:17:50Z

Branch pushed to git repo; I updated commit sha1. New commits:

`92b8aa0`	`Added more unit tests, replaced overwritten method quotients() with get preperiod length, so that all doctests pass. Added a few more doctests. Now all methods are accompanied with doctests.`

sagetrac-git · 2016-05-08T20:21:11Z

Changed commit from 92b8aa0 to e063f2f

sagetrac-git · 2016-05-08T20:21:11Z

Branch pushed to git repo; I updated commit sha1. New commits:

`e063f2f`	`Using a set of tuples instead of list of dictionaries for state tracking, should improve performance. Using lazy_list instead of Word for instances of infinite continued fractions.`

fchapoton · 2019-05-12T12:50:57Z

comment:16

rebase, squashed, py3-compatible

New commits:

`3308c92`	`Implement Gosper algorithm for homographic action on continued fractions`

fchapoton · 2019-05-12T12:50:57Z

Changed commit from e063f2f to 3308c92

fchapoton · 2019-05-12T12:50:57Z

Changed branch from u/mirgee/my_sage_1 to public/ticket/19120

sagetrac-git · 2019-05-12T20:06:05Z

Branch pushed to git repo; I updated commit sha1. New commits:

`031088f`	`fix for py2: also define next`

sagetrac-mirgee · 2020-09-24T17:16:28Z

comment:25

Replying to @videlec:

Author? (name in the git log is John Doe <miroslav.kovar@concur.com>)

I am the author: Miroslav Kovar (miroslavkovar@protonmail.com)

sagetrac-git · 2020-09-24T17:59:02Z

Changed commit from fe2cd08 to 81e0693

sagetrac-git · 2020-09-24T17:59:02Z

Branch pushed to git repo; I updated commit sha1. New commits:

`81e0693`	`fixes, documentation, copyright, optimization`

videlec · 2020-09-24T17:59:29Z

comment:27

Replying to @sagetrac-mirgee:

Replying to @videlec:

Author? (name in the git log is John Doe <miroslav.kovar@concur.com>)

I am the author: Miroslav Kovar (miroslavkovar@protonmail.com)

Thanks. I put your name and mail in the copyright header of the file.

videlec · 2020-09-24T18:00:29Z

Author: Miroslav Kovar

videlec · 2020-09-24T18:00:29Z

Reviewer: Vincent Delecroix

fchapoton · 2020-09-25T07:24:41Z

comment:29

patchbot plugins complain

fchapoton · 2020-09-25T07:38:55Z

comment:30

Le reference [LS1998] a une allure bizarre, avec un P isolé

sagetrac-git · 2020-09-25T13:34:42Z

Changed commit from 81e0693 to 3323f09

sagetrac-git · 2020-09-25T13:34:42Z

Branch pushed to git repo; I updated commit sha1. New commits:

`3323f09`	`enoding, import, references`

fchapoton · 2020-09-26T06:17:30Z

comment:32

Merci. Pyflakes est encore pas content:

src/sage/rings/continued_fraction_gosper.py:37:1 'sage.rings.real_mpfr.RR' imported but unused

sagetrac-git · 2020-09-26T15:24:33Z

Changed commit from 3323f09 to 7161eaf

sagetrac-git · 2020-09-26T15:24:33Z

Branch pushed to git repo; I updated commit sha1. New commits:

`7161eaf`	`remove unused import`

videlec · 2020-09-26T15:42:17Z

comment:34

There is something wrong in the way infinity is handled. In the situation where we apply x -> 1 / (qx - p) to x=p/q Gosper iterator is empty. But currently continued_fraction([]) is wrongly 0.

sagetrac-git · 2020-09-26T15:56:40Z

Changed commit from 7161eaf to 8cafbb4

sagetrac-git · 2020-09-26T15:56:40Z

Branch pushed to git repo; I updated commit sha1. New commits:

`8cafbb4`	`fix infinities in continued fraction and do not forward values`

videlec · 2020-09-26T15:57:26Z

comment:36

fixed

fchapoton · 2020-09-28T07:42:58Z

comment:37

ok, this seems to be ready for a positive review ?

videlec · 2020-09-28T09:36:14Z

Changed reviewer from Vincent Delecroix to Vincent Delecroix, Frédéric Chapoton

vbraun · 2020-11-07T16:23:27Z

Changed branch from public/ticket/19120 to 8cafbb4

staroste added c: number theory pending labels Sep 1, 2015

staroste self-assigned this Sep 1, 2015

This comment has been minimized.

Sign in to view

videlec added s: needs review and removed s: needs work labels Sep 24, 2020

videlec added s: needs work and removed s: needs review labels Sep 26, 2020

videlec added s: needs review and removed s: needs work labels Sep 26, 2020

videlec added s: positive review and removed s: needs review labels Sep 28, 2020

vbraun removed the s: positive review label Nov 7, 2020

vbraun closed this as completed in be8479b Nov 7, 2020

efficient algorithm to compute continued fraction of a sum of continued fractions #19120

efficient algorithm to compute continued fraction of a sum of continued fractions #19120

Comments

staroste commented Sep 1, 2015

sagetrac-mirgee mannequin commented Apr 29, 2016

sagetrac-git mannequin commented Apr 29, 2016

sagetrac-git mannequin commented Apr 29, 2016

sagetrac-git mannequin commented Apr 29, 2016

sagetrac-git mannequin commented Apr 29, 2016

videlec commented Apr 29, 2016

videlec commented Apr 29, 2016

sagetrac-mirgee mannequin commented Apr 30, 2016

This comment has been minimized.

This comment has been minimized.

sagetrac-git mannequin commented Apr 30, 2016

sagetrac-git mannequin commented Apr 30, 2016

videlec commented Apr 30, 2016

videlec commented Apr 30, 2016

sagetrac-mirgee mannequin commented Apr 30, 2016

sagetrac-git mannequin commented May 3, 2016

sagetrac-git mannequin commented May 3, 2016

sagetrac-git mannequin commented May 4, 2016

sagetrac-git mannequin commented May 4, 2016

sagetrac-git mannequin commented May 8, 2016

sagetrac-git mannequin commented May 8, 2016

fchapoton commented May 12, 2019

fchapoton commented May 12, 2019

fchapoton commented May 12, 2019

sagetrac-git mannequin commented May 12, 2019

sagetrac-mirgee mannequin commented Sep 24, 2020

sagetrac-git mannequin commented Sep 24, 2020

sagetrac-git mannequin commented Sep 24, 2020

videlec commented Sep 24, 2020

videlec commented Sep 24, 2020

videlec commented Sep 24, 2020

fchapoton commented Sep 25, 2020

fchapoton commented Sep 25, 2020

sagetrac-git mannequin commented Sep 25, 2020

sagetrac-git mannequin commented Sep 25, 2020

fchapoton commented Sep 26, 2020

sagetrac-git mannequin commented Sep 26, 2020

sagetrac-git mannequin commented Sep 26, 2020

videlec commented Sep 26, 2020

sagetrac-git mannequin commented Sep 26, 2020

sagetrac-git mannequin commented Sep 26, 2020

videlec commented Sep 26, 2020

fchapoton commented Sep 28, 2020

videlec commented Sep 28, 2020

vbraun commented Nov 7, 2020