#fibonacci#matrixexponentiation#memoization
92K subscribers • 1 video on Hallway
Intermediate. Assumes working knowledge.
920K views2 years ago1 recommendation
Computer scienceProgramming languagesAlgorithmsMath for programmersData structures
An exploration of different algorithms, from recursion to matrix exponentiation, to compute the largest possible Fibonacci number in one second.
Most of us are familiar with the Fibonacci sequence. What's the largest Fibonacci number you can compute in 1 second? I'm not setting any world records, here; I don't own a supercomputer. You can criticise my code here: github.com/SheafificationOfG/Fibsonicci Addenda: __________ At , the e_{01}s in the bottom row are incorrect... [in my defense, the Fibonacci transition matrix is symmetric]. Thanks @andykhang404! At (as of 2024-09-16), the GitHub link has been moved! See above. At , the formula for the coefficient of the product polynomial is incorrect; every instance of (N-1) should be replaced with an n in the summation on the right hand side... This error repeats at . Embarrassing! Thanks @henryroyer7691! Timestamps: __________ - Introduction - Recursion - Memoisation - "Linear" nonrecursive algorithm - Matrix-based algorithm - Things add up - Fast exponentiation algorithm - Grade-school multiplication - Multiplication through division - Discreet improvements - Fast and Furious (wysi) - Golden medallist - Thx 4 watching - The ugly truthWhat people say. Recommended as a humorous and educational video about optimizing Fibonacci calculations.
u/jarulsamyin r/rust • Recommends
On “Calculate a million digits of Pi within seconds”