Hardware implementation of square root?

math hardware sqrt
Dimitar Petrov picture Dimitar Petrov · Jan 15, 2012 · Viewed 9.9k times · Source

I'm trying to find a little bit more information for efficient square root algorithms which are most likely implemented on FPGA. A lot of algorithms are found already but which one are for example from Intel or AMD? By efficient I mean they are either really fast or they don't need much memory.

EDIT: I should probably mention that the question is generally a floating point number and since most of the hardware implements the IEEE 754 standard where the number is represented as: 1 sign bit, 8 bits biased exponent and 23 bits mantissa.

Thanks!

Answer

Paul S picture Paul S · Jan 16, 2012

Not a full solution, but a couple of pointers.

I assume you're working in floating point, so point 1 is remember that floating point is stored as a mantissa and exponent. The exponent of the square root will be approximately half the exponent of the original number thanks to logarithms.

Then the mantissa can be approximated with a look-up table, and then you can use a couple of newton-raphson rounds to give some accuracy to the result from the LUT.

I haven't implemented anything like this for about 8 years, but I think this is how I did it and was able to get a result in 3 or 4 cycles.

Related questions

How does the CPU do subtraction?

I have some basic doubts, but every time I sit to try my hands at interview questions, these questions and my doubts pop up. Say A = 5, B = -2. Assuming that A and B are 4-bytes, how does the CPU do …

Read More
How can I check for NaN values?

float('nan') results in Nan (not a number). But how do I check for it? Should be very easy, but I cannot find it.

Read More
Math.random() explanation

This is a pretty simple Java (though probably applicable to all programming) question: Math.random() returns a number between zero and one. If I want to return an integer between zero and hundred, I would do: (int) Math.floor(Math.…

Read More