Question: Disclaimer: Homework question. I'm looking for a hint…

Professor F. Lake tells his class that it is asymptotically faster to square an n-bit integer than to multiply two n-bit integers. Should they believe him?

I believe that multiplying two n-bit ints via shift/add is an O(n) operation, but I can't see why squaring an n-bit int would be any different. Am I missing something?

Answer: 
Since you wanted only a hint, answer comes from this equation: `(a + b)^2 = a^2 + b^2 + 2*a*b` 

To not spoil the puzzle, I've posted complete solution [separately](http://jsfiddle.net/DqpLm/1/) :)
My thought is that to multiply two n-bit integers your algorithm needs to cater for any two n-bit integers. That's `(2^n)^2` possible inputs.

A squaring algorithm only needs to handle `2^n` possible inputs, although it can be modelled as a multiply algorithm with two inputs the same.

My guess is that there would be some way to optimise the generic multiply algorithm when you know that both inputs will be the same, but I'd have to think about it. That's the line I'd be investigating, anyway...