Hacker's Delight

11-1. Integer Square Root

By the “integer square root” function, we mean the function To extend its range of application and to avoid deciding what to do with a negative argument, we assume x is unsigned. Thus, 0 ≤ x ≤ 2³² − 1.

Newton’s Method

For floating-point numbers, the square root is almost universally computed by Newton’s method. This method begins by somehow obtaining a starting estimate g₀ of Then, a series of more accurate estimates is obtained from

The iteration converges quadratically—that is, if at some point is accurate to