Comment by LnxPrgr3 | Hacker News Reader

Comment by LnxPrgr3 | Hacker News Reader

Parent Full thread

Recent surprise: exponentiation by squaring. Not by name, but by being the correct answer to the question. (This is in the list of 500, by the way.)

It's trivial to explain:

    x^n = x(x^2)^((n-1)/2), if n is odd
        = (x^2)^(n/2)     , if n is even

Knowing that (or having figured that out yourself if an interview was your first exposure to this problem), it's even more trivial to implement, making it a math quiz far more than a programming exercise. (Though I later turned it into a programming exercise entirely to exploit an arbitrary eye bleedecution bug in the human brain: https://gist.github.com/LnxPrgr3/7154873d3eb8b1e5960851628c7...)

Maybe that's what they intended. It's certainly legit if the job will have you actually doing, rather than applying, math. Except that it concludes you can math if you're smart enough to pretend to derive the answer you memorized after encountering it before. You might accidentally hire a bunch of crypto nerds.

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.

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.

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

Reply on news.ycombinator.com