18 Comments

Representing recurrences as matrix multiplications is one of the most mind-blowing applications of algebra. Surely one of my favourites. Nice one!

Expand full comment
Nov 10, 2023Liked by Abhinav Upadhyay

This was really interesting and led me down a rabbit hole, thank you!

On the way down the hole, I noticed that the TAOCP reference for the closed form should probably be page 79, not 99.

Expand full comment
Nov 6, 2023Liked by Abhinav Upadhyay

has anyone tried the mojo compiler on this? I've seen the demo/notebook here: https://github.com/modularml/mojo/blob/main/examples/notebooks/Matmul.ipynb

it uses:

https://mlir.llvm.org/

Expand full comment

That was very interesting. Does the “alternate proof of this form using linear algebra” involve diagonalizing the 2 by 2 matrix? If so, that’s a nice elementary application of eigenvectors and eigenvalues.

Expand full comment
Nov 5, 2023Liked by Abhinav Upadhyay

That was a fun read, thank you! I'm intrigued now to possibly buy the book - this post served as an excellent advertisement for it.

Expand full comment
Nov 5, 2023Liked by Abhinav Upadhyay

Great article. Looking forward to your next post.

Expand full comment
Nov 5, 2023Liked by Abhinav Upadhyay

You have managed to skillfully craft yet another addictive confession :) Great job, Abhi! Keep them coming 🎊

Expand full comment

Neat!

Expand full comment

What really bugs me is when people apply relatively fancy techniques like memoization and recursion without any need to do so. It's a telltale sign of an intern straight off LeetCode with very little coding experience. I mean, just do a simple loop - it's less code, works faster and easier to understand

Expand full comment