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
    #1
    1. Advertising

  2. "" <> 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
    #2
    1. Advertising

  3. osmium 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?


    You can do it the way that used to be taught in elementary school.
     
    osmium, Mar 1, 2006
    #3
  4. 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
    #4
  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
    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.

    --
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
     
    , Mar 1, 2006
    #5
  6. Malcolm Guest

    <> 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)
    $1.25 download or $6.90 paper, available www.lulu.com
     
    Malcolm, Mar 1, 2006
    #6
  7. 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
    #7
  8. pete Guest

    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
    #8
  9. Ben Pfaff Guest

    pete <> writes:

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


    A math haiku. Bravo!
    --
    "Your correction is 100% correct and 0% helpful. Well done!"
    --Richard Heathfield
     
    Ben Pfaff, Mar 1, 2006
    #9
  10. 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
    #10
  11. 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
    #11
  12. CBFalconer Guest

    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
    "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/>
     
    CBFalconer, Mar 2, 2006
    #12
  13. Jordan Abel Guest

    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
    #13
  14. Malcolm Guest

    --

    "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)
    $1.25 download or $6.90 paper, available www.lulu.com
     
    Malcolm, Mar 2, 2006
    #14
  15. "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
    #15
  16. 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
    #16
  17. pete Guest

    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
    #17
  18. 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
    #18
  19. pete Guest

    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
    #19
  20. pete Guest

    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
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Luca
    Replies:
    1
    Views:
    1,045
    salman sheikh
    Apr 29, 2004
  2. Replies:
    0
    Views:
    1,243
  3. Christian

    Fix point square root

    Christian, Apr 25, 2005, in forum: VHDL
    Replies:
    5
    Views:
    6,671
    jeppe
    Mar 18, 2010
  4. sathyashrayan

    Finding the square root and guessing the number

    sathyashrayan, Apr 22, 2006, in forum: C Programming
    Replies:
    4
    Views:
    412
    Mark McIntyre
    Apr 22, 2006
  5. vibeni
    Replies:
    2
    Views:
    5,489
    vipinlal
    Mar 18, 2010
Loading...

Share This Page