You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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
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?
@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
Activity
cclauss commentedon Sep 14, 2019
👍 Go for it!
anirudnits commentedon Sep 14, 2019
sure
cclauss commentedon 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 commentedon Sep 16, 2019
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 commentedon Sep 25, 2019
@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 commentedon Sep 25, 2019
#1180 (comment) submit the PR
anirudnits commentedon Sep 25, 2019
Submitted the PR, please have a look.