Skip to content
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

Matrix Exponentiation #589

Merged
merged 10 commits into from
Dec 5, 2019
Merged

Matrix Exponentiation #589

merged 10 commits into from
Dec 5, 2019

Conversation

kushagra98
Copy link

Matrix Exponentiation (also known as matrix power, repeated squaring) is a technique used to solve linear recurrences. This technique is very useful in competitive programming when dealing with linear recurrences (appears along Dynamic Programming).

Example to calculate the 10^18th fibonacci series term, it can not be done using Recursion, or DP but using matrix expo.

@cclauss cclauss added the automated tests are failing Do not merge until tests pass label Dec 5, 2019
@cclauss
Copy link
Member

cclauss commented Dec 5, 2019

Our automated tests are failing at https://github.com/TheAlgorithms/C-Plus-Plus/pull/589/checks?check_run_id=334456290#step:9:46

Also, please remove the file .DS_Store from this pull request.

@kushagra98
Copy link
Author

There was a slight mistake in the code. It is fixed now.

@cclauss
Copy link
Member

cclauss commented Dec 5, 2019

Click Details next to the ❌ below to see why tests are failing.

@cclauss
Copy link
Member

cclauss commented Dec 5, 2019

I am learning about cpplint and clang-format with your file. I hope it is not too disturbing.

I am down to the last two issues but I need your help to resolve them:

others/matrix_exponentiation.cpp:27:  Use int16/int64/etc, rather than the C type long  [runtime/int] [4]
others/matrix_exponentiation.cpp:28:  Use int16/int64/etc, rather than the C type long  [runtime/int] [4]

@kushagra98
Copy link
Author

I don't why there are errors of spaces before and after '<<' and '>>'. I came across this problem for the first time. I think it is due to the compiler, maybe github uses a 64 bit compiler.

@kushagra98
Copy link
Author

I have no clue how this compiler of github works. I'm still reading about it and trying to fix the code.

@kushagra98
Copy link
Author

Done!

@cclauss
Copy link
Member

cclauss commented Dec 5, 2019

cpplint is not a compiler. It is a Python program that Google wrote to drive consistency in its code reviews.

@kushagra98
Copy link
Author

Thanks for the knowledge. I really had no idea about it. Actually I'm more into competitive programming, where you have to code fast. So generally we don't care about the spaces and tabs.
Now the code is good to go. Thanks for the contributions and your help as well. Much appreciated sir. 👍

@cclauss cclauss merged commit b53bdf1 into TheAlgorithms:master Dec 5, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
automated tests are failing Do not merge until tests pass
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants