How do you write your own function for finding the most accurate square root of an integer?
After googling it, I found this, but firstly, I didn't get it completely, and secondly, it is approximate too.
Assume square root as nearest integer (to the actual root) or a float.
Of course it's approximate; that is how math with floating-point numbers work.
Anyway, the standard way is with Newton's method. This is about the same as using Taylor's series, the other way that comes to mind immediately.
In general the square root of an integer (like 2, for example) can only be approximated (not because of problems with floating point arithmetic, but because they're irrational numbers which can't be calculated exactly).
Of course, some approximations are better than others. I mean, of course, that the value 1.732 is a better approximation to the square root of 3, than 1.7
The method used by the code at that link you gave works by taking a first approximation and using it to calculate a better approximation.
This is called Newton's Method, and you can repeat the calculation with each new approximation until it's accurate enough for you.
In fact there must be some way to decide when to stop the repetition or it will run forever.
Usually you would stop when the difference between approximations is less than a value you decide.
EDIT: I don't think there can be a simpler implementation than the two you already found.
Let me point out an extremely interesting method of calculating an inverse square root 1/sqrt(x) which is a legend in the world of game design because it is mind-boggingly fast. Or wait, read the following post:
http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/
PS: I know you just want the square root but the elegance of quake overcame all resistance on my part :)
By the way, the above mentioned article also talks about the boring Newton-Raphson approximation somewhere.
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.
Depending on you needs, a simple divide-and-conquer strategy can be used. It won't converge as fast as some other methods but it may be 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
The first thing comes to my mind is: this is a good place to use Binary search (inspired by this great tutorials.)
To find the square root of vaule ,we are searching the number in (1..value) where the predictor
is true for the first time. The predictor we are choosing is number * number - value > 0.00001.
double sqaure_root_of(double value)
{
assert(value >= 1);
double lo = 1.0;
double hi = value;
while( hi - lo > 0.00001)
{
double mid = lo + (hi - lo) / 2 ;
std::cout << lo << "," << hi << "," << mid << std::endl;
if( mid * mid - value > 0.00001) //this is the predictors we are using
{
hi = mid;
} else {
lo = mid;
}
}
return lo;
}
#!/usr/bin/env python
import decimal
def sqrt(n):
assert n > 0
with decimal.localcontext() as ctx:
ctx.prec += 2 # increase precision to minimize round off error
x, prior = decimal.Decimal(n), None
while x != prior:
prior = x
x = (x + n/x) / 2 # quadratic convergence
return +x # round in a global context
decimal.getcontext().prec = 80 # desirable precision
r = sqrt(12345)
print r
print r == decimal.Decimal(12345).sqrt()
Output:
111.10805551354051124500443874307524148991137745969772997648567316178259031751676
True
As expected, most people here are suggesting various semi-broken or slow methods that they saw on a blog somewhere, so let me give you a proper algorithm. 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).
Found a great article about Integer Square Roots.
The final algorithm that it showed was. It should be pretty quick.
unsigned short sqrt(unsigned long a){
unsigned long rem = 0;
unsigned long root = 0;
for (int i = 0; i < 16; i++){
root <<= 1;
rem = ((rem << 2) + (a >> 30);
a <<= 2;
root ++;
if(root <= rem){
rem -= root;
root ++;
}
else
root --;
}
return (unsigned short)(root >> 1);
}
The inverse, as the name says, but sometimes "close enough" is "close enough"; an interesting read anyway.