For Task 1 refer notebook
For Task 2 refer notebook
In case of Task 1 the calculation of Fibonacci numbers as per the notebook is done by adding the last and the second last element. There are a lot of other advanced algorithms to do this faster.
Correction: The fast doubling method is faster than the recursive method to compute the nth fibonacci number but it is going to be slower when computing an entire series.link to issue
References to the fast doubling method : link1 link2
Matrix exponentiation method :
This is a simple identity relating the left matrix with the Fibonnaci sequence. Matrix multiplication is very fast when compared to other techniques but as n increases this increases computation as well.
Hence here comes the fast doubling method derived from the matrix exponentation algorithms.
I have benchmarked the results of calculating the nth Fibonacci number using both these methods. Initially till n = 40 the recurisive method is a bit faster but then the fast doubling algorithm becomes exponentially faster. code implementation
Results:
Thanks to @NishantPrabhu for his detailed notebooks.