1

So I'm doing this project where, using binary search, I have to plug in values into a formula and check if the output is approximately equal to my key. Because this formula I'm plugging into has to do with area of a circle, I need it to be approximately equal to the key by 7 decimal places.

double binarySearch(min, max, key){
   int mid;
   if(max > min)
   {
       mid = (1 + (max-min)/2)/1;

       if(funtion(mid) == key)
       {
           return mid;
       }
       if(function(mid) > key)
       {
           return binarySearch(min, mid-1, key);
       }
       if(function(mid) < key)
       {
           return binarySearch(mid+1, max, key);
       }

       return -1;
    }
}

so I know its pointless to check if(function(mid)==key) because its never going to be exactly equal. I'm just not sure how to return an answer that's accurate to 7 decimal places (or approximately equal to our key).

Tacio Costa
  • 92
  • 7
Maria Greenfield
  • 21
  • 3
  • Please, improve your code adding types and indentation. Is `key` a `double`? – Dario Rodriguez Jun 16 '18 at 21:58
  • I strongly recommend using a 'relative difference' function — such as the one found at [If statement when x is near a value](https://stackoverflow.com/a/42682190/15168). – Jonathan Leffler Jun 16 '18 at 22:13
  • 1
    yea my key is a double. this isn't my exact program I just posted a sample binary search cuz mine's a little messy right now. I just need to know what i should be putting in my first if statement – Maria Greenfield Jun 16 '18 at 22:33

4 Answers4

2

There are several approaches possible, one would be to check if the difference is smaller than the error, e.g.:

if(fabs(mid - key) <= 1e-7 ) {
   return mid;
}

This is still not fully correct because a floating point variable can also be infinite, NaN, and denormal. If you have a decent math library (>= C99) you can (and should) use islessequal() instead.

Eric Postpischil
  • 195,579
  • 13
  • 168
  • 312
deamentiaemundi
  • 5,502
  • 2
  • 12
  • 20
0

You can do function(mid) * pow(10, 7), it will shift 7 decimal digits to the left.

10.12345678 * 10^7 = 101234567.8

Then, you can cast the result to an integer, so that the remaining decimal digits can be ignored.

Tacio Costa
  • 92
  • 7
  • 1
    This shall do it well enough as far as the boundaries of the floating point are not reached. This can be done easily by testing the value before multiplying it. Also, as pow(10,7) is a constant, it shall be implemented just as a MULSD. – Dario Rodriguez Jun 16 '18 at 23:38
  • 1
    When one speaks of figures being equal to seven decimal places, one commonly means that the figures are within about 1e-7 of each other, not that they have the same decimal numeral to seven decimal places. Thus, .123456799 and .123456801 would be considered the same to seven decimal places, but this answer would indicate they are different, an undesired result. Additionally, multiplying by 10,000,000 incurs a floating-point rounding error, and thus the test of whether `floor(x*10000000)` equals `floor(y*10000000)` will sometimes fail to indicate whether `x` and `y` have the same digits. – Eric Postpischil Jun 17 '18 at 03:52
  • You're right about "_the figures are within about 1e-7 of each other_". Reason enough not to do it. – Dario Rodriguez Jun 17 '18 at 20:51
-1

Checking if an answer is correct to 7 decimal places

Let us specify correct to 7 decimal places. Is that 7 places after the decimal point or to 7 significant digits?

If you want "7 places after the decimal point", consider @deamentiaemundi. Note that for very small min,key like 1e-10, 1e-20, that will always be true. For min,key that are very large and different, even by a bit, will always be false like 1.0e10, 1.00000000001e10.

With floating point numbers, it is usually 7 significant digits that is sought.

Then 1234.5678eN, 1234.5679eN are "correct" to 7 digits regardless of the value of N.

Further 9.999999999 and 10.0 are "correct" to 7 digits, which differ by 0.000000001.

Since OP is looking for the area, let us assume min,key are both positive. (zero and mix-sign need additional code.

Find the relative difference.

bool close_enough(double min, double key) {
  if (min == key) {
    return true;
  }
  if (min < 0.0 != key < 0.0) {
    // Handle different signs
    // this is usually false, but you may want something different.
    return false;   
  }
  double dif_abs = fabs(min - key);
  double average = fabs((min + key)/2);
  double dif_rel = dif_abs/average;
  return (dif_rel <= 1.0e7);
}

Additional concerns include Not-a-number, infinity == infinity, 0 and a small value, min + key could overflow. But this above should get one started.

chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
-2

It's a little hacky, but you can use snprintf() to print your floating point values as strings out to 7 decimals and then compare the strings using strncmp(). Hope that helps.

Newt Hoenikker
  • 113
  • 5
  • 1
    This is not hacky, this is foolish and wastes resources. Please read IEEE 754. – Dario Rodriguez Jun 16 '18 at 22:23
  • It wastes at most a few hundred bytes and a handful of cycles while sidestepping branches to check for NaN, +/-Inf, and denormal values. I wouldn't use it for a production level API, or a function that's getting called millions of times, or when I know that my values will regularly brush up against `DBL_MAX`. I think this is a reasonable use case when OP is clearly doing a homework assignment and probably cares more about getting it done than impressing their professor with their knowledge of IEEE 754. – Newt Hoenikker Jun 16 '18 at 22:55
  • 2
    This fails because two values could differ by a very small amount yet be an opposite sides of a point where numbers round up versus down (e.g., .1234567499 and .1234567501), so `snprintf` gives different results for them even though OP likely wants to consider them a match. – Eric Postpischil Jun 16 '18 at 23:28