Writing your own square root function

by

The following computes floor(sqrt(N)) for N > 0:

x = 2^ceil(numbits(N)/2)
loop:
    y = floor((x + floor(N/x))/2)
    if y >= x
        return x
    x = y

This is a version of Newton’s method given in Crandall & Pomerance, “Prime Numbers: A Computational Perspective”. The reason you should use this version is that people who know what they’re doing have proven that it converges exactly to the floor of the square root, and it’s simple so the probability of making an implementation error is small. It’s also fast (although it’s possible to construct an even faster algorithm — but doing that correctly is much more complex). A properly implemented binary search can be faster for very small N, but there you may as well use a lookup table.

To round to the nearest integer, just compute t = floor(sqrt(4N)) using the algorithm above. If the least significant bit of t is set, then choose x = (t+1)/2; otherwise choose t/2. Note that this rounds up on a tie; you could also round down (or round to even) by looking at whether the remainder is nonzero (i.e. whether t^2 == 4N).

Note that you don’t need to use floating-point arithmetic. In fact, you shouldn’t. This algorithm should be implemented entirely using integers (in particular, the floor() functions just indicate that regular integer division should be used).

More Related Contents:

  1. Calculate distance between two latitude-longitude points? (Haversine formula)
  2. Unique (non-repeating) random numbers in O(1)?
  3. How to determine if a point is in a 2D triangle? [closed]
  4. Algorithm to find Largest prime factor of a number
  5. How to make rounded percentages add up to 100%
  6. Sort points in clockwise order?
  7. How do you calculate the average of a set of circular data? [closed]
  8. How do Trigonometric functions work? [closed]
  9. Precise subpixel line drawing algorithm (rasterization algorithm)
  10. Finding out nth fibonacci number for very large ‘n’
  11. Algorithm for finding similar images
  12. Why does this simple shuffle algorithm produce biased results?
  13. Mapping N-dimensional value to a point on Hilbert curve
  14. What’s a good algorithm to determine if an input is a perfect square? [duplicate]
  15. Floating Point Divider Hardware Implementation Details
  16. nᵗʰ ugly number
  17. Unsupervised clustering with unknown number of clusters
  18. Calculate largest inscribed rectangle in a rotated rectangle
  19. Two Rectangles intersection
  20. Fastest primality test
  21. Circle-circle intersection points
  22. Efficient maths algorithm to calculate intersections
  23. How do I find a factorial? [closed]
  24. Calculating the position of points in a circle
  25. Strategies for simplifying math expressions
  26. How to express tetration function, for complex numbers
  27. An inverse Fibonacci algorithm?
  28. How to check if an integer is a power of 3?
  29. Optimized low-accuracy approximation to `rootn(x, n)`
  30. How can I perform Collision Detection on rotated rectangles? [closed]

Leave a Comment