Homemade Square Roots

**MisterWonderful** · 02-29-2004

Okay, I'm aware that this is highly inefficient, that this is reinventing the wheel, etc., etc. ; however, I'm a curious guy, and I'd like to be able to say that I could write my own square root function before using the compiler's. But I'm getting nowhere as to thinking up just how to do something like that. Any ideas? Thanks.

**undisputed007** · 02-29-2004

look

Code:

#include<iostream>
#include<cmath>
using namespace std;

int main()
{
int n;

cout<<"enter the number:\n ";
cin>>n;
cout<<"the square root is :" <<sqrt(n)<<endl;

return 0;
}

but if you mean without using this function sqrt i dont know and i hope to know it too

**laserlight** · 02-29-2004

Do you know any algorithms?

**joshdick** · 02-29-2004

Those algorithms look like a bit much. I'd say take a look at Newton's Method. It was covered in my high school calculus class, so I don't think it's too difficult to grasp.

**Iamien** · 02-29-2004

i dont remember the exact way. google square root without calculator. it is wierd. i can't explain

**Lurker** · 02-29-2004

num^.5

It doesn't really help, but it isn't using the sqrt function!

**MisterWonderful** · 02-29-2004

Thanks for all of the input. No, unfortunately I'm not too familiar with algorithms, but I'd love to learn about them.

One thing I do remember from 8th grade algebra is a trial-and-error method of getting a square root, come to think of it. You'd guess what whole number would go into it squared, and then tenth place, etc. etc., and I was thinking there must be some intricate for() loop thing that a person could do to keep narrowing it down to say, 3 decimal places.

**Prelude** · 02-29-2004

Here's a simple and naive algorithm...

Code:

double square_root ( double value )
{
  double result = .00001;

  while ( result * result < value )
    result += .00001;

  return result;
}

**Lurker** · 02-29-2004

Fastest algorithm: lookup tables. Of course, they aren't that useful either in some cases

.

**sean** · 03-01-2004

I replied to a post about how to convert square root function calls into something like 3 times the square root of 5. SO what you could do, is use the tables method, but reduce it down to just the prime numbers, etc.. That way, you just use the same rules to smplify the paramter, like factoring out and then extracting duplicates, and then multiply by the answer you get in the table for the simplified radical.

**MisterWonderful** · 03-03-2004

Firstly, I thank everyone who offered their input.

Secondly— I conferred with a mathematically-gifted friend of mine, and researched the matter online. I found a whole bunch of methods, including the Newton Method, Bisection Method, and an ancient technique called the Bahkshali formula. Now I just need to figure out how to implement these in C++.

Bahkshali formula:

sqrt(Q) = sqrt(A^2 + b) =
A + b/ (2A) - (b/ (2A) )^2/ [2(A + b/ (2A) ) ]

• Where A = largest perfect square that will go
into Q, and b = remainder

Bisection Method:

1) Factor. 2) Find 2 closest factors.

3) Avg. the 2. 4) Div. orig. # by avg.

5) Repeat 3-4 to desired accuracy.

Ex.) 500 = 10 • 50 avg = 30

500 / 30 = 50/3 avg (30, 50/3) = 70/3

500 / (70/3) = 150/7 avg (70/3, 150/7) ≈
22.381
500/22.381 ≈ 22.340

500 ≈ (22.381)(22.340)

If I remember correctly, the Bahkshali formula is accurate to the hundred-thousandth's place, and Bisection is accurate to whatever degree you choose to take it to.

Check out URL=http://mathforum.org/library/drmath/sets/high_square_roots.html]Ask Dr. Math[/URL] to see a whole these and a whole lot more algorithms.

**Zach L.** · 03-03-2004

Been a while since I did numerical methods, but I'm fairly sure that Newton-Raphson converges much more quickly than Bisection. The reason Bisection is sometimes better is that NR can easily go off on tangents (literally) and get itself lost or stuck in a loop with poorly chosen functions. For a square root, however, the function is: f(x) = x^2 - n, where n is the numer whose root you are trying to find, and NR will work just fine on this function.

**chrismiceli** · 03-03-2004

Originally posted by Prelude

Here's a simple and naive algorithm...

Code:

double square_root ( double value )
{
  double result = .00001;

  while ( result * result < value )
    result += .00001;

  return result;
}

I hope you were joking

.

**Prelude** · 03-03-2004

>I hope you were joking
Everything I say is a joke.

Thread: Homemade Square Roots

Thread Tools

Search Thread

Display

Homemade Square Roots

Many Thanks, and a Follow-up

Similar Threads

Forced moves trouble!!

Help with my draughts game

Simplifing Square Roots

for loops using square roots, square, Cube

Square roots / Powers etc.