Square root of a number.

P

priyam.trivedi

Hi!

Could anyone tell me how to find the square root of a number without
using the sqrt function. I did it by using Newton's Formula. How can it
be done by using the Binomial Theorem/Taylor Series? Is there any other
way of doing it rather than using series?

Thank you,

Priyam
 
K

Keith Thompson

Could anyone tell me how to find the square root of a number without
using the sqrt function.

Why? Is there something wrong with the sqrt function?

In any case, I don't think your question is particularly about C.
You might try comp.programming or one of the math.* groups.
 
O

osmium

Could anyone tell me how to find the square root of a number without
using the sqrt function. I did it by using Newton's Formula. How can it
be done by using the Binomial Theorem/Taylor Series? Is there any other
way of doing it rather than using series?

You can do it the way that used to be taught in elementary school.
 
C

Christian Bau

Hi!

Could anyone tell me how to find the square root of a number without
using the sqrt function. I did it by using Newton's Formula. How can it
be done by using the Binomial Theorem/Taylor Series? Is there any other
way of doing it rather than using series?

The usual method is to calculate sqrt (1 / x) first using Newton
iteration, because it can be done in a form that doesn't need any slow
divisions; then multiply the result by x,

On a computer without floating point unit, a reasonable approach is to
find a square root similar to performing a division: sqrt (x) = x / sqrt
(x), only modifying the remainder and the divisor after each digit of
the result is found.
 
W

websnarf

Could anyone tell me how to find the square root of a number without
using the sqrt function. I did it by using Newton's Formula. How can it
be done by using the Binomial Theorem/Taylor Series? Is there any other
way of doing it rather than using series?

Everything you ever wanted to know about square roots but were afraid
to ask:

http://www.pobox.com/~qed/sqroot.html

I never thought of using the Binomial Theorem. I guess you would
normalize the exponent so that you could try to expand:

(1 + x) ^ 0.5 = 1 + Choose(0.5,1) * x + Choose(0.5,2) * x^2 + ...

were Choose(r,i) = r*(r-1)*(r-2)* ... * (r-i+1) / i!

This works directly for 1 <= r < 2. If we have 2 <= r < 4 then you can
compute the square root of the reciprocal and reciprocate it again at
the end.

But in general Taylor series like expansions are going to be slower
than the other calculating methods. Even the digit by digit methods
use fewer resources per digit.
 
M

Malcolm

Hi!

Could anyone tell me how to find the square root of a number without
using the sqrt function. I did it by using Newton's Formula. How can it
be done by using the Binomial Theorem/Taylor Series? Is there any other
way of doing it rather than using series?
You are passed a positive real number.
You know that the square root cannot be less than zero, and cannot be
greater than the number itself.
Take the number halfway between (half the number you are passed) and
multiply it by itself. If it is equal to the number, you have your answer.
If it is too low, you have a new minimum, if it is too high, you have a new
maximum.
Repeat with these limits, until you either get the answer or hit the
floating point accuracy of the machine - this will happen quite quickly even
for huge arguments.

This isn't the most sophisticated algorithm, but it will work.
 
R

Richard Heathfield

Malcolm said:
You are passed a positive real number.
You know that the square root cannot be less than zero, and cannot be
greater than the number itself.

double root = malcolmsqrt(0.25);

Oops.
 
R

Richard Heathfield

pete said:
The square root of N
Is in between N and one
Except for zero

If N and one are included in the range, then it works for zero too. And if
they're not, it doesn't work for one.
 
C

CBFalconer

Malcolm said:
You are passed a positive real number.
You know that the square root cannot be less than zero, and
cannot be greater than the number itself.
Take the number halfway between (half the number you are passed)
and multiply it by itself. If it is equal to the number, you
have your answer. If it is too low, you have a new minimum, if
it is too high, you have a new maximum.
Repeat with these limits, until you either get the answer or
hit the floating point accuracy of the machine - this will
happen quite quickly even for huge arguments.

This isn't the most sophisticated algorithm, but it will work.

After the initial guess (which should be 1 + N) this is effectively
Newton-Raphson.

guessnplus1 = 1/2 * (guessn + N/guessn);

or, in C:

guess = N + 1.0;
do {
lastguess = guess;
guess = 0.5 * (guess + N / guess);
} while ( /* not converged */ );

and I leave you to fabricate code for "not converged". Beware
small oscillations, and it may be advisable to involve epsilon.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
 
J

Jordan Abel

Ben Pfaff said:


A better haiku
Would get the mathematics
Absolutely right.

What's wrong with saying that the value is between N and 1, if you grant
"between" being inclusive and a particular definition of "between" to
apply to complex numbers?
 
M

Malcolm

--

Richard Heathfield said:
Malcolm said:


double root = malcolmsqrt(0.25);

Oops.
You are right, of course.
1 and the number are the bounds, and you have to do a test to see which is
the upper and which is the lower.Buy my book 12 Common Atheist Arguments (refuted)
$1.25 download or $6.90 paper, available www.lulu.com
 
K

Keith Thompson

Malcolm said:
--


You are right, of course.
1 and the number are the bounds, and you have to do a test to see which is
the upper and which is the lower.
[snip]

I presume you didn't intend your entire article to appear *after* the
signature delimiter.
 
R

Richard Heathfield

Jordan Abel said:
What's wrong with saying that the value is between N and 1, if you grant
"between" being inclusive and a particular definition of "between" to
apply to complex numbers?

Nothing would be wrong with that, but if them's your rules, then zero is not
an exception.
 
P

pete

Richard said:
pete said:


If N and one are included in the range,
then it works for zero too. And if
they're not, it doesn't work for one.

Knowing that the square root of N is bewteen N an one
is useful for calculating the square root of positive N,
but it is not useful for finding the square root of zero.

The square root of zero can't be found
by searching between N and one,
in the same way that all the other roots can.

double sq_rt(double x)
{
if (x > 0) {
const double a = x;
double b = x / 2 + 0.5;

do {
x = b;
b = (a / x + x) / 2;
} while (x > b);
}
return x;
}
 
R

Richard Heathfield

pete said:
The square root of zero can't be found
by searching between N and one,
in the same way that all the other roots can.

#include <float.h>

double square_root(double n)
{
double top = n;
double bottom = 0;
double root = 0;

double diff = 1;

while(diff < -DBL_EPSILON || diff > DBL_EPSILON)
{
root = (top + bottom) / 2;
diff = n - root * root;
if(diff < -DBL_EPSILON)
{
top = root;
}
else if(diff > DBL_EPSILON)
{
bottom = root;
}
}
return root;
}
 
P

pete

Richard said:
pete said:


#include <float.h>

double square_root(double n)
{
double top = n;
double bottom = 0;
double root = 0;

double diff = 1;

while(diff < -DBL_EPSILON || diff > DBL_EPSILON)
{
root = (top + bottom) / 2;
diff = n - root * root;
if(diff < -DBL_EPSILON)
{
top = root;
}
else if(diff > DBL_EPSILON)
{
bottom = root;
}
}
return root;
}

What's that function supposed to do?
Are you even *trying* ?!

/* BEGIN square_root.c output */

DBL_MIN is 2.225074e-308.

sq_rt(DBL_MIN) is 1.491668e-154.

square_root(DBL_MIN) is 1.112537e-308.

/* END square_root.c output */


/* BEGIN square_root.c */

#include<stdio.h>
#include <float.h>

double square_root(double n);
double sq_rt(double x);

int main(void)
{
puts("/* BEGIN square_root.c output */\n");
printf("DBL_MIN is %e.\n\n",
DBL_MIN);
printf("sq_rt(DBL_MIN) is %e.\n\n",
sq_rt(DBL_MIN));
printf("square_root(DBL_MIN) is %e.\n\n",
square_root(DBL_MIN));
puts("/* END square_root.c output */");
return 0;
}

double sq_rt(double x)
{
if (x > 0) {
const double a = x;
double b = x / 2 + 0.5;

do {
x = b;
b = (a / x + x) / 2;
} while (x > b);
}
return x;
}

double square_root(double n)
{
double top = n;
double bottom = 0;
double root = 0;

double diff = 1;

while(diff < -DBL_EPSILON || diff > DBL_EPSILON)
{
root = (top + bottom) / 2;
diff = n - root * root;
if(diff < -DBL_EPSILON)
{
top = root;
}
else if(diff > DBL_EPSILON)
{
bottom = root;
}
}
return root;
}

/* END square_root.c */
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top