This is very, very cool. Moving this kind of intelligence into the compiler and runtime is one of the things I desperately wanted to do in grad school. The academic machine ground that desire out of me in short order, but I still have a tremendous love of the work.
Are you working on compilers and runtimes? If you are interested in doing this, please shoot me an email svembu at zoho
This is great when your inner loop is calculating the nth Fibonacci number, but I'm skeptical that there are all that many practically occurring inner loops that are linear recurrences where the author of the code has not already recognized them as such.
The language he describes is not Turing-complete, which limits the number of use cases. Still very interesting when you have such a situation.
Have you considered doing matrix decompositions for faster exponentiation?
I guess the floating point handling would be hard to get right though.