Academic presentation (in French) on the numeric computation of the Fibonacci sequence
Main issue : How to compute Fibonacci sequence in the most powerful way ?
Execution of sample/plotting script :
pip install matplotlib # unique Python dependency
python3 script.py
- Naive and iterative approaches
- Recursion formula
- Explicit method
- Recursion, a good lead ?
- Implementation attempt
- Comparison of iterative and recursive methods
- A last track : matrix writing
- General presentation of the used method
- Choice of fast exponentiation method
- Implementation for calculating quantities
$F_n$
- Conclusion & Answer to the problem
- Appendix : Application of
$F_n$ • Euclid's algorithm
Main reference : Based on Arnaud de Saint Julien's paper : Escapade algorithmique avec Fibonacci
Lucas RODRIGUEZ (MPSI - 2018/2019)