1

I have an expression that is used to estimate percentiles by interpolating between two values.

windowMin + (currentPercentile - lastPercentile) * (windowMax - windowMin) / (percentile - lastPercentile)

This has given me very good real-world results. However, in my unit tests, I'm having trouble assering that things are working correctly, since I consistently get significant rounding error.

In three test cases, I try to get the 40th, 50th and 60th percentile, resulting in these computations:

1 + (0.4 - 0.3333333333333333) * (2 - 1) / (0.6666666666666666 - 0.3333333333333333)
1 + (0.5 - 0.3333333333333333) * (2 - 1) / (0.6666666666666666 - 0.3333333333333333)
1 + (0.6 - 0.3333333333333333) * (2 - 1) / (0.6666666666666666 - 0.3333333333333333)

This yields:

{
  "0.4": 1.2000000000000002,
  "0.5": 1.5,
  "0.6": 1.8
}

This fails my assertion, which is looking for 1.2 for the 40th percentile.

Is there a way to restructure this expression to improve accuracy in all cases? If not, is there an easy way to work around this issue with chai assertions?

John Gietzen
  • 48,783
  • 32
  • 145
  • 190
  • possible duplicate of [Is JavaScript's Floating-Point Math Broken?](http://stackoverflow.com/questions/588004/is-javascripts-floating-point-math-broken) – Barmar Sep 22 '13 at 04:44
  • See also http://stackoverflow.com/questions/2221167/javascript-formatting-a-rounded-number-to-n-decimals?lq=1 – Barmar Sep 22 '13 at 04:44
  • 2
    @Barmar: This is not a duplicate. I'm asking about a specific expression. I'm not asking for an explanation, I'm asking for a mitigation. – John Gietzen Sep 22 '13 at 04:48
  • 1
    But the problem you're having is the same problem -- you're running into the fact that floating point cannot represent values exactly, there will always be glitches like this. – Barmar Sep 22 '13 at 04:49
  • 1
    @Barmar: you need to listen to the stackoverflow podcast. Just because there are similarities between questions, and just because questions may have the same answer, that does not make them duplicates. This is from Joel Spolsky, himself. – John Gietzen Sep 22 '13 at 04:51
  • 1
    @Barmar: In any case, this isn't even the same as either of the questions that you linked. I'm looking for a technique to rearrange my computation for maximum precision. I'm NOT looking for an explanation, like the other questions. – John Gietzen Sep 22 '13 at 04:53
  • That's why I also gave a reference to another question that would be helpful. No matter how you slice it, there's nothing new in this question, it's just rehashing issues that have been addressed in many other questions. – Barmar Sep 22 '13 at 04:53
  • You can't change the precision of Javascript floating point, it is what it is. And it won't help, you'll just get lots more zeroes. – Barmar Sep 22 '13 at 04:54
  • 4
    @Barmar: There are a number of techniques in floating point that can be used to analyze errors in expressions, design computations to reduce errors, and/or extend precision. Asking whether such techniques can aid in a particular situation is a completely different question from asking why floating-point arithmetic does not work like exact or expected math. – Eric Postpischil Sep 22 '13 at 10:46

4 Answers4

1

These rounding errors are a characteristic of floating point maths.

One possible solution might be to apply .toPrecision() to your calculations before returning the result:

var result = windowMin + (currentPercentile - lastPercentile) * (windowMax - windowMin) / (percentile - lastPercentile);
return result.toPrecision(6);  // returns six significant figures

or possibly toFixed():

return result.toFixed(2); // returns two decimal places.
  • Fair enough. However, the range of my values may vary wildly. Is there a way to do this for a certain number of significant digits. In my case, I would like it to be several times smaller than `windowMin - windowMax`, which will typically start out around `0.0000375`. So, in that case, I would like to round to 9 digits. – John Gietzen Sep 22 '13 at 04:55
  • `.toPrecision()` takes a parameter specifying the number of significant digits. Here's [the reference](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/toPrecision). Of course, the more you include the more likely you are to encounter a rounding error. –  Sep 22 '13 at 04:59
1

The chai closeTo is designed to handle this sort of test:

expect(calculatedValue).to.be.closeTo(1.2, 0.000001);

The first argument is the expected value and the second is a delta indicating how close calculatedValue needs to be to 1.2.

David Norman
  • 19,396
  • 12
  • 64
  • 54
0

I see two ways to solve that problem:

  1. If you are going to have only finite numbers in result you can round the numbers up to some little precision

  2. Division confuses you. Multiply both sides of equtation to the divider and you'll have no more infinite fractions in the result :)

Stalinko
  • 3,319
  • 28
  • 31
0

It happens that 1.2000000000000002 is already the double precision floating point value nearest to the exact interpolation you submitted, as illustrated with Pharo smalltalk expression below (asTrueFraction means that floating point value is converted to a Fraction having exactly the same value)

(1 + ((0.4 asTrueFraction - 0.3333333333333333 asTrueFraction) * (2 - 1) / (0.6666666666666666 asTrueFraction - 0.3333333333333333 asTrueFraction))) asFloat
-> 1.2000000000000002.

Even if you evaluate the interpolation with exact arithmetic, we can do that by replacing asTrueFraction with asMinimalDecimalFraction (which get you the decimal number with minimal number of digits that will be rounded to the same Float):

0.4 asTrueFraction -> (3602879701896397/9007199254740992).
0.4 asMinimalDecimalFraction -> (2/5).
0.3333333333333333 asMinimalDecimalFraction -> (3333333333333333/10000000000000000).
0.6666666666666666 asMinimalDecimalFraction -> (3333333333333333/5000000000000000).

Then you get again the same result, see how it decompose:

(1 + ((0.4 asMinimalDecimalFraction - 0.3333333333333333 asMinimalDecimalFraction) * (2 - 1) / (0.6666666666666666 asMinimalDecimalFraction - 0.3333333333333333 asMinimalDecimalFraction))) 
 -> (4000000000000000/3333333333333333).

(4000000000000000/3333333333333333) asFloat ->  1.2000000000000002.

In other words, if you want a result in floating point, then 1.2000000000000002 is the best value.

I don't say that interpolation formula will always be exact as it is written, it can cumulate round off errors, but it already performs a decent job on your input data.

Change the test rather than the formula, and insert explicit accuracy requirements.

aka.nice
  • 9,100
  • 1
  • 28
  • 40