Writing your own square root function

Question

How do you write your own function for finding the most accurate square root of an integer?

After googling it, I found this (archived from its original link), but first, I didn't get it completely, and second, it is approximate too.

Assume square root as nearest integer (to the actual root) or a float.

Answer 1

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

Answer 2

Depending on your needs, a simple divide-and-conquer strategy can be used. It won't converge as fast as some other methods but it may be a lot easier for a novice to understand. In addition, since it's an O(log n) algorithm (halving the search space each iteration), the worst case for a 32-bit float will be 32 iterations.

Let's say you want the square root of 62.104. You pick a value halfway between 0 and that, and square it. If the square is higher than your number, you need to concentrate on numbers less than the midpoint. If it's too low, concentrate on those higher.

With real math, you could keep dividing the search space in two forever (if it doesn't have a rational square root). In reality, computers will eventually run out of precision and you'll have your approximation. The following C program illustrates the point:

#include <stdio.h>
#include <stdlib.h>

int main (int argc, char *argv[]) {
    float val, low, high, mid, oldmid, midsqr;
    int step = 0;

    // Get argument, force to non-negative.

    if (argc < 2) {
        printf ("Usage: sqrt <number>\n");
        return 1;
    }
    val = fabs (atof (argv[1]));

    // Set initial bounds and print heading.

    low = 0;
    high = mid = val;
    oldmid = -1;

    printf ("%4s  %10s  %10s  %10s  %10s  %10s    %s\n",
        "Step", "Number", "Low", "High", "Mid", "Square", "Result");

    // Keep going until accurate enough.

    while (fabs(oldmid - mid) >= 0.00001) {
        oldmid = mid;

        // Get midpoint and see if we need lower or higher.

        mid = (high + low) / 2;
        midsqr = mid * mid;
        printf ("%4d  %10.4f  %10.4f  %10.4f  %10.4f  %10.4f  ",
            ++step, val, low, high, mid, midsqr);
        if (mid * mid > val) {
            high = mid;
            printf ("- too high\n");
        } else {
            low = mid;
            printf ("- too low\n");
        }
    }

    // Desired accuracy reached, print it.

    printf ("sqrt(%.4f) = %.4f\n", val, mid);
    return 0;
}

Here's a couple of runs so you hopefully get an idea how it works. For 77:

pax> sqrt 77
Step      Number         Low        High         Mid      Square    Result
   1     77.0000      0.0000     77.0000     38.5000   1482.2500  - too high
   2     77.0000      0.0000     38.5000     19.2500    370.5625  - too high
   3     77.0000      0.0000     19.2500      9.6250     92.6406  - too high
   4     77.0000      0.0000      9.6250      4.8125     23.1602  - too low
   5     77.0000      4.8125      9.6250      7.2188     52.1104  - too low
   6     77.0000      7.2188      9.6250      8.4219     70.9280  - too low
   7     77.0000      8.4219      9.6250      9.0234     81.4224  - too high
   8     77.0000      8.4219      9.0234      8.7227     76.0847  - too low
   9     77.0000      8.7227      9.0234      8.8730     78.7310  - too high
  10     77.0000      8.7227      8.8730      8.7979     77.4022  - too high
  11     77.0000      8.7227      8.7979      8.7603     76.7421  - too low
  12     77.0000      8.7603      8.7979      8.7791     77.0718  - too high
  13     77.0000      8.7603      8.7791      8.7697     76.9068  - too low
  14     77.0000      8.7697      8.7791      8.7744     76.9893  - too low
  15     77.0000      8.7744      8.7791      8.7767     77.0305  - too high
  16     77.0000      8.7744      8.7767      8.7755     77.0099  - too high
  17     77.0000      8.7744      8.7755      8.7749     76.9996  - too low
  18     77.0000      8.7749      8.7755      8.7752     77.0047  - too high
  19     77.0000      8.7749      8.7752      8.7751     77.0022  - too high
  20     77.0000      8.7749      8.7751      8.7750     77.0009  - too high
  21     77.0000      8.7749      8.7750      8.7750     77.0002  - too high
  22     77.0000      8.7749      8.7750      8.7750     76.9999  - too low
  23     77.0000      8.7750      8.7750      8.7750     77.0000  - too low
sqrt(77.0000) = 8.7750

For 62.104:

pax> sqrt 62.104
Step      Number         Low        High         Mid      Square    Result
   1     62.1040      0.0000     62.1040     31.0520    964.2267  - too high
   2     62.1040      0.0000     31.0520     15.5260    241.0567  - too high
   3     62.1040      0.0000     15.5260      7.7630     60.2642  - too low
   4     62.1040      7.7630     15.5260     11.6445    135.5944  - too high
   5     62.1040      7.7630     11.6445      9.7037     94.1628  - too high
   6     62.1040      7.7630      9.7037      8.7334     76.2718  - too high
   7     62.1040      7.7630      8.7334      8.2482     68.0326  - too high
   8     62.1040      7.7630      8.2482      8.0056     64.0895  - too high
   9     62.1040      7.7630      8.0056      7.8843     62.1621  - too high
  10     62.1040      7.7630      7.8843      7.8236     61.2095  - too low
  11     62.1040      7.8236      7.8843      7.8540     61.6849  - too low
  12     62.1040      7.8540      7.8843      7.8691     61.9233  - too low
  13     62.1040      7.8691      7.8843      7.8767     62.0426  - too low
  14     62.1040      7.8767      7.8843      7.8805     62.1024  - too low
  15     62.1040      7.8805      7.8843      7.8824     62.1323  - too high
  16     62.1040      7.8805      7.8824      7.8815     62.1173  - too high
  17     62.1040      7.8805      7.8815      7.8810     62.1098  - too high
  18     62.1040      7.8805      7.8810      7.8807     62.1061  - too high
  19     62.1040      7.8805      7.8807      7.8806     62.1042  - too high
  20     62.1040      7.8805      7.8806      7.8806     62.1033  - too low
  21     62.1040      7.8806      7.8806      7.8806     62.1038  - too low
  22     62.1040      7.8806      7.8806      7.8806     62.1040  - too high
  23     62.1040      7.8806      7.8806      7.8806     62.1039  - too high
sqrt(62.1040) = 7.8806

For 49:

pax> sqrt 49
Step      Number         Low        High         Mid      Square    Result
   1     49.0000      0.0000     49.0000     24.5000    600.2500  - too high
   2     49.0000      0.0000     24.5000     12.2500    150.0625  - too high
   3     49.0000      0.0000     12.2500      6.1250     37.5156  - too low
   4     49.0000      6.1250     12.2500      9.1875     84.4102  - too high
   5     49.0000      6.1250      9.1875      7.6562     58.6182  - too high
   6     49.0000      6.1250      7.6562      6.8906     47.4807  - too low
   7     49.0000      6.8906      7.6562      7.2734     52.9029  - too high
   8     49.0000      6.8906      7.2734      7.0820     50.1552  - too high
   9     49.0000      6.8906      7.0820      6.9863     48.8088  - too low
  10     49.0000      6.9863      7.0820      7.0342     49.4797  - too high
  11     49.0000      6.9863      7.0342      7.0103     49.1437  - too high
  12     49.0000      6.9863      7.0103      6.9983     48.9761  - too low
  13     49.0000      6.9983      7.0103      7.0043     49.0598  - too high
  14     49.0000      6.9983      7.0043      7.0013     49.0179  - too high
  15     49.0000      6.9983      7.0013      6.9998     48.9970  - too low
  16     49.0000      6.9998      7.0013      7.0005     49.0075  - too high
  17     49.0000      6.9998      7.0005      7.0002     49.0022  - too high
  18     49.0000      6.9998      7.0002      7.0000     48.9996  - too low
  19     49.0000      7.0000      7.0002      7.0001     49.0009  - too high
  20     49.0000      7.0000      7.0001      7.0000     49.0003  - too high
  21     49.0000      7.0000      7.0000      7.0000     49.0000  - too low
  22     49.0000      7.0000      7.0000      7.0000     49.0001  - too high
  23     49.0000      7.0000      7.0000      7.0000     49.0000  - too high
sqrt(49.0000) = 7.0000

Answer 3

A simple (but not very fast) method to calculate the square root of X:

squareroot(x)
    if x<0 then Error
    a = 1
    b = x
    while (abs(a-b)>ErrorMargin) 
        a = (a+b)/2
        b = x/a
    endwhile
    return a;

Example: squareroot(70000)

    a       b
    1   70000
35001       2
17502       4
 8753       8
 4381      16
 2199      32
 1116      63
  590     119
  355     197
  276     254
  265     264

As you can see it defines an upper and a lower boundary for the square root and narrows the boundary until its size is acceptable.

There are more efficient methods but this one illustrates the process and is easy to understand.

Just beware to set the Errormargin to 1 if using integers else you have an endless loop.