Yeah. Solved it 16 years ago as an intellectual game. comp.lang.c was my Hacker News at the time ;) See http://groups.google.fr/group/comp.lang.c/browse_thread

Yeah. Solved it 16 years ago as an intellectual game. comp.lang.c was my Hacker News at the time ;) See http://groups.google.fr/group/comp.lang.c/browse_thread/thread/229c0a6f0d0c031c/5aacf5997b615c37 http://groups.google.fr/group/comp.lang.c/browse_thread/thre... The method is very simple. We know how to compute the square of a value. So start by finding the biggest integer value with a single bit set whose square is smaller than the input value. Then set the bit just below to one, compute the square of the value and compare it with the input value. If it is bigger, the bit should be 0 otherwise it should be left to 1. And so on. The thing is to avoid the multiplication to compute the square. So if you have a value n and you want to set a bit to one. We compute in fact the square of (N+B) where B is an integer with the bit to set to one, set to one. We then have (N+B)² = N² + 2NB + B² The last term is easy to compute from the previous B with the previous bit set. We simply divide by 4. 2NB is computed by a simple shift and N² is the result of the previous computation. For fixed point, we benefit from the fact that while we progress in computing the square root, we have an increasing number of bits set to 0 in the most significant bits of the values. I then simply shift up to get usable bits in the less significant bits. The only limitation is that we need the sign bit of the fixed point. So the computation won't work with big unsigned fixed points. This is solved by unwinding the first iteration. It took me some time to understand all this. All I had was a short code to compute integer square root and I had no idea how it worked.