Finding the square root of a given number using bitwise operations

Question

Is there an algorithm for finding the square root of a given number using bitwise operations?

Answer 1

There is this famous piece of code magic that calculates the inverse square root with some very smart bit. This is incorrectly attributed to John Carmack - here digging deeper into his origin. Perhaps what are you asking?

I would not suggest using it. On a modern processor, it cannot surpass faithful transcendental instructions. Your regular C ++ intrinsic sqrt() will probably beat him with his hands.

[Edit:] This article describes the general derivation method for such quick approximations and explicitly states: "Derive a similar method for sqrt (x)" as a home task in its final lines. Thus, you should be able to track your reasoning and independently develop a similar method for sqrt (without the reverse).

Answer 2

Wikipedia contains an article and code too. And another wikipedia article shows an algorithm (even for roots greater than 2), which can be easily implemented in binary format (such as the operation on bits).

If you want to stick to only real bitwise operators, you need to implement + using Ands, Ors, Xors, Nots ... If you want to do this on floats according to IEEE, you will need more work (the first wikipedia code can be used on the mantissa “directly”, probably under a certain restriction, and adjust the indicator “accordingly” ... you need to figure out how, however!)

Answer 3

No ... I guess this is for performance? If so, the best thing you are likely to get is to use a lookup table. If you have the ability to work with integer math (for example, using numbers multiplied by 10, 100, or 1000 instead of floating), you can use bitwise rotation to quickly reset unnecessary precision and go to the lookup table.