CODEWITHSUNDEEP
c++c++11
user2785675
user2785675

Reputation: 57

pseudo code for sqrt function

I managed to get my sqrt function to run perfectly, but I'm second guessing if I wrote this code correctly based on the pseudo code I was given.

Here is the pseudo code:

x = 1
repeat 10 times:  x = (x + n / x) / 2
return x.

The code I wrote,

#include <iostream> 
#include <math.h> 
using namespace std; 

double my_sqrt_1(double n) 
{
double x= 1; x<10; ++x;
return (x+n/x)/2; 
}

Upvotes: 2

Views: 10823

Answers (3)

lapk
lapk

Reputation: 3918

Since people are showing different approaches to calculating the square root, I couldn't resist ;)...

Below is the exact copy (with the original comments, but without preprocessor directives) of the inverse square root implementation from Quake III Arena:

float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;                       // evil floating point bit level hacking
        i  = 0x5f3759df - ( i >> 1 );               // what the...?
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//      y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

        return y;
}

Upvotes: 1

Nemanja Boric
Nemanja Boric

Reputation: 22157

No, your code is not following your pseudo-code. For example, you're not repeating anything in your code. You need to add a loop to do that:

#include <iostream> 
#include <math.h> 
using namespace std; 

double my_sqrt_1(double n) 
{
  double x = 1;
  for(int i = 0; i < 10; ++i) // repeat 10 times
    x = (x+n/x)/2;
  return x; 
}

Let's analyze your code:

double x = 1;
// Ok, x set to 1


x < 10; 
// This is true, as 1 is less than 10, but it is not used anywhere

++x;
// Increment x - now x == 2

return (x + n / x) / 2 
// return value is always (2 + n / 2) / 2

As you don't have any loop, function will always exit in the first "iteration" with the return value (2 + n / 2) / 2.

Upvotes: 7

Kevin Bello
Kevin Bello

Reputation: 179

Just as another approach that you can use binary search or the another pretty elegant solution is to use the Newton's method.

Newton's method is a method for finding roots of a function, making use of a function's derivative. At each step, a value is calculated as: x(step) = x(step-1) - f(x(step-1))/f'(x(step-1)) Newton's_method

This might be faster than binary search.My implementation in C++:

double NewtonMethod(double x) {
        double eps = 0.0001; //the precision 
        double x0 = 10;
        while( fabs(x-x0) > eps) {
            double a = x0*x0-n;
            double r = a/(2*x0);
            x = x0 - r;
            x0 = x;
        }
        return x;
    }

Upvotes: 3

Related Questions