3 ms·
It is funny to see the repeated squares algorithm every time it is rediscovered. Knuth, unsurprisingly, had one of his earlier papers involving it. He present
by taeric 8y ago
It is funny to see the repeated squares algorithm every time it is rediscovered. Knuth, unsurprisingly, had one of his earlier papers involving it. He presented it as related to addition chains and shows that just repeated squaring is not always superior.
I'm curious what all came of this effort, seeing it is marked 2015. It is also fun to see benchmarks of this method used in executing fib.
- zawerf 8y agoIt's not just the repeated squares algorithm though. The novel part about this post is the application of it. For most languages, if you write a for loop, the compiler is not smart enough to generate anything that runs in sublinear time. It might do some loop unrolling, reordering, or just skip running the whole loop altogether if it's dead code. But this is the first time I have seen something that can rewrite a loop to run in a different runtime complexity (specifically logarithmic time). He relies on rewriting python byte code but there's no reason why let's say a C compiler can't automatically identify a loop that can be rewritten as a linear recurrence relation and thus has a matrix exponentiation form.
- phkahler 8y ago... this is the first time I have seen something that can rewrite a loop to run in a different runtime complexity... Same here, but I really want to know how often this helps in real programs.
- jcranmer 8y agoClang will optimize basic loops away: https://godbolt.org/g/GMjKZm https://godbolt.org/g/GMjKZm
- taeric 8y agoThis isn't new, though. Just doesn't come up as often as folks would like. Consider benchmarks that get reduced to constant. Happens literally all the time. This particular change is neat, and is ultimately keyed on seeing optimizations from really old math. Which is the only thing I was wanting to add.