Skip to content

Adding Matrix Exponentiation #1180

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
anirudnits opened this issue Sep 14, 2019 · 7 comments · Fixed by #1203
Closed

Adding Matrix Exponentiation #1180

anirudnits opened this issue Sep 14, 2019 · 7 comments · Fixed by #1203

Comments

@anirudnits
Copy link
Contributor

I was just browsing through the algorithms and data structures but couldn't find Matrix Exponentiation, which is useful for solving linear recurrences in logarithmic time. So, is this something you guys think should be added? If yes then I can work on it and submit a PR. Thanks

@cclauss
Copy link
Member

cclauss commented Sep 14, 2019

👍 Go for it!

@anirudnits
Copy link
Contributor Author

sure

@cclauss
Copy link
Member

cclauss commented Sep 14, 2019

Please show us side-by-sige benchmarks (using timeit or similar) of the two methods running on the same square matrices so we can see the performance.

@anirudnits
Copy link
Contributor Author

Initially I thought of using the simple problem of finding the nth element of fibonacci series in O(logn) using Matrix Exponentiation as the base example to use because this is the most common problem in competitive programing sites to introduce matrix exponentiation. So, do you think this problem is enough or do I go for some more general linear recurrence?

@anirudnits anirudnits reopened this Sep 16, 2019
@TheAlgorithms TheAlgorithms deleted a comment from anirudnits Sep 16, 2019
@anirudnits
Copy link
Contributor Author

@cclauss I used the example of finding the nth element in the Fibonacci series in O(logn) to demonstrate Matrix Exponentiation. For performance evaluation, I compared the simple linear method of finding the nth element with the same using Matrix Exponentiation for random numbers in range of 10**4. Is anything else you would like me to add? otherwise I will submit the PR. Thanks

@cclauss
Copy link
Member

cclauss commented Sep 25, 2019

#1180 (comment) submit the PR

@anirudnits
Copy link
Contributor Author

Submitted the PR, please have a look.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants