3 ms·
It'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
by zawerf 8y ago
It'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.