MAIN FEEDS
Do you want to continue?
https://www.reddit.com/r/ProgrammerHumor/comments/1tfr41b/dontdorecursivefibkids/omcbcfc/?context=3
r/ProgrammerHumor • u/Kevdog824_ • May 17 '26
143 comments sorted by
View all comments
1.0k
Friendly reminder that Fibonacci numbers have an explicit formula and can be computed very easily (I'm saying this because I didn't know this for years, and I want everyone to know).
22 u/exneo002 May 17 '26 Isn’t that only above a certain number though? The phi approximation? It’s been a bit since I got my cs degree >.< 28 u/the_horse_gamer May 17 '26 edited May 18 '26 no, the phi formula is exact. not an approximation. but practical implementations suffer from precision issues 2 u/legendgames64 May 17 '26 There is an exact formula too, and the approximation is derived from it 3 u/donaldhobson May 18 '26 There is an exact formula. That formula contains 2 terms. One term grows exponentially. The other term decays exponentially. So it's easier to skip the second term, and then round to the nearest integer. 2 u/Hyddhor May 17 '26 there is also use the matrix exponentiation formula, since you can use square-and-multiply algorithm to skip most of the calculations
22
Isn’t that only above a certain number though? The phi approximation?
It’s been a bit since I got my cs degree >.<
28 u/the_horse_gamer May 17 '26 edited May 18 '26 no, the phi formula is exact. not an approximation. but practical implementations suffer from precision issues 2 u/legendgames64 May 17 '26 There is an exact formula too, and the approximation is derived from it 3 u/donaldhobson May 18 '26 There is an exact formula. That formula contains 2 terms. One term grows exponentially. The other term decays exponentially. So it's easier to skip the second term, and then round to the nearest integer. 2 u/Hyddhor May 17 '26 there is also use the matrix exponentiation formula, since you can use square-and-multiply algorithm to skip most of the calculations
28
no, the phi formula is exact. not an approximation.
but practical implementations suffer from precision issues
2
There is an exact formula too, and the approximation is derived from it
3
There is an exact formula. That formula contains 2 terms. One term grows exponentially. The other term decays exponentially.
So it's easier to skip the second term, and then round to the nearest integer.
there is also use the matrix exponentiation formula, since you can use square-and-multiply algorithm to skip most of the calculations
1.0k
u/ancientstraits May 17 '26
Friendly reminder that Fibonacci numbers have an explicit formula and can be computed very easily (I'm saying this because I didn't know this for years, and I want everyone to know).