Is there an algorithm to find the square root of a given number using bitwise operations?
+1
A:
No... I'm assuming it's for the sake of performance? If so, the best you are probably going to get is using a lookup table. If you have the option to work with integer math (ex. by working with numbers multiplied by 10, 100 or 1000 instead of floats) you can use bitwise rotation to quickly throw off unneeded precision and jump into a lookup table.
kasperjj
2010-07-04 12:44:44
+7
A:
There is this famous piece of code magic that computes inverse square root with a some very clever bit twiddling. It is wrongfully attributed to John Carmack - here's a deeper dig into its origin. Maybe that's what you're asking about?
I wouldn't suggest using it, though. On modern CPU's it cannot beat dedicated transcendental instructions. Your usual c++ intrinsic sqrt() would probably beat it hands down.
[Edit:] The cited article describes a general derivation method for such fast approximations, and explicitly states 'Derive a similar method for sqrt(x)' as a homework problem at its final lines. So you should be able to track its reasoning and devise a similar method for sqrt (without the reciprocal) directly.
Ofek Shilon
2010-07-04 13:01:11
A:
Yes, of course there is, how do you think computers compute square roots other than by using bitwise operations ?
High Performance Mark
2010-07-04 13:23:27
-1 Mark you know damn well that [bitwise operation](http://en.wikipedia.org/wiki/Bitwise_operation) has a precise meaning.
BlueRaja - Danny Pflughoeft
2010-07-04 17:27:17
Depends. Quantum computers execute on qubitwise operations?
John
2010-07-04 18:16:19
+1 it is useful to remember that complex operations are all implemented in "gate-logic"(*) with ands, ors, nots, shifters and alike. So the answer to "does it exist an algo to find the square root of a number using bitwise operations" can't be no. (indeed for performance something can use indeed a "table", but only once they realized that there was no way to make complex operations faster)
ShinTakezou
2010-07-05 06:18:57
+1 looking at the FPU implementation is indeed a good (hidden) pointer.
Mau
2010-07-06 22:16:49
+2
A:
Wikipedia has an article about and a code too. And another wikipedia article shows an algorithm (even for roots greater than 2) that can be easily implemented in binary (so, involving operation on bits).
If you want to stick only to real bitwise operators, you have to implement + using Ands, Ors, Xors, Nots... If you want to do it on floats according to IEEE, you need more work (the first code in wikipedia could be used on the mantissa "directly", likely under certain restriction, and adjust exponent "accordingly"... you have to figure out how, however!)
ShinTakezou
2010-07-04 13:53:43