Incidentally, even if you are using Newton's method to do square roots, it helps significantly to start with a guess of the right size. If your initial guess i

Incidentally, even if you are using Newton's method to do square roots, it helps significantly to start with a guess of the right size. If your initial guess is way too large, each step will cut it down by about a factor of 1/2; if it's way too small, it's equivalent (for finding sqrt(N)) to choosing N/guess. Thus, if you're taking the square root of 2^64, and you start with 1, your subsequent guesses will be roughly 2^63, 2^62, 2^61, 2^60, ..., taking a total of 36 steps to reach the right integer; whereas if you started with 2^33, it takes (by my computation) only 5 steps to get to the right integer. The effect is more significant with larger numbers: arc> (newton-steps (round (* 3/2 (expt 2 1000))) 1) 508 arc> (newton-steps (round (* 3/2 (expt 2 1000))) (expt 2 500)) 8