Skip to content

Adding Matrix Exponentiation #1180

Closed

Description

@anirudnits

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

Activity

  1. cclauss commented on Sep 14, 2019

    @cclauss
    Member

    👍 Go for it!

  2. anirudnits commented on Sep 14, 2019

    @anirudnits
    ContributorAuthor

    sure

  3. cclauss commented on Sep 14, 2019

    @cclauss
    Member

    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.

  4. anirudnits commented on Sep 16, 2019

    @anirudnits
    ContributorAuthor

    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?

  5. anirudnits commented on Sep 25, 2019

    @anirudnits
    ContributorAuthor

    @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

  6. cclauss commented on Sep 25, 2019

    @cclauss
    Member

    #1180 (comment) submit the PR

  7. anirudnits commented on Sep 25, 2019

    @anirudnits
    ContributorAuthor

    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

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions