The "how to fibonacci" table is missing one other fun and clever way that I want to share -- using a field extension.
Using the Binet closed form for Fibonacci with floating point numbers is problematic because of finite precision. Naive exponentiations of the golden ratio are not accurate. Part of the problem is the infinite precision needed to deal with sqrt(5).
One way to deal with that is to represent numbers in the numerator or denominator as (a + b √5) with a and b as integers. Whenever the √5 gets multiplied you separate it out as 5.
This is way is not faster. One ends up with the logarithmic complexity of exponentiation by squaring. Nonetheless its quite fun and accurate.
Comments
The "how to fibonacci" table is missing one other fun and clever way that I want to share -- using a field extension.
Using the Binet closed form for Fibonacci with floating point numbers is problematic because of finite precision. Naive exponentiations of the golden ratio are not accurate. Part of the problem is the infinite precision needed to deal with sqrt(5).
One way to deal with that is to represent numbers in the numerator or denominator as (a + b √5) with a and b as integers. Whenever the √5 gets multiplied you separate it out as 5.
This is way is not faster. One ends up with the logarithmic complexity of exponentiation by squaring. Nonetheless its quite fun and accurate.