Homemade Square Roots

This is a discussion on Homemade Square Roots within the C++ Programming forums, part of the General Programming Boards category; Okay, I'm aware that this is highly inefficient, that this is reinventing the wheel, etc., etc. ; however, I'm a ...

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    17

    Question Homemade Square Roots

    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.
    "None are more hopelessly enslaved than those who falsely believe they are free."
    -Goethe

    [paraphrased] "Those who would sacrifice essential liberties for a little temporary safety deserve neither."
    -Benjamin Franklin

  2. #2
    Registered User
    Join Date
    Feb 2004
    Posts
    127
    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

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,968
    Do you know any algorithms?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    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.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  5. #5
    Wen Resu
    Join Date
    May 2003
    Posts
    219
    i dont remember the exact way. google square root without calculator. it is wierd. i can't explain

  6. #6
    The Defective GRAPE Lurker's Avatar
    Join Date
    Feb 2003
    Posts
    949
    num^.5
    It doesn't really help, but it isn't using the sqrt function!
    Do not make direct eye contact with me.

  7. #7
    Registered User
    Join Date
    Apr 2003
    Posts
    17
    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.
    "None are more hopelessly enslaved than those who falsely believe they are free."
    -Goethe

    [paraphrased] "Those who would sacrifice essential liberties for a little temporary safety deserve neither."
    -Benjamin Franklin

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Here's a simple and naive algorithm...
    Code:
    double square_root ( double value )
    {
      double result = .00001;
    
      while ( result * result < value )
        result += .00001;
    
      return result;
    }
    My best code is written with the delete key.

  9. #9
    The Defective GRAPE Lurker's Avatar
    Join Date
    Feb 2003
    Posts
    949
    Fastest algorithm: lookup tables. Of course, they aren't that useful either in some cases .
    Do not make direct eye contact with me.

  10. #10
    Super Moderator
    Join Date
    Sep 2001
    Posts
    4,913
    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.

  11. #11
    Registered User
    Join Date
    Apr 2003
    Posts
    17

    Lightbulb Many Thanks, and a Follow-up

    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.
    "None are more hopelessly enslaved than those who falsely believe they are free."
    -Goethe

    [paraphrased] "Those who would sacrifice essential liberties for a little temporary safety deserve neither."
    -Benjamin Franklin

  12. #12
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    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.

  13. #13
    Obsessed with C chrismiceli's Avatar
    Join Date
    Jan 2003
    Posts
    501
    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 .
    Help populate a c/c++ help irc channel
    server: irc://irc.efnet.net
    channel: #c

  14. #14
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I hope you were joking
    Everything I say is a joke.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Forced moves trouble!!
    By Zishaan in forum Game Programming
    Replies: 0
    Last Post: 03-27-2007, 06:57 PM
  2. Help with my draughts game
    By Zishaan in forum C++ Programming
    Replies: 9
    Last Post: 03-24-2007, 07:33 AM
  3. Simplifing Square Roots
    By LiNeAr in forum C++ Programming
    Replies: 11
    Last Post: 10-01-2005, 08:56 PM
  4. for loops using square roots, square, Cube
    By lotf in forum C Programming
    Replies: 3
    Last Post: 03-21-2004, 03:29 AM
  5. Square roots / Powers etc.
    By Robert602 in forum C++ Programming
    Replies: 4
    Last Post: 09-30-2001, 03:26 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21