# Square root of a number.

Discussion in 'C Programming' started by priyam.trivedi@gmail.com, Mar 1, 2006.

1. ### Guest

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

, Mar 1, 2006

2. ### Keith ThompsonGuest

"" <> writes:
> 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.

--
Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

Keith Thompson, Mar 1, 2006

3. ### osmiumGuest

<> wrote:

> 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.

osmium, Mar 1, 2006
4. ### Christian BauGuest

In article <>,
"" <> wrote:

> 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.

Christian Bau, Mar 1, 2006
5. ### Guest

wrote:
> 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

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.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

, Mar 1, 2006
6. ### MalcolmGuest

<> wrote in message
news:...
> 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.
>

--
Buy my book 12 Common Atheist Arguments (refuted)

Malcolm, Mar 1, 2006
7. ### Richard HeathfieldGuest

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.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Richard Heathfield, Mar 1, 2006
8. ### peteGuest

Richard Heathfield wrote:
>
> 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);

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

--
pete

pete, Mar 1, 2006
9. ### Ben PfaffGuest

pete <> writes:

> The square root of N
> Is in between N and one
> Except for zero

A math haiku. Bravo!
--
--Richard Heathfield

Ben Pfaff, Mar 1, 2006
10. ### Richard HeathfieldGuest

pete said:

> Richard Heathfield wrote:
>>
>> 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);

>
> 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.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Richard Heathfield, Mar 1, 2006
11. ### Richard HeathfieldGuest

Ben Pfaff said:

> pete <> writes:
>
>> The square root of N
>> Is in between N and one
>> Except for zero

>
> A math haiku. Bravo!

A better haiku
Would get the mathematics
Absolutely right.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Richard Heathfield, Mar 1, 2006
12. ### CBFalconerGuest

Malcolm wrote:
> <> wrote in message
>>
>> 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.

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

CBFalconer, Mar 2, 2006
13. ### Jordan AbelGuest

On 2006-03-01, Richard Heathfield <> wrote:
> Ben Pfaff said:
>
>> pete <> writes:
>>
>>> The square root of N
>>> Is in between N and one
>>> Except for zero

>>
>> A math haiku. Bravo!

>
> 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?

Jordan Abel, Mar 2, 2006
14. ### MalcolmGuest

--

"Richard Heathfield" <> wrote in message
news:du58gf\$2j8\$-infra.bt.com...
> 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.
>

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)

Malcolm, Mar 2, 2006
15. ### Keith ThompsonGuest

"Malcolm" <> writes:
> --
>
> "Richard Heathfield" <> wrote in message
> news:du58gf\$2j8\$-infra.bt.com...
>> 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.
>>

> 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.

--
Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

Keith Thompson, Mar 2, 2006
16. ### Richard HeathfieldGuest

Jordan Abel said:

> On 2006-03-01, Richard Heathfield <> wrote:
>> Ben Pfaff said:
>>
>>> pete <> writes:
>>>
>>>> The square root of N
>>>> Is in between N and one
>>>> Except for zero
>>>
>>> A math haiku. Bravo!

>>
>> 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?

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

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Richard Heathfield, Mar 2, 2006
17. ### peteGuest

Richard Heathfield wrote:
>
> pete said:
>
> > Richard Heathfield wrote:
> >>
> >> 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);

> >
> > 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.

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

--
pete

pete, Mar 2, 2006
18. ### Richard HeathfieldGuest

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

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Richard Heathfield, Mar 2, 2006
19. ### peteGuest

Richard Heathfield wrote:
>
> 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;
> }

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 */

--
pete

pete, Mar 2, 2006
20. ### peteGuest

pete wrote:
>
> Richard Heathfield wrote:
> >
> > 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;
> > }

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

square_root(10) freezes my computer.

--
pete

pete, Mar 2, 2006