square root algorithm???

This is a discussion on square root algorithm??? within the C++ Programming forums, part of the General Programming Boards category; LuckY nailed this one. It was less code than I thought there would be. What would I need to learn ...

  1. #16
    Registered User
    Join Date
    Dec 2004
    Posts
    31
    LuckY nailed this one. It was less code than I thought there would be. What would I need to learn to make it graphical? Like have a square calculator pop up when I run the .exe file with buttons for each number a a screen that displays what you are entering. Basically just like the windows calculator. Would that deal with OpenGL or what?
    Last edited by Emotions; 12-29-2004 at 05:17 PM.

  2. #17
    Sweet
    Join Date
    Aug 2002
    Location
    Tucson, Arizona
    Posts
    1,812
    There are many options for making it graphical. You could go with poratble solutions like OpenGl, SDL, Allegro, wxWindows,... or if your working in windows use win32 API. But first I would make sure I have a functional program then worring about adding a gui.
    Woop?

  3. #18
    Registered User Finchie_88's Avatar
    Join Date
    Aug 2004
    Posts
    154
    From the laws on indices, the square root of a number is that number to the power of a half, so, what is wrong with this code, because for some reason, the answer is always 2, it might be the ^, I think that is the power operator, from what is happening, I think it might mean something different...

    Code:
    int x;
        int funct;
        funct = x^(1/2);
        cout << "Please input a number:" << endl;
        cin >> x;
        cout << funct << endl;

  4. #19
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    ^ is not the power operator, it is the bitwise exclusive or operator.

    Besides, you never initialize x before using it so it wouldn't work anyway.
    Last edited by jlou; 12-29-2004 at 06:55 PM.

  5. #20
    Sweet
    Join Date
    Aug 2002
    Location
    Tucson, Arizona
    Posts
    1,812
    The ^ is not the power operator it's the bitwise OR.
    Woop?

  6. #21
    Registered User Bajanine's Avatar
    Join Date
    Dec 2001
    Location
    The most peaks over 10,000 feet!
    Posts
    396
    Power function is like so: double pow(double x, double y);

    But I think this takes the fun out of it so to speak. Here is another method although it is more convoluted than the previous example given by Sang-drax .
    Favorite Quote:

    >For that reason someone invented C++.
    BLASPHEMY! Begone from my C board, you foul lover of objects, before the gods of C cast you into the void as punishment for your weakness! There is no penance for saying such things in my presence. You are henceforth excommunicated. Never return to this house, filthy heretic!



  7. #22
    C/C++ homeyg's Avatar
    Join Date
    Nov 2004
    Location
    Louisiana, USA
    Posts
    209
    There is also a way to find square roots that I don't think is very well known, it works sort of like long division.

    Here is a picture of what I'm talking about. Has anyone else seen this method? (I mean, I asked my math teacher about it and he said he'd never 'seen such a thing'.) I use it all the time. I think it would be pretty easy to program. (PM me if you can't figure out how it works, it's to long to describe here)

    Dang it! The post above me beat me to it!

  8. #23
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    I actually also implemented that algorithm. I have found, however, that it is not very accurate beyond 5 decimal digits. After that things go downhill and fast.

  9. #24
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    You don't have to iterate Newton's algoritm 100 times.

    When the algorithm converges (it always does in this case), it does so quadratically = quite fast.

    Try around 10 iterations. This is just a suggestion, I don't know if speed matters to you.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  10. #25
    ---
    Join Date
    May 2004
    Posts
    1,379
    Carmack's inverse sqrt

    Code:
    float InvSqrt (float x)
    {
        float xhalf = 0.5f*x;
        int i = *(int*)&x;
        i = 0x5f3759df - (i >> 1);
        x = *(float*)&i;
        x = x*(1.5f - xhalf*x*x);
        return x;
    }

  11. #26
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    always a fun time:
    Code:
    std::complex<double> mysqrt(double num, const double precision = 0.0000001);
    std::complex<double> mysqrt(double num, const double precision )
    {
      bool real = true;
    
      if ( num < 0.0 )
      {
        real = false;
        num = -num;
      }
    
      double root = 1.0;
      while ( fabs((root * root) - num) > precision )
        root = (root + (num/root)) / 2;
    
      if ( real )
        return std::complex<double>(root,0);
      return std::complex<double>(0,root);
    
    }
    Edit: Credit to LuckY for the
    Code:
    root = (root + (num/root)) / 2;
    Last edited by Thantos; 12-31-2004 at 10:46 AM.

  12. #27
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    Yes, I agree with Sang-drax and Lucky. It's best to use Newton-Raphson method.
    I'd like to mathematically clearify what is going on, maybe someone will find it useful.
    Basically we want to solve equation f(x)=x^2-C=0;
    Consider function f(x) on interval [A,B]. Assume that exists n-th derivation of function f(x) in point a where a is from interval [A,B].
    First derivation is labeled f'(x)
    Second derivation is labeled f''(x)... and so on

    In mathematical analysis function f(x) can be represent with the following series:
    f(x)=f(a)+f'(a)(x-a)+f''(x)(x-a)^2/2!+....
    First approximation (linear) is:

    f(x)~=f(a)+f'(a)(x-a) (sign '~=' is aproximation of '=').

    If e is root of equation f(x)=0 ( f(e)=0 ) then we have:

    f(e)~=f(a)+f'(a)(x-a) =>
    0~=f(a)+f'(a)(x-a) =>

    x=a-f(a)/f'(a).
    Now we can form an iterative procedure:
    x(k)=x(k-1)+f(x(k-1))/f'(x(k-1))
    Now we need to choose start value x(0) and start calculating x(1),x(2),...
    Of coures there are conditions which must be satisfied for this series to converge ( in this case it always does ) but it would took too much time and complex math to explain. This algorithm converge quadratically.

    When calculating roots of equation x^2-C=0 according to procedure above we have:
    x(k)=x(k-1)-(x(k-1)^2-C)/(2*x(k-1)) =>

    x(k)=x(k-1)-(x(k-1)-C/x(k-1))/2; (Lucky's formula)
    This is called Newton-Raphson method and also tangent method

    To understand clearly what is going on you could look at the attached picture.
    Now you can see why this algorithm converge quadratically (very very fast) so it's much better to define precision first (or number of exacts decimal digits in solution) example if x(k)-x(k-1)<=eps where eps is 10^(-7) that means we'll have 7 exact decimal digits (digits after decimal point) in solution. So criteria for stopping calculation could be |x(k)-x(k-1)|< eps.

    Choosing start velue has big influence on number of iterations. It's always good to choose start value closer to actual solution!

    Hope someone will find this useful.

    P.S. Sorry because of bad English.
    Attached Images Attached Images  

  13. #28
    Registered User
    Join Date
    Mar 2003
    Posts
    580
    Excellent explanation Micko.

    This is just another implementation of the newtonian approximation algorithm. I wrote this as a part of my math library. It works, but it's not really faster than crt sqrt much less the sqrt method on your floating point unit (you can't realistically beat hardware). If you need to also balance speed you can actually download the doom3 sdk as I believe it contains methods for using the approximation algorithm with a clever way of finding the seed (initial guess)...this is used in the lighting algorithms.

    so, here's my implementation:
    float IterSqrtf(float r, int numtries)
    {
    float m(0.0f);
    float b(0.0f);
    float currx=r;
    float curry(0.0f);
    float root(0.0f); //this is what gets returned

    while(numtries--)
    {
    curry = (currx*currx) - r; //y1
    //Check to see if curry is < 0
    m = 2 * currx;
    b = (-m*currx) + curry;
    root = -b / m;
    currx = root;
    }
    return root;
    }
    Here's an implementation from tricks of the 3d game programming gurus...it's faster than sqrt() and is always within 5% accuracy

    float Faster_Sqrtf(float f)
    {
    float result;

    _asm
    {
    mov eax, f
    sub eax, 0x3f800000
    sar eax, 1
    add eax, 0x3f800000
    mov result, eax
    }

    return result;
    }
    Last edited by Darkness; 12-31-2004 at 05:16 PM.

  14. #29
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    Quote Originally Posted by pktcperlc++java
    the way I did this for my own calculator was through a for loop

    Code:
    for(int i=0;pow(i,2)<number;i+=0.001){
    
    //do nothing inside loop
    
    }//end for
    the +=0.001 ends up being formated by the compiler as a huge string of decimals and it can always be formated later in the code

    a bit off topic:
    this
    for(int i=0;pow(i,2)<number;i+=0.001);
    works without the {} and is more readable
    i seem to have GCC 3.3.4
    But how do i start it?
    I dont have a menu for it or anything.

Page 2 of 2 FirstFirst 12
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, 07:57 PM
  2. Bisection Method function value at root incorrect
    By mr_glass in forum C Programming
    Replies: 3
    Last Post: 11-10-2005, 09:10 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 02:24 AM

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