Thread: square root algorithm???

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.

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

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.

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.

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;
}

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.

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.