Help! Square root algorithms request,PLZ.

[svenchen]

I am working on graphic computing these days.

Good square roots implementation on hardware is needed.

Could anybody offer some good paper on it?

Many thanks.

 

[LouisSheffield]

I'm looking for a paper online, with little luck so far.
I found it in the past - it's just a matter of time.

For most instances, you'll want a "reciprocal square-root" algorithm. The algorithm is iterative, and you end up with x^-0.5.
That's ok - just multiply by x when you're done, and you have x^+0.5.

That form is used (to my knowledge) within most DSPs and FPGAs, since it makes the least use of divides.

Added after 16 minutes:

Still looking, but I need to do a few things - I don't believe this is what I had found in the past, but it'll get you started:

**broken link removed**

(I'll look some more later)

Added after 6 minutes:

Also - are you looking for floating-point implementations? Or maybe integer with extra fractional bits?

 

[svenchen]

whoops
I was such a fool.
Multiply by x when you're done, and you have x^+0.5.
Quite a few papers on reciprocal square-root or say inverse square root could be found online.

But, might be a naive question, we need extra multiply which could cost much?

The value will be normalized to 1.x0x1x2......xm .

Again, Thanks a lot.

 

[LouisSheffield]

Nope - you're no fool.
These kinds of algorithms are usually dreamt up by people with names like Newton, as opposed to "Charlie the Baker" down the street.

Don't worry about an extra scaling multiply - modern hardware does pretty well with multiplies nowadays.

The absolute best algorithm I've ever used (without seeing what went on inside the black box) was done by TI for their TMS320C4x DSP line.

It involved an "approximate reciprocal square root" that got you 8-bits closer to done per iteration - four iterations, and you're good for 32-bit numbers.

Added after 10 minutes:

More questions on my part ... Given you're using this for graphics, is it more an issue that you merely know when to jog pixels while rendering something?
(this would be akin to how much the value of a square root changes, as opposed to the value itself)

If so, there's a series of books (Graphics Gems) that you'll want to have access to and learn from.