Code Snippets

  

C++ Source Code


Welcome to Dream.In.Code
Getting C++ Help is Easy!

Join 118,589 C++ Programmers for FREE! Ask your question and get quick answers from experts. There are 814 online right now! We've got more than 500 tutorials and 2,000 snippets. Join and find out why Dream.In.Code is the #1 programming help community on the internet! Registration is fast and FREE... Join Now!




Finding Square Root without using sqrt()

This code shows how to find out the square root of a number without using the sqrt() function. The result obtained by both functions are the same and hence can also be used as an alternative sqrt() function.

Submitted By: born2c0de
Actions:
Rating:
Views: 28,079

Language: C++

Last Modified: August 20, 2005

Snippet


  1. /*          Code written by Sanchit Karve
  2.                   A.K.A born2c0de
  3.                   Contact Me at born2c0de AT hotmail.com
  4.                   20 August, 2005
  5. */
  6.  
  7.  
  8.  
  9.  
  10. #include <iostream>
  11. #include <math.h>
  12.  
  13. using namespace std;
  14.  
  15.  
  16. float sqroot(float m)
  17. {
  18.      float i=0;
  19.    float x1,x2;
  20.    while( (i*i) <= m )
  21.           i+=0.1;
  22.    x1=i;
  23.    for(int j=0;j<10;j++)
  24.    {
  25.         x2=m;
  26.       x2/=x1;
  27.       x2+=x1;
  28.       x2/=2;
  29.       x1=x2;
  30.    }
  31.    return x2;
  32. }
  33.  
  34. int main()
  35. {
  36.    cout<<"Enter a Number:";
  37.    int no;
  38.    cin>>no;
  39.      cout<<"Square Root using sqroot()= "<<sqroot(no)<<endl
  40.        <<"Square Root using sqrt()  = "<<sqrt(no);
  41.  
  42.    return 0;
  43. }
  44.  

Copy & Paste


Comments


bodom658 2008-03-05 20:21:48

very cool! thanks for sharing!

mikeblas 2008-04-20 13:25:58

I suppose this method kind of works, but, WOW, is it slow! You start at 0, then multiply 0*0 to find that it's less than m. Then, you add 0.1, multiplying that times itself -- you get 0.01, and it's still less than m. You keep adding 0.1 to your candidate root until it's greater than m when squared... then use that as your starting point for ten iterations of approximation. What if m is 750,000,000 ? It will take you more than 270,000 multiplications to find the answer.

born2c0de 2008-04-21 04:23:44

Yes, it will. It uses a method of approximations and has that limitation. All approximation algorithms have that property, including Newton Raphson's, Runge Kutta's etc.

trbot 2008-06-10 11:32:34

I suspect this method would gain much, in the processing of large numbers, by taking a page from the book of binary algorithms. If, instead of adding 0.1 each time, you added 0.1, 0.2, 0.4, 0.8, 1.6, doubling each time, and then, after exceeding m, subtracted half of the largest value originally added, halfing this value and subtracting successively until you are below m, halfing it and adding until you are above m, ..., you can iteratively narrow the margin of error until (i*i - m < 0.1) to come up with the same result in a O(log n) algorithm. For small numbers there will be some overhead (to avoid this, use an if statement to select the appropriate algorithm based on a threshold), but for big numbers, you will cut running-time significantly. m = 750,000,000 would originally take 273,862 add/mult over lines 22 and 23. With the algorithm I have described, it will take 68 add, 34 mult/div.

phauline 2008-09-02 02:55:09

excellent!

David W 2008-10-07 03:54:53

very inaccurate for values from 0 to 0.000001


Add comment


You must be registered and logged on to </dream.in.code> to leave comments.





Live C++ Help!

C++ Tutorials

Reference Sheets

C++ Snippets

Bye Bye Ads

Free DIC T-Shirt

T-Shirt Example

Related Sites

Monthly Drawing

Thumb Drive

Partners

Top Contributors

Top 10 Kudos This Month