[SamReidHughes]

For what it's worth I learned that explicitly in a data structures & algorithms class. I've seen it come up in a bunch of other introductory material, so it seems like a relatively standard part of "the curriculum." I think somebody might have a chance of coming up with this shortcut on their own, if, for example, they wanted to compute the Nth Fibonacci number efficiently (using matrix exponentiation -- the bignum arithmetic makes it O(n^2) if you just do n multiplications) or if they wanted to compute a polynomial more efficiently by memoizing the values x^(2^n), or if you kidnapped them and threatened to kill their family if they couldn't figure out how to compute x^n using O(log_2(n)) multiplications...

The difficult thing about that shortcut isn't that you couldn't come up with it, it's that you wouldn't think to try coming up with it unless you are in a particularly painful situation.

I don't view this exponentiation speedup stuff as math-specific, it's something you can come across when efficiently updating string checksums under random access modifications and concatenations, or when solving some graph problem where you exponentiate an adjacency matrix.

[turnip1979]

I'm glad your algorithm class covered this. Mine did not. It surely covered some other obscure material that you don't know. You are missing the point. If we had a standard CS curriculum, you can fault people for missing out on stuff they should know. I think part of the problem is people is that CS is too big of a discipline at this point. A systems person couldn't pass a graphics person's interview, etc.

[SamReidHughes]

But I wouldn't require somebody to know of faster exponentiation in an interview. It's still too obscure.