square root algorithm???

This is a discussion on square root algorithm??? within the C++ Programming forums, part of the General Programming Boards category; I am building a calculator and already have addition, subtraction, multiplication, division, squaring a number, and I want to add ...

  1. #1
    Registered User
    Join Date
    Dec 2004
    Posts
    31

    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.

  2. #2
    Epo
    Epo is offline
    Registered User
    Join Date
    Jun 2003
    Posts
    361
    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.
    Pentium 4 - 2.0GHz, 512MB RAM
    NVIDIA GeForce4 MX 440
    WinXP
    Visual Studio .Net 2003
    DX9 October 2004 Update (R.I.P. VC++ 6.0 Compatability)

  3. #3
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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

  4. #4
    Registered User
    Join Date
    Dec 2004
    Posts
    31
    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.

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,506
    > 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).

  6. #6
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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.

  7. #7
    the hat of redundancy hat nvoigt's Avatar
    Join Date
    Aug 2001
    Location
    Hannover, Germany
    Posts
    3,139
    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
    hth
    -nv

    She was so Blonde, she spent 20 minutes looking at the orange juice can because it said "Concentrate."

    When in doubt, read the FAQ.
    Then ask a smart question.

  8. #8
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    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.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  9. #9
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    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.

  10. #10
    Registered User
    Join Date
    Dec 2004
    Posts
    31
    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.

  11. #11
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    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. #12
    Registered User
    Join Date
    Dec 2004
    Posts
    31
    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.
    Last edited by Emotions; 12-29-2004 at 12:17 PM.

  13. #13
    Registered User
    Join Date
    Nov 2004
    Posts
    86
    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

  14. #14
    Registered User
    Join Date
    Dec 2004
    Posts
    31
    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.
    Last edited by Emotions; 12-29-2004 at 12:38 PM.

  15. #15
    Registered User Kybo_Ren's Avatar
    Join Date
    Sep 2004
    Posts
    136
    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.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Forced moves trouble!!
    By Zishaan in forum Game Programming
    Replies: 0
    Last Post: 03-27-2007, 06:57 PM
  2. Bisection Method function value at root incorrect
    By mr_glass in forum C Programming
    Replies: 3
    Last Post: 11-10-2005, 08:10 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 01:24 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21