Opened 3 years ago
Last modified 7 weeks ago
#28282 needs_work enhancement
Add iterator method in QQ for Calkin-Wilf sequence
Reported by: | bgillespie | Owned by: | |
---|---|---|---|
Priority: | minor | Milestone: | sage-9.7 |
Component: | combinatorics | Keywords: | sequence, iterator |
Cc: | slelievre | Merged in: | |
Authors: | Bryan Gillespie | Reviewers: | Samuel Lelièvre |
Report Upstream: | N/A | Work issues: | |
Branch: | u/bgillespie/add_iterator_method_in_qq_for_calkin_wilf_sequence (Commits, GitHub, GitLab) | Commit: | 9b82daceade1a4ab1cedbe13d1c1d2cb61aa39ea |
Dependencies: | Stopgaps: |
Description
Add a method to the set of rational numbers to produce an iterator for the Calkin-Wilf sequence, an explicit ordering of the positive rationals with some interesting features. Background:
Change History (14)
comment:1 Changed 3 years ago by
- Branch set to u/bgillespie/add_iterator_method_in_qq_for_calkin_wilf_sequence
comment:2 Changed 3 years ago by
- Commit set to 9b82daceade1a4ab1cedbe13d1c1d2cb61aa39ea
comment:3 Changed 3 years ago by
- Status changed from new to needs_review
comment:4 Changed 2 years ago by
- Milestone changed from sage-8.9 to sage-9.1
Ticket retargeted after milestone closed
comment:5 Changed 2 years ago by
- Milestone changed from sage-9.1 to sage-9.2
Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.
comment:6 Changed 21 months ago by
- Cc slelievre added
- Reviewers set to Samuel Lelièvre
- Status changed from needs_review to needs_work
That would be a nice addition!
The branch needs rebasing. In addition I suggest considering these minor changes:
- p, q = ZZ(1), ZZ(1) + p = q = ZZ.one() if all_rationals: - yield self(0) + yield self.zero() while True: - yield self(p / q) - yield -self(p / q) + yield self((p, q)) + yield self((-p, q)) p, q = q, 2 * (p // q) * q - p + q else: while True: - yield self(p / q) + yield self((p, q)) p, q = q, 2 * (p // q) * q - p + q
comment:7 Changed 21 months ago by
We've been there already:
It's indeed a cute sequence. The generating formula is surprisingly simple, but most problems that require iterating over the rationals are better served by another order (indeed, it's since been replaced by iteration by height):
https://git.sagemath.org/sage.git/commit/?h=55ad3590cb7d993f38c9104ea87da24b21567009
comment:8 follow-up: ↓ 9 Changed 21 months ago by
Thanks @nbruin for pointing out the initial iterator for QQ
used this sequence, and for the pointers to the commits
implementing it and then replacing it with a better default.
This ticket aims to provide a Calkin-Wilf iterator as distinct
from the standard iterator for QQ
.
Would you advise against it? Would this Calkin-Wilf iterator
better be given as an example in the tutorial on iterators?
Maybe with a reference from the documentation of QQ
?
comment:9 in reply to: ↑ 8 Changed 21 months ago by
Replying to slelievre:
Thanks @nbruin for pointing out the initial iterator for
This ticket aims to provide a Calkin-Wilf iterator as distinct from the standard iterator for
Would you advise against it? Would this Calkin-Wilf iterator better be given as an example in the tutorial on iterators? Maybe with a reference from the documentation of
I'd think so. The formula is exceedingly simple: see the original implementation that was essentially a one-liner.
I was originally enthusiastic when I learned about the formula, but I don't think the sequence really has wider applications. Including it would be more of encyclopedic interest, and I think QQ
is not the right place for that. We already have OEIS. Interfacing with that makes more sense. There is in fact a (lousy) sage program listed there. It would make a lot more sense if there were an iterator there.
comment:10 Changed 19 months ago by
- Milestone changed from sage-9.2 to sage-9.3
comment:11 Changed 15 months ago by
- Milestone changed from sage-9.3 to sage-9.4
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:12 Changed 10 months ago by
- Milestone changed from sage-9.4 to sage-9.5
Setting a new milestone for this ticket based on a cursory review.
comment:13 Changed 5 months ago by
- Milestone changed from sage-9.5 to sage-9.6
comment:14 Changed 7 weeks ago by
- Milestone changed from sage-9.6 to sage-9.7
Branch pushed to git repo; I updated commit sha1. New commits:
Add literature reference and improve performance