# square root algorithm???

Show 80 post(s) from this thread on one page
Page 2 of 2 First 12
• 12-29-2004
Emotions
LuckY nailed this one. It was less code than I thought there would be. What would I need to learn to make it graphical? Like have a square calculator pop up when I run the .exe file with buttons for each number a a screen that displays what you are entering. Basically just like the windows calculator. Would that deal with OpenGL or what?
• 12-29-2004
prog-bman
There are many options for making it graphical. You could go with poratble solutions like OpenGl, SDL, Allegro, wxWindows,... or if your working in windows use win32 API. But first I would make sure I have a functional program then worring about adding a gui.
• 12-29-2004
Finchie_88
From the laws on indices, the square root of a number is that number to the power of a half, so, what is wrong with this code, because for some reason, the answer is always 2, it might be the ^, I think that is the power operator, from what is happening, I think it might mean something different...

Code:

```int x;     int funct;     funct = x^(1/2);     cout << "Please input a number:" << endl;     cin >> x;     cout << funct << endl;```
• 12-29-2004
jlou
^ is not the power operator, it is the bitwise exclusive or operator.

Besides, you never initialize x before using it so it wouldn't work anyway. ;)
• 12-29-2004
prog-bman
The ^ is not the power operator it's the bitwise OR.
• 12-29-2004
Bajanine
Power function is like so: double pow(double x, double y);

But I think this takes the fun out of it so to speak. Here is another method although it is more convoluted than the previous example given by Sang-drax :D .
• 12-29-2004
homeyg
There is also a way to find square roots that I don't think is very well known, it works sort of like long division.

Here is a picture of what I'm talking about. Has anyone else seen this method? (I mean, I asked my math teacher about it and he said he'd never 'seen such a thing'.) I use it all the time. I think it would be pretty easy to program. (PM me if you can't figure out how it works, it's to long to describe here)

Dang it! The post above me beat me to it!
• 12-30-2004
LuckY
I actually also implemented that algorithm. I have found, however, that it is not very accurate beyond 5 decimal digits. After that things go downhill and fast.
• 12-30-2004
Sang-drax
You don't have to iterate Newton's algoritm 100 times.

When the algorithm converges (it always does in this case), it does so quadratically = quite fast.

Try around 10 iterations. This is just a suggestion, I don't know if speed matters to you.
• 12-30-2004
sand_man
Carmack's inverse sqrt

Code:

```float InvSqrt (float x) {     float xhalf = 0.5f*x;     int i = *(int*)&x;     i = 0x5f3759df - (i >> 1);     x = *(float*)&i;     x = x*(1.5f - xhalf*x*x);     return x; }```
• 12-31-2004
Thantos
always a fun time:
Code:

```std::complex<double> mysqrt(double num, const double precision = 0.0000001); std::complex<double> mysqrt(double num, const double precision ) {   bool real = true;   if ( num < 0.0 )   {     real = false;     num = -num;   }   double root = 1.0;   while ( fabs((root * root) - num) > precision )     root = (root + (num/root)) / 2;   if ( real )     return std::complex<double>(root,0);   return std::complex<double>(0,root); }```
Edit: Credit to LuckY for the
Code:

`root = (root + (num/root)) / 2;`
• 12-31-2004
Micko
Yes, I agree with Sang-drax and Lucky. It's best to use Newton-Raphson method.
I'd like to mathematically clearify what is going on, maybe someone will find it useful.
Basically we want to solve equation f(x)=x^2-C=0;
Consider function f(x) on interval [A,B]. Assume that exists n-th derivation of function f(x) in point a where a is from interval [A,B].
First derivation is labeled f'(x)
Second derivation is labeled f''(x)... and so on

In mathematical analysis function f(x) can be represent with the following series:
f(x)=f(a)+f'(a)(x-a)+f''(x)(x-a)^2/2!+....
First approximation (linear) is:

f(x)~=f(a)+f'(a)(x-a) (sign '~=' is aproximation of '=').

If e is root of equation f(x)=0 ( f(e)=0 ) then we have:

f(e)~=f(a)+f'(a)(x-a) =>
0~=f(a)+f'(a)(x-a) =>

x=a-f(a)/f'(a).
Now we can form an iterative procedure:
x(k)=x(k-1)+f(x(k-1))/f'(x(k-1))
Now we need to choose start value x(0) and start calculating x(1),x(2),...
Of coures there are conditions which must be satisfied for this series to converge ( in this case it always does ) but it would took too much time and complex math to explain. This algorithm converge quadratically.

When calculating roots of equation x^2-C=0 according to procedure above we have:
x(k)=x(k-1)-(x(k-1)^2-C)/(2*x(k-1)) =>

x(k)=x(k-1)-(x(k-1)-C/x(k-1))/2; (Lucky's formula)
This is called Newton-Raphson method and also tangent method

To understand clearly what is going on you could look at the attached picture.
Now you can see why this algorithm converge quadratically (very very fast) so it's much better to define precision first (or number of exacts decimal digits in solution) example if x(k)-x(k-1)<=eps where eps is 10^(-7) that means we'll have 7 exact decimal digits (digits after decimal point) in solution. So criteria for stopping calculation could be |x(k)-x(k-1)|< eps.

Choosing start velue has big influence on number of iterations. It's always good to choose start value closer to actual solution!

Hope someone will find this useful.

P.S. Sorry because of bad English.
• 12-31-2004
Darkness
Excellent explanation Micko.

This is just another implementation of the newtonian approximation algorithm. I wrote this as a part of my math library. It works, but it's not really faster than crt sqrt much less the sqrt method on your floating point unit (you can't realistically beat hardware). If you need to also balance speed you can actually download the doom3 sdk as I believe it contains methods for using the approximation algorithm with a clever way of finding the seed (initial guess)...this is used in the lighting algorithms.

so, here's my implementation:
Quote:

float IterSqrtf(float r, int numtries)
{
float m(0.0f);
float b(0.0f);
float currx=r;
float curry(0.0f);
float root(0.0f); //this is what gets returned

while(numtries--)
{
curry = (currx*currx) - r; //y1
//Check to see if curry is < 0
m = 2 * currx;
b = (-m*currx) + curry;
root = -b / m;
currx = root;
}
return root;
}
Here's an implementation from tricks of the 3d game programming gurus...it's faster than sqrt() and is always within 5% accuracy

Quote:

float Faster_Sqrtf(float f)
{
float result;

_asm
{
mov eax, f
sub eax, 0x3f800000
sar eax, 1
mov result, eax
}

return result;
}
• 12-31-2004
misplaced
Quote:

Originally Posted by pktcperlc++java
the way I did this for my own calculator was through a for loop

Code:

```for(int i=0;pow(i,2)<number;i+=0.001){ //do nothing inside loop }//end for```
the +=0.001 ends up being formated by the compiler as a huge string of decimals and it can always be formated later in the code

a bit off topic:
this
for(int i=0;pow(i,2)<number;i+=0.001);
works without the {} and is more readable
Show 80 post(s) from this thread on one page
Page 2 of 2 First 12