Ask Hackaday: Computing Square Roots on FPGA?

Hackaday reader [nats.fr] wrote in with some code from a project that resizes a video stream on the fly using an FPGA. Doing this right means undoing whatever gamma correction has been applied to the original stream, resizing, and then re-applying the gamma. Making life simpler, [nats.fr] settled on a gamma of two, which means taking a bunch of square roots, which isn’t fast on an FPGA.

[nats]’s algorithm is pretty neat: it uses a first-stage lookup to figure out in which broad range the value lies, and then one step of Hero’s algorithm to refine from there. (We think this is equivalent to saying he does a piecewise linear interpolation, but we’re not 100% sure.) Anyway, it works decently.

Of course, when you start looking into the abyss that is special function calculation, you risk falling in. Wikipedia lists more methods of calculating square roots than we have fingers. One of them, CORDIC, avoids even using multiplication by resorting to clever bitshifts and a lookup table. Our go-to in these type of situations, Chebyshev polynomial approximation, didn’t even make the cut. (Although we suspect it would be a contender in the gamma=1.8 or gamma=2.2 cases, especially if combined with range-reduction in a first stage like [nats.fr] does.)

So what’s the best/fastest approximation for sqrt(x) for 16-bit integers on an FPGA? [nats.fr] is using a Spartan 6, so you can use a multiplier, but division is probably best avoided. What about arbitrary, possibly fractional, roots?

Relays Calculate Square Roots

After seeing an exhibit of an old relay-based computer as a kid, [Simon] was inspired to build a simple two-relay latching circuit. Since then, he’s been fascinated by how relays can function to do computation. He’s come quite a long way from that first latching circuit, however, and recently finished a huge five-year project which uses electromechanical relays to calculate square roots.

DSC_0240-e1394580570356

The frame of the square root calculator can hold up to 30 identical relay modules, each of which hold 16 relays on PCBs, for a total of 480 relays. The module-based setup makes repair and maintenance a breeze. Numbers are entered into the computer┬áby a rotary dial from an old phone and stored in the calculator’s relay memory. A nixie tube display completes the bygone era-theme of the device and shows either the current number that’s being entered, or the square root of that number as it’s being calculated.

The real magic of this project is that each relay has an LED which illuminates whenever the relay is energized, which shows the user exactly where all of the bits of the machine are going. [Simon] worked on this project from 2009 and recently completed it in 2014, and it has been featured at the San Mateo Maker Faire and at Microsoft Research in Redmond, WA. We’ve seen smaller versions of this before, but never on this scale and never for one specific operation like square roots.

Video below. Thanks to [Bonsaichop] for the tip!

Continue reading “Relays Calculate Square Roots”