# square root algorithm???

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 12-28-2004
Emotions
square root algorithm???
I am building a calculator and already have addition, subtraction, multiplication, division, squaring a number, and I want to add in the square root function. The only problem is I don't know what the formula or whatever its called is for finding the square root of a number. Does anyone know it? I figured out if you could multiply 64 by .125 and it gives you 8 but that doesn't work for all numbers such as 49. So if someone could tell me the formula I would be greatly appreciated. Thanks alot.
• 12-28-2004
Epo
One way to do it is to start with a guess, and work your way down....for example...say you want to get the square root of 64.

You guess it to be 10 (doesn't really matter what the guess is to start), but 10 squared is 100, so the real root must be smaller.

Your next guess is half of 10; 5. 5 squared is 25, too small, so now pick between 5 and 10.

7.5 squared is 56.25, too small. Now pick halfway between 7.5 and 10; 8.75.

8.75 squared is too large...

7.5 and 8.75: 8.125
7.5 and 8.125: 7.8125
7.8125 and 8.125: 7.96875

...Keep doing this...

Do this a couple of thousand times, and you're bound to be very very close.
• 12-28-2004
Thantos
http://www.rism.com/Trig/square.htm

In my c++ class we basically did a binary search for the number. You use a precision const to let you know when you are close enough.

You set your high mark (the number you are looking for) and your low mark (1). If the number is 0<x<1 then you switch it so the high is 1 and the low is the number

Take the mid point. Square it. If its within your precision to the number you are looking for use that. If not: If its too large set your new high to be that mid point. If too low set your low mark to that mid point. continue
• 12-28-2004
Emotions
How can I turn that into something the calculator can perform? I want it to be so the user can input a number and it tells the answer. But I can't think of any sort of set formula. I did some research on google, but I got basically what you said about the guess and estimate etc. way. But the only way to get that to work would be to make the computers first guess to always be 10 or some number then it return if it was true or not and if so let that be the answer and if not to return it was higher or lower. If it was higher take half of that number like you did and repeat until it gives me only an estimate. But that would take a crapload of code. I was wondering if any of you had like a set formula of how to do it or if the estimating is the only way. How does a regular calculator do it. Like the computer calculator.
• 12-28-2004
Salem
> But that would take a crapload of code.
They're called loops.

Here's one very crude loop.
Code:

```int num = 49;  // the num you want a root of int root = 0; // the answer while ( root * root < num ) root++;```
> or if the estimating is the only way
Yeah, read the previously posted link and study Newton's method. It is an iterative procedure (that means you need a while loop).
• 12-28-2004
Thantos
Quote:

But that would take a crapload of code.
I just looked at my program. Over two functions (one interface and one worker) with liberal use of white space it was 40 lines.
• 12-29-2004
nvoigt
Well, you could use the sqrt function in <math.h>... but that's not as much fun and not as rewarding as doing it yourself :)
• 12-29-2004
Sang-drax
To find te square root of a number C is equivalent to solving the following equation:

x^2 - C = 0

If x is an approximation of the square root then, according to Newton's algorithm, a better approximation can be obained with the following formula:

xBetter = x - (x^2 - C)/(2x) = (x - C/x)/2

This is a pretty good method.
• 12-29-2004
LuckY
It's funny you mention this. I just implemented a square root function on our system here at work using Newton's Iteration.

The formula, simplified, is: Xn = (Xn-1 + Y/Xn-1) / 2, where X0 = 1
(those are "x sub n" and "x sub n minus one")

So you just loop from n = 1 upward. The further you go, the more precise your result. So, for a simple example, to determine sqrt(81):
X1 = (X0 + 81/X0) / 2 --> (1 + 81/1) / 2 --> 41
X2 = (41 + 81/41) / 2 = 21.49
X3 = (21.49 + 81/21.49) / 2 = 12.63
X4 = (12.63 + 81/12.63) / 2 = 9.52
X5 = (9.52 + 81/9.52) / 2 = 9.02
X6 = (9.02 + 81/9.02) / 2 = 9.00

That should give you a clear idea of how it works. It's basically what Sang-drax said, but a with a little more detail.
• 12-29-2004
Emotions
I don't quite understand how to put what you said lucky into a loop. I had already written this before I read your post, but it doesn't work right. I was wondering if this could work and if it could whats wrong with it. If not could you give a brief description of what I need to do for the loop. This square root this is basically me trying to learn loops better. But anyways here is the code I wrote.

Code:

```#include <iostream> #include <stdlib.h> using namespace std; int main() {  int theirNumber;  int theAnswer = 1;      cout<<"Please enter a number that you would like to find the square root of"<<endl;  cin>> theirNumber;  /*this loop if coded properly will find the square root of any number the  user inputs into the calculator*/   do   {   if (theAnswer * theAnswer < theirNumber)        /*this should continue to increase theAnswer by 1 until it finds the correct answer*/   {                                                  theAnswer++;    }   else if (theAnswer * theAnswer > theirNumber) //this should continue to decrease theAnswer by 1 until it finds the correct answer   {     theAnswer--;   }   else if(theAnswer * theAnswer == theirNumber) //is theAnswer times itself equals the number the user input then it should output theAnswer to the problem   {     cout<<"The square root of: "<<theirNumber<<" is: "<<theAnswer<<endl;   }   }while (theAnswer * theAnswer != theirNumber);                   system("PAUSE");          return 0; }```

It compiles fine, but all it does is ask for the number and when I input a number such as 49 it just goes straight to "Press any key to continue..." and then it exits. I'm a little confused can someone help me out.
• 12-29-2004
LuckY
To be clear, you are not implementing the algorithm Sang-drax and I spoke of. Your problem is one of logic. Once you reach theAnswer = 7 in your first if statement the while test will evaluate to false and the loop will end without ever printing anything. Just remove the else from your third if statement so it will check every time through if you've found the right number.

You should understand that this will work only for any number that has an even square root. If not you will just loop forever.

Here is Newton's iteration.
Code:

```#include <iostream> #include <cstdlib> using namespace std; int main() {   float theirNumber;   float theAnswer = 1.0;// note we want decimal precision     cout << "Please enter a number that you would like to find the square root of" << endl;   cin >> theirNumber;   /* 100 is arbitrary overkill here; we are just seeking accuracy */   for (int i = 0; i < 100; ++i)     theAnswer = (theAnswer + (theirNumber / theAnswer)) / 2;     cout << "The square root of " << theirNumber << " is " << theAnswer << endl;   return 0; }```
• 12-29-2004
Emotions
That works great. Thanks. The next thing I want to do is have the program keep repeating after it does a problem. I want to enter an exit choice that when you choose it will exit, but otherwise the program will repeat. So after you pick square root and you find the square root of 49 is 7 it will ask "What would you like to do?"And present the menu again. I figure it is a loop but for I loop the whole thing or what?

Code:

```#include <iostream> #include <stdlib.h> #include <string> using namespace std; int main() {   float first;   float second;   float theirNumber;   float theAnswer = 1.0;   int choice;     cout<<"Please choose the operation you would like to perform.\n"       <<"1)Addition\n"       <<"2)Subtraction\n"       <<"3)Multiplication\n"       <<"4)Division\n"       <<"5)Square the number\n"       <<"6)Square root\n"       <<"7)Exit"<<endl;         cin>> choice;     switch(choice)   {     case 1:       cout<<"Please enter the first number."<<endl;       cin>> first;       cout<<"Please enter the second number."<<endl;       cin>> second;       cout<<"The answer is: "<<(first + second)<<endl;     break;         case 2:       cout<<"Please enter the first number."<<endl;       cin>> first;       cout<<"Please enter the second number."<<endl;       cin>> second;       cout<<"The answer is: "<<(first - second)<<endl;     break;         case 3:       cout<<"Please enter the first number."<<endl;       cin>> first;       cout<<"Please enter the second number."<<endl;       cin>> second;       cout<<"The answer is: "<<(first * second)<<endl;     break;         case 4:       cout<<"Please enter the first number."<<endl;       cin>> first;       cout<<"Please enter the second number."<<endl;       cin>> second;       cout<<"The answer is: "<<(first / second)<<endl;     break;         case 5:       cout<<"Please enter the first number."<<endl;       cin>> first;       cout<<"The answer is: "<<(first * first)<<endl;     break;         case 6:       cout<<"Please enter the number you would like to find the square root of."<<endl;       cin>> theirNumber;       for (int i = 0; i < 100; ++i)       {         theAnswer = (theAnswer + (theirNumber / theAnswer)) / 2;       }       cout<<"The square root of "<<theirNumber<<" is "<<theAnswer<<endl;     break;           case 7:       return 0;     break;         default:       cout<<"Your input was invalid."<<endl;   }       system("PAUSE");          return 0; }```
I have the exit there. But I don't know how I can get it to do the repeat.
• 12-29-2004
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
• 12-29-2004
Emotions
I got it. I add a Do...While loop in there. I added int loopcount. So I have everything defined and then my code is surrounded by a do....while (loopcount > 0); and inside my code I never stated to increase or decrease my loopcount so it should run infinitly. But when I hit the exit number it still exits immediately. So it is all worked out. Thanks for all the help.
• 12-29-2004
Kybo_Ren
I saw this thread and immediately thought of Newton's Iteration.

This is the fastest and most precise method you can use. Go with LuckY on this one.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last