A Linear Algebra Trick for Computing Fibonacci Numbers Fast

Re:A Linear Algebra Trick for Computing Fibonacci Numbers Fast by nimish on Monday November 06, 2023 @02:44PM (#38167834)

It's easier to treat these as linear difference equations with constant coefficients and use the ansatz of λ^{n}. This is morally the same thing but without the need for matrix manipulation.

Knuth, Oren and Patashnik's Concrete Mathematics is full of these and is required reading for discrete math.

[ Parent | on HN ]

Re:A Linear Algebra Trick for Computing Fibonacci Numbers Fast by mahalex on Monday November 06, 2023 @11:54PM (#38173391)

Note that “Oren and Patashnik” is one person named Oren Patashnik.

[ Parent | on HN ]

Re:A Linear Algebra Trick for Computing Fibonacci Numbers Fast by nimish on Wednesday November 08, 2023 @10:43AM (#38191980)

Thanks! The correct authors are Graham, Knuth, and Patashnik.

[ Parent | on HN ]

Re:A Linear Algebra Trick for Computing Fibonacci Numbers Fast by giik on Tuesday November 07, 2023 @10:53AM (#38178273)

I came here to say the same: difference equations, z-transform, recurrence relations, are (or used to be) standard undergrad eng curriculum (typically via some required Signals & Systems course). Maybe not so popular in the CS world though?

Beautiful expo on the subject: https://eee.guc.edu.eg/Courses/Communications/COMM401%20Sign... (Chapter 10, etc.)

[ Parent | on HN ]