0

I need to write a function that squares numbers for a course assignment. It calculates the square roots of numbers like 16 and 25 but does not accurately calculate the square root of 9.

Below is the code 

 double mysqrt (double x)
{
   double low, high, mid;

This if statement decides creates a range to determine the square root.

   if (x >= 0) {

      low = 0;
      high = x;

   }
   else {

     low = x;
     high = 1;

   }

This statement calculates the middle value

   mid = (high + low)/2.0;

The while loop is used to determine the square root. 

   while (abs(mid*mid - x) > 0.0001)
   {

      if (mid * mid > x)
          high = mid;

      else
          low = mid;

      mid = (high/2.0) + (low/2.0);
   }

   return mid;
 }
Akash21
  • 39
  • 5
  • Any reason for not using the [std::sqrt](http://en.cppreference.com/w/cpp/numeric/math/sqrt) function? –  Sep 16 '16 at 23:13
  • 2
    The teacher would probably frown on use of std::sqrt for an assignment about performing a binary search. – Christopher Oicles Sep 16 '16 at 23:16
  • `does not accurately calculate the square root of 9` Define "*accurately*". This is floating point, so there will never be 100% accuracy. Besides, your loop breaks at `0.0001` which is way worse than the precision of doubles anyway. – dxiv Sep 16 '16 at 23:17
  • 1
    http://stackoverflow.com/questions/19611198/finding-square-root-without-using-sqrt-function have a look at answer one if your not wanting to use std::sqrt – DevGuy Sep 16 '16 at 23:20
  • I don't see why you complain about accuracy, the result I get is 2.9999, it's about good for the square root of 9 with the precision you are using. – fernando.reyes Sep 16 '16 at 23:22
  • I'm pretty sure `if (x >= 0)...` wants to be `if (x >= 1)...` – Christopher Oicles Sep 16 '16 at 23:38

1 Answers1

1

Normally I don't just do someone's homework for them, but i wanted to challenge the idea that convergence should always be detected by comparing the error against a fixed epsilon value.

Keep in mind that the double data type, can only represent values taken from a finite range, so comparing for equivalence between two results can be used to detect convergence, where doing so with arbitrary precision could lead to infinite iteration

Also, a set of possible floating-point values is distributed so that the difference between one value and the next greater is smaller for small values than large values, so if you use an epsilon, it usually isn't appropriate to keep it fixed at some arbitrarily "small" value.

The code below performs the same dumb binary search, but the exit condition tests for a re-visiting of a previous iteration's result, which means that further iteration would just repeatedly cover the same search states forever and that the error is close to the minimum possible.

In this way, epsilon is automatically determined by the double data type itself, along with the input. If you replaced double with some kind of arbitrary-precision class, then you would indeed need to supply an epsilon, otherwise irrational roots might loop until some sort of failure, like an out-of-memory condition.

#include <iostream>
#include <iomanip>

double mysqrt(double x) {
    double low, high;
    if(x < 1) {
        if(x <= 0) return 0;
        low = x;
        high = 1;
    } else {
        low = 1;
        high = x;
    }
    for(;;) {
        const double mid = (low + high) / 2;
        if(high == mid || low == mid) return mid;
        if(mid * mid > x) {
            high = mid;
        } else {
            low = mid;
        }
    }
}

int main() {
    std::cout <<  std::setprecision(14) << mysqrt(3) << '\n';
}
Christopher Oicles
  • 3,017
  • 16
  • 11
  • +1 for `challenge the idea that convergence should always be detected by comparing the error against a fixed epsilon value`. For a nitpick, `mid * mid` can potentially overflow for *very* large `x`. And it is left as an exercise to the reader to figure why a `mysqrt(0)` call would fail if `<=` were replaced with `<` on the line `if(x <= 0) return 0;` (even though the math works out fine for `x=0`). – dxiv Sep 17 '16 at 01:20
  • 1
    Good points, I did very little testing with this, but I did see the bad case where x==0, so I just lumped it together with the detection for negative inputs. And I agree that `if(mid > x / mid)...` might be a better way to go, but I wanted to keep things close to OP's original code. – Christopher Oicles Sep 17 '16 at 01:26