Did any processor implement an integer square root instruction?

AArch64 NEON has the URSQRTE instruction, which gets closer to the OP&#x27;s question than you might think; view a 32-bit value as a fixed-precision integer with 32 fractional bits (so the representable range is evenly spaced 0 through 1-ε, where ε=2^-32), then URSQRTE computes the approximate inverse square root, halves it, then clamps it to the range 0 through 1-ε. Fixed-precision integers aren&#x27;t quite integers, and approximate inverse square root isn&#x27;t quite square root, but it might get you somewhere close.<p>The related FRSQRTE instruction is much more conventional, operating on 32-bit floats, again giving approximate inverse square root.

Is it possible in a single clock-cycle. Yes, with a very large lookup table. It is probably possible to reduce the size depending on how many serial logical gates can be executed within the clock-cycle. Think about that the binary root of 10000 is rather similar to that of 100 only with respect to different number of zero&#x27;s.

If you wanted to expand the definition of “processor” to electromechanical contraptions, the Friden SRQ could perform square roots using just additions and shifts, with not a single electronic component other than a motor. And since you had to position the decimal points manually, it would _technically_ be an integer operation…<p>Video: <a href="https:&#x2F;&#x2F;youtu.be&#x2F;o44a1ao5h8w" rel="nofollow">https:&#x2F;&#x2F;youtu.be&#x2F;o44a1ao5h8w</a>

Can&#x27;t you use the sequence 1 + 3 + 5 + ... + 2k + 1 to get the integer square root of any integer number? It&#x27;s basically the k of the nearest lower number to your number in this sequence.

This bit in an answer further down made me chuckle:<p>&gt; <i>My implementation of square root using binary search, that doesn&#x27;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.</i><p>A fine reminder that if we write clever code, we&#x27;re probably not going to remember how it works.

You need to read down a bit, but the answer “ENIAC” is hilarious.

2 ^ (1&#x2F;2 * Log2(X)) = sqrt(X)<p>You can get a really really rough approximation if you replace Log2(x) with &#x27;count leading zeroes&#x27;. With a better approximation of Log(2), you can get closer to the answer.

For an approximate (very rough) answer, as opposed to one accurate to the nearest integer, a right shift by half the number of bits of the leading 1’s position will do, and of course nearly every processor has a shift instruction. I’m not sure how often processors haven’t had something like FLO (Find Leading One) or FFS (Find First Set) instruction, those seem ubiquitous as well.<p>The super rough approximation for some uses can be approximately as good as an accurate answer. When you just need a decent starting place for some further Newton-Raphson iteration, for example. (Of course the right-shift trick is a nice way to seed a more accurate square root calculation. :P)

IIRC, most (all?) fixed point DSP&#x27;s have a square root instruction and&#x2F;or helper instructions.

Semi-related and of interest to 6502 fans, exhaustive analysis of square root algorithms: <a href="https:&#x2F;&#x2F;github.com&#x2F;TobyLobster&#x2F;sqrt_test">https:&#x2F;&#x2F;github.com&#x2F;TobyLobster&#x2F;sqrt_test</a>

ARM VFP has VSQRT<p><a href="https:&#x2F;&#x2F;developer.arm.com&#x2F;documentation&#x2F;dui0473&#x2F;m&#x2F;vfp-instructions&#x2F;vsqrt" rel="nofollow">https:&#x2F;&#x2F;developer.arm.com&#x2F;documentation&#x2F;dui0473&#x2F;m&#x2F;vfp-instru...</a>

I&#x27;m sure the VAX must have? (if we are including microcode)