3

The algorithm is as follows:

res <- 0
for i from 15 downto 0 do:
   change the ith bit of result to 1
   if res^2 > x then:
      change the ith bit of res back to 0
return res

I completely understand how it works, but I don't know what this method is called. I've been looking at the wiki for computing methods of square root but to no avail. Is this the digit-by-digit method?

(related: How to compute the integer square root of a number in x86-64, without using div?)

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
whoshotya
  • 49
  • 4
  • In other areas (especially analog-to-digital conversion), that procedure is called "successive approximation". In square roots, though, Newton's method is also called "successive approximation". You could call this method "binary successive approximation" to distinguish it. It isn't used for square roots, because Newton's method converges a lot faster. – Matt Timmermans Sep 29 '17 at 04:03
  • 4
    This one is pretty clearly what wikipedia calls the [digit by digit algorithm](https://en.wikipedia.org/wiki/Integer_square_root#Digit-by-digit_algorithm), using bitwise ops for a base-2 implementation. BTW, on modern x86 hardware, the fastest integer sqrt is to use the FP `double`-precision hardware. On Haswell, converting to/from `double` is 4 cycle latency each way, plus 16 cycle latency for `sqrtsd`. (And it's only 3 instructions / 5 uops, so out-of-order execution can easily hide this latency if there's anything else to do.) – Peter Cordes Sep 29 '17 at 04:15
  • 2
    it looks like an ancient relic from times, where CPUs didn't even have multiplying instructions. the `res^2` can easily be avoided (by using 2 different values for res and res², initialized with 0x8000 and 0x40000000: one - res - shiftet right by 1 bit, the other - res² - by 2 bits each loop), after that this can be implemented easily on 6502 and similar CPUs – Tommylee2k Sep 29 '17 at 07:26

1 Answers1

4

As Peter Cordes mentioned in comments, this is digit-by-digit algorithm (here binary digits).

It is kind of binary search. You set i-th bit if squared result becomes closer to x but does not exceed it, so adding needed powers of two approximates result better and better.

MBo
  • 77,366
  • 5
  • 53
  • 86