Performance of __getitem__ of CFiniteSequence #36763
Labels
Milestone
Comments
5 tasks
vbraun
pushed a commit
to vbraun/sage
that referenced
this issue
Dec 10, 2023
Efficiency of `__getitem__` for CFiniteSequence is improved. Fixes sagemath#36763 <!-- ^^^^^ Please provide a concise, informative and self-explanatory title. Don't put issue numbers in there, do this in the PR body below. For example, instead of "Fixes sagemath#1234" use "Introduce new method to calculate 1+1" --> <!-- Describe your changes here in detail --> <!-- Why is this change required? What problem does it solve? --> <!-- If this PR resolves an open issue, please link to it here. For example "Fixes sagemath#12345". --> <!-- If your change requires a documentation PR, please link it appropriately. --> ### 📝 Checklist <!-- Put an `x` in all the boxes that apply. --> <!-- If your change requires a documentation PR, please link it appropriately --> <!-- If you're unsure about any of these, don't hesitate to ask. We're here to help! --> <!-- Feel free to remove irrelevant items. --> - [x] The title is concise, informative, and self-explanatory. - [x] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [ ] I have created tests covering the changes. - [ ] I have updated the documentation accordingly. ### ⌛ Dependencies <!-- List all open PRs that this PR logically depends on - sagemath#12345: short description why this is a dependency - sagemath#34567: ... --> <!-- If you're unsure about any of these, don't hesitate to ask. We're here to help! --> URL: sagemath#36764 Reported by: Ryuhei Mori Reviewer(s): Marc Mezzarobba, Ryuhei Mori
vbraun
pushed a commit
to vbraun/sage
that referenced
this issue
Dec 13, 2023
Efficiency of `__getitem__` for CFiniteSequence is improved. Fixes sagemath#36763 <!-- ^^^^^ Please provide a concise, informative and self-explanatory title. Don't put issue numbers in there, do this in the PR body below. For example, instead of "Fixes sagemath#1234" use "Introduce new method to calculate 1+1" --> <!-- Describe your changes here in detail --> <!-- Why is this change required? What problem does it solve? --> <!-- If this PR resolves an open issue, please link to it here. For example "Fixes sagemath#12345". --> <!-- If your change requires a documentation PR, please link it appropriately. --> ### 📝 Checklist <!-- Put an `x` in all the boxes that apply. --> <!-- If your change requires a documentation PR, please link it appropriately --> <!-- If you're unsure about any of these, don't hesitate to ask. We're here to help! --> <!-- Feel free to remove irrelevant items. --> - [x] The title is concise, informative, and self-explanatory. - [x] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [ ] I have created tests covering the changes. - [ ] I have updated the documentation accordingly. ### ⌛ Dependencies <!-- List all open PRs that this PR logically depends on - sagemath#12345: short description why this is a dependency - sagemath#34567: ... --> <!-- If you're unsure about any of these, don't hesitate to ask. We're here to help! --> URL: sagemath#36764 Reported by: Ryuhei Mori Reviewer(s): Marc Mezzarobba, Ryuhei Mori
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Problem Description
The function
__getitem__for CFiniteSequence employs the matrix multiplications. Let d be the length of the linear recurrence (= the degree of the denominator of the generating function). Then, the computation of the n-th element requires time proportinal to d^3 log n.For example,
sage: C(1/(1-x^1000))[10^18]requries a couple of seconds. This is because the current program computes 10^18-th power of a 1000 x 1000 matrix.
Proposed Solution
There are mainly two algorithms requiring time proportinal to M(d) log n where M(d) is a time for computing a product of two polynomials of degree d. The naive algorithm for the polynomial multiplications gives M(d) = d^2. Other algorithms, e.g., Karatsuba, FFT, give asymptotically faster polynomial multiplications.
The newer algorithm for computing the n-th element of CFiniteSequence was proposed in https://arxiv.org/abs/2008.08822
This algorithm is easier to implement.
Alternatives Considered
Fiduccia's algorithm (https://doi.org/10.1137/0214007) has asymptotically similar time complexity. But, it is 1.5 times slower than the above algorithm.
Additional Information
No response
Is there an existing issue for this?
The text was updated successfully, but these errors were encountered: