ADD Nth Fibonacci Number

[Mukesh751]

Feature description

Want to add a python script which calculates Nth Fibonacci number in log(N) time complexity.
I have gone through the repo, the current version of Fibonacci Number uses Binet's formula and it's TC is (1.6)^n.

If possible please label this under HacktoberFest'23, if not, no issues.
Please assign this issue to me.

[tianyizheng02]

Please assign this issue to me.

No. We don't assign issues in this repo. Please read the contributing guidelines.

Want to add a python script which calculates Nth Fibonacci number in log(N) time complexity.

We already have dynamic_programming/fast_fibonacci.py, which calculates the nth Fibonacci number in logarithmic time. Is this the algorithm that you're referring to? If so, please consider contributing something else because we want to avoid duplicates in this repo.

[parsariyahi]

There is one problem with the code of fast_fibonacci.py
if we give the program a number like 100000
we get an error:
ValueError: Exceeds the limit (4300) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

[Mukesh751]

Please assign this issue to me.

No. We don't assign issues in this repo. Please read the contributing guidelines.

Want to add a python script which calculates Nth Fibonacci number in log(N) time complexity.

We already have dynamic_programming/fast_fibonacci.py, which calculates the nth Fibonacci number in logarithmic time. Is this the algorithm that you're referring to? If so, please consider contributing something else because we want to avoid duplicates in this repo.

No sir not that algorithm, the algorithm which I mentioned uses Matrix exponentiation Technique. I didn't find this algo in the repo, so I want to contribute.

[parsariyahi]

aha, I thought you want to edit the current dynamic_programming/fast_fibonacci.py code and just wanted to mention the error that I faced, and because of the merge request of the code I got confused, sorry.

[KunjMaheshwari]

Please assign this issue to me.

[tianyizheng02]

@KunjMaheshwari Did you even read my previous comment? We don't assign issues in this repo. Read the contributing guidelines.

[tianyizheng02]

No sir not that algorithm, the algorithm which I mentioned uses Matrix exponentiation Technique. I didn't find this algo in the repo, so I want to contribute.

Once again, we already have that algorithm: matrix/nth_fibonacci_using_matrix_exponentiation.py. Please make use of GitHub codebase search functionality.