Effective square root algorithms implemented on FPGAs already

The usual software implementation, especially in floating point, is Newton-Raphson based. With a good starting value, and appopriate exponent adjustment, it is about two cycles for single precision and four for double, with a divide in each cycle.

There is an algorithm that is mostly shift and add (or subtract), slightly similar to shift and subtract divide algorithms, a binary implementation of the pencil and paper square root algorithm that was used before calculators became common. There is a related algorithm used to do square root on an abacus.

-- glen

I thought that the abacus finds just the integer part of the square root and it's not working on floating point numbers?

root

algorithms

more

--------------------------------------- Posted through

Search for the paper:

Implementation of Single Precision Floating Point Square Root on FPGAs

- by Yamin Li and Wanming Chu.

Cheers, Jon

Fixed point, but you can move the decimal point anywhere you want to. One position in the square root for each two positions in the argument. That is, sqrt(2) = sqrt(2000000)/1000. Just like the slide rule, you have to remember the position of the decimal point.

I once tested the algorithm to calculate sqrt(2) to six places. (The digits of the starting number decrease in pairs, as the digits of the square root increase. I had to make up some tricks to get six.

I bought a cheap abacus with a little booklet of algorithms in the Chinatown of some large city. There is also a cube root algorithm, but you need two abaci for a reasonable number of digits. (You keep the accumulating cube root and its square as you go.)

-- glen

Probably not so hard. The hard one to do on FPGAs is floating point addition. (Pre and post normalization are much bigger than the add.)

You need to multiply by sqrt(2) if the incoming exponent is odd, otherwise it is as easy as fixed point.

-- glen

Thanks for hints guys.

@Glen: Could you please explain why it's hard to it on FPGAs?

I got a little bit confused right now ;) Most of the algorithms which are already implemented on FPGAs are floating point right?

Cheers, Dimitar

--------------------------------------- Posted through

Not at all. I churn out signal processing designs in FPGAs pretty constantly and have never once implemented a floating-point design. They're very expensive in terms of hardware used, as compared to fixed-point. I'm not saying that there aren't plenty of people out there, including on this group, doing floating. But I think you'd find that floating point designs are in the minority, especially on lower-end (Spartan, Cyclone) FPGAs.

Roby, thanks a lot for bringing a little bit light. I really appreciate that. I'll take a look and try to clarify to myself cons and pros of both.

Cheers, Dimitar

floating

constantly and have never once implemented a floating-point design. They're very expensive in terms of hardware used, as compared to fixed-point. I'm not saying that there aren't plenty of people out there, including on this group, doing floating. But I think you'd find that floating point designs are in the minority, especially on lower-end (Spartan, Cyclone) FPGAs.

--------------------------------------- Posted through