Hacker’s Delight, Second Edition

Chapter 11. Some Elementary Functions

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, ...