Opened 6 years ago

Closed 13 months ago

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

Reported by: Owned by: sstarosta sstarosta minor sage-9.3 number theory continued_fraction vdelecroix, sstarosta Miroslav Kovar Vincent Delecroix, Frédéric Chapoton N/A 8cafbb4 8cafbb46fc9f1a5256e80f53ea37b6712d01652b

Implement a method which, taking continued fraction x as an input, computes the continued fraction of (a*x+b)/(c*x+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.)

### comment:1 Changed 6 years ago by mirgee

• Branch set to u/mirgee/my_sage_1

### comment:2 Changed 6 years ago by git

• Commit set to 3fcc597e97e028f66e1fc1048338d6dd8f20a836

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.`

### comment:3 Changed 6 years ago by git

• Commit changed from 3fcc597e97e028f66e1fc1048338d6dd8f20a836 to 51f21d56f009aa01c8fd39a6409956ee935c0e9f

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

 ​51f21d5 `Better check coefficients using Integer.`

### comment:4 Changed 6 years ago by vdelecroix

Hello,

Some remarks:

1. You would better edit the description of this ticket to explain what you want to do.
1. 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.
1. The commit message should reflect what is inside the commit. Not your mood at the time you did the commit.
1. 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`.
1. 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.
1. All methods must be documented as explained in details in the developer manual.

Vincent

### comment:5 Changed 6 years ago by vdelecroix

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

### comment:6 follow-up: ↓ 10 Changed 6 years ago by 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

1. value() method is by documentation optional,
1. in case of _infinite, this would delegate the computation of value to RLF, which itself may use comparison,
1. 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?

### comment:7 Changed 6 years ago by mirgee

• Description modified (diff)

### comment:8 Changed 6 years ago by mirgee

• Description modified (diff)

### comment:9 Changed 6 years ago by git

• Commit changed from 51f21d56f009aa01c8fd39a6409956ee935c0e9f to fa1173a4a5d7a2570212b7dbaa62faf7a9669b37

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

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

### comment:10 in reply to: ↑ 6 Changed 6 years ago by vdelecroix

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

1. value() method is by documentation optional,
1. in case of _infinite, this would delegate the computation of value to RLF, which itself may use comparison,
1. 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))
```

### comment:11 Changed 6 years ago by vdelecroix

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 4). By the way why did you make this change in `lazy_list.pyx`?
• add doctests to each method or function

### comment:12 Changed 6 years ago by mirgee

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.

### comment:13 Changed 6 years ago by git

• Commit changed from fa1173a4a5d7a2570212b7dbaa62faf7a9669b37 to fea8eb997260a2a4d056fc26e4e72752a2e13702

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

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

### comment:14 Changed 6 years ago by git

• Commit changed from fea8eb997260a2a4d056fc26e4e72752a2e13702 to 92b8aa03f51c1d1abef29b5b4e2f657d267db9eb

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.`

### comment:15 Changed 6 years ago by git

• Commit changed from 92b8aa03f51c1d1abef29b5b4e2f657d267db9eb to e063f2fbdb0d43ee4d75b13d23c1f88eb1d125cb

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.`

### comment:16 Changed 3 years ago by chapoton

• Branch changed from u/mirgee/my_sage_1 to public/ticket/19120
• Commit changed from e063f2fbdb0d43ee4d75b13d23c1f88eb1d125cb to 3308c92d78c4ef22373f2cf7cccaf5d2273f6a79

rebase, squashed, py3-compatible

New commits:

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

### comment:17 Changed 3 years ago by git

• Commit changed from 3308c92d78c4ef22373f2cf7cccaf5d2273f6a79 to 031088f7ca9b4a18530fb972729472f8e8d71a27

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

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

### comment:18 Changed 15 months ago by chapoton

• Keywords continued_fraction added; continued fractions removed

### comment:19 Changed 15 months ago by git

• Commit changed from 031088f7ca9b4a18530fb972729472f8e8d71a27 to aeb6da12b14ff152dd1ec02abdc0b8cfa35970af

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

 ​aeb6da1 `Merge branch 'public/ticket/19120' in 9.2.b12`

### comment:20 Changed 15 months ago by chapoton

• Status changed from new to needs_review

### comment:21 Changed 15 months ago by chapoton

• Milestone changed from sage-pending to sage-9.3

### comment:22 Changed 15 months ago by git

• Commit changed from aeb6da12b14ff152dd1ec02abdc0b8cfa35970af to fe2cd08a88e946b7dd9878d3c13d951fb159f376

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

 ​fe2cd08 `fix one returns`

### comment:23 Changed 15 months ago by vdelecroix

• Status changed from needs_review to needs_work

not suitable yet. I will provide a commit.

### comment:24 follow-up: ↓ 25 Changed 15 months ago by vdelecroix

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

Last edited 15 months ago by vdelecroix (previous) (diff)

### comment:25 in reply to: ↑ 24 ; follow-up: ↓ 27 Changed 15 months ago by mirgee

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

I am the author: Miroslav Kovar (miroslavkovar@…)

### comment:26 Changed 15 months ago by git

• Commit changed from fe2cd08a88e946b7dd9878d3c13d951fb159f376 to 81e069389c5944f1b26ecc7aac111bda7bc9b1c2

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

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

### comment:27 in reply to: ↑ 25 Changed 15 months ago by vdelecroix

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

I am the author: Miroslav Kovar (miroslavkovar@…)

### comment:28 Changed 15 months ago by vdelecroix

• Authors set to Miroslav Kovar
• Reviewers set to Vincent Delecroix
• Status changed from needs_work to needs_review

### comment:29 Changed 15 months ago by chapoton

patchbot plugins complain

### comment:30 Changed 15 months ago by chapoton

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

### comment:31 Changed 15 months ago by git

• Commit changed from 81e069389c5944f1b26ecc7aac111bda7bc9b1c2 to 3323f09f75c96787cd0d7496aa4b761cd32fc1a0

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

 ​3323f09 `enoding, import, references`

### comment:32 Changed 15 months ago by chapoton

Merci. Pyflakes est encore pas content:

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

### comment:33 Changed 15 months ago by git

• Commit changed from 3323f09f75c96787cd0d7496aa4b761cd32fc1a0 to 7161eafc6a96ba597d3b6165257cac1070f56ac1

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

 ​7161eaf `remove unused import`

### comment:34 Changed 15 months ago by vdelecroix

• Status changed from needs_review to needs_work

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`.

### comment:35 Changed 15 months ago by git

• Commit changed from 7161eafc6a96ba597d3b6165257cac1070f56ac1 to 8cafbb46fc9f1a5256e80f53ea37b6712d01652b

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

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

### comment:36 Changed 15 months ago by vdelecroix

• Status changed from needs_work to needs_review

fixed

### comment:37 Changed 15 months ago by chapoton

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

### comment:38 Changed 15 months ago by vdelecroix

• Reviewers changed from Vincent Delecroix to Vincent Delecroix, Frédéric Chapoton
• Status changed from needs_review to positive_review

### comment:39 Changed 13 months ago by vbraun

• Branch changed from public/ticket/19120 to 8cafbb46fc9f1a5256e80f53ea37b6712d01652b
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.