Did any processor implement an integer square root instruction?

Question

Has any processor ever implemented an integer square root instruction? Obviously, floating-point square root instructions are quite common, but I've never seen one specifically for integers.

One close candidate I know of is the Nintendo DS, which contained a memory-mapped integer divider/square rooter. This was helpful for 3D calculations, given that its ARM processor had no FPU or hardware divider. However, it's not a native processor instruction.

Answer 1

Yes. The Harris RTX 2000 Forth CPU offered a multi-step square root instruction, as did its military-grade sibling, the RTX 2010. There may have been others, but that is the one I know of.

See: https://users.ece.cmu.edu/~koopman/stack_computers/sec4_5.html

Answer 2

Is 1946 retro enough?

From Wikipedia:

ENIAC used four of the accumulators (controlled by a special multiplier unit) to perform up to 385 multiplication operations per second; five of the accumulators were controlled by a special divider/square-rooter unit to perform up to 40 division operations per second or three square root operations per second.

ENIAC accumulators operated on decimal integers.

Answer 3

It's not that easy.

The most efficient method to calculate square root is to calculate inverse/reciprocal of the square root using Newton-Raphson iterations, and then multiply it with the original.

This is best known as the "Quake method" (see also Where did Fast InvSqrt() come from?). The more modern version used by contemporary CPU and GPUs are generalized into two instructions, one for estimating the initial guess (e.g. frsqrte of ARMv8), another to run the following iterations (e.g. frsqrts of ARMv8). Single-instruction version of sqrt is a micro-coded or pseudo-instruction version of these two instructions.

The prerequisite for all of this is a multiplier.

If you want to calculate FP (i)sqrt, then you need a (fast) FP multiplier, which all FPUs have.

If you want to calculate integer (i)sqrt, then you need a (fast) integer multiplier, which most CPUs don't have (historically). Otherwise it would be called a DSP.

To make it better, you need a (fast) multiplier that is twice the width of your input to have sufficient precision, which most CPUs definitely don't have until "relatively" recently (relative to RetroComputing).

And precision matters, or not?

If you look at the "Quake method" closely, you notice that one of the iterations was commented out.

There are a lot of use cases where the extreme precision isn't necessary and it'll be better to leave the choice of precision/speed trade off to programmers. isqrt was intentionally separated into fsqrte and fsqrts on ARMv8 exactly for this reason: so that the programmer can adjust the number of fsqrts for the desired speed and accuracy tradeoff.

So I don't quite agree to the statement that single instruction sqrt is very common. It's there because the IEEEE754 and the C stand math library requires it (for the flag bits and exceptions), but that doesn't mean it's frequently used.

Further reading

• SPRC542 TI's math library for C64x DSP (8-issue VLIW CPU with two 32x32=64 multipliers). In this library _iq _IQisqrt is implemented using Newton-Raphson iterations and _iq _IQsqrt is calculated by multiplying the original with the isqrt. The source code is available on request.
• SPRUGG9 TMS320C64x+ IQmath Library User's Guide.The user guide for SPRC542.
• My implementation of square root using binary search, that doesn't depend on a multiplier. Only basic ALU instructions are used. It is vigorously undocumented. I have no idea what I wrote but it seems to work.

.

unsigned int usqrt(unsigned int x){
    unsigned int a=0;
    unsigned int masksq=0,mask=0;
    unsigned int mask_shift=15;
    for(masksq=1u<<(mask_shift<<1),mask=1u<<(mask_shift);
        mask!=0;
        masksq=masksq>>2,mask=mask>>1,mask_shift--){
        if(x>=masksq){
            a=mask;
            break;
        }
    }
    x-=masksq;//masksq==a*a;
    mask=mask>>1;
    mask_shift--;
    while(mask>0){
        unsigned int step=(mask<<mask_shift)+(a<<(mask_shift+1));
        if(x>=step){
            a|=mask;
            x-=step;
        }
        mask=mask>>1;
        mask_shift--;
    }
    return a;
}

Answer 4

The claim in another answer of the Quake trick being the most efficient has not been true for a long time, and was only true regarding low-quality results for floats on specific hardware. On pretty much every modern chip the native instructions are much, much faster, often a few clock cycles. (I'm the Chris Lomont that wrote an early, widely cited paper on the Quake trick, providing generalizaitions and an improvement that seems to have been copied everywhere, despite it being a terrible idea now).

A much quicker method, one used in hardware (with many more tricks), is to store a (non-equal spaced) table of values, use a quick method to pull two values, linear (or better) interpolate, shift base 2 exponent with any odd excess becoming a multiple by constant sqrt2, then, if needed, one iteration of methods better than Newton–Raphson.

Things like Halley's (and many others) converge quicker than Netwon–Raphson, and are often much faster depending on what time various operations take.

Approximations for square root on a fixed interval (since all the methods for computers are bounded) are often also faster, polynomial, Cheby stuff, Pade and higher versions, all can be done in software or hardware, depending on what tradeoffs you want.

If you only want integer, say 2^32, the same trick applies, do it in fixed point, and some not too hard analysis lets you bound tables very quickly. Another simple method used in hardware for integers is divide and conquer: each say 8 bits maps to a table of 256 fixed point values, instantly looked up in parallel, then 3 multiples (2 in parallel) give the 32 bit value (after a free truncate).

There's still plenty of research being done on speeding these up (e.g., https://inria.hal.science/hal-03424131), so any technique over 10 years old is most surely obsolete for any metric: speed, power consumption, die size, etc.