Bug 62121 - Calculating the power of a negative number with a fraction fails (for example -2^(1/3))
Summary: Calculating the power of a negative number with a fraction fails (for example...
Status: RESOLVED FIXED
Alias: None
Product: POI
Classification: Unclassified
Component: XSSF (show other bugs)
Version: unspecified
Hardware: All All
: P2 normal (vote)
Target Milestone: ---
Assignee: POI Developers List
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2018-02-21 08:19 UTC by Bob van den Berge
Modified: 2018-04-01 15:59 UTC (History)
1 user (show)



Attachments
Excel that includes the formula that is giving the issue (8.14 KB, application/vnd.openxmlformats-officedocument.spreadsheetml.sheet)
2018-02-21 08:19 UTC, Bob van den Berge
Details
Obsolote - Patch that will apply the suggested fix (4.50 KB, patch)
2018-03-17 16:55 UTC, Bob van den Berge
Details | Diff
Patch that will apply the suggested fix v2 (37.44 KB, application/mbox)
2018-03-18 08:39 UTC, Bob van den Berge
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Bob van den Berge 2018-02-21 08:19:14 UTC
Created attachment 35735 [details]
Excel that includes the formula that is giving the issue

The resolution of formula "=-2^(1/3)" happens in 2 steps:
1: Calculate 1/3
2: Calculate -2 ^ 0.333....

This calculation gets performed by the standard java util function Math.pow(double a, double b). Math.pow returns NaN if a is a negative number and b is a decimal number. Excel however can execute this. 

The solution to this problem is to alter the calculation that happens. We can alter the calculation is "-1 * (2 ^ 0.333..)" which is functionally the same but is supported by Math.pow(). 

I will try to put together a patch somewhere this week to resolve this issue.
Comment 1 Javen O'Neal 2018-02-21 11:19:53 UTC
Hmm.. -2^0.5 could be interpreted as either -1*(2^0.5)≈0.707 or (-2)^0.5≈0+0.707i, with the latter being the commonly accepted interpretation in mathematics. Looks like if Excel interprets this as the former, that's a quirk in their implementation that we unfortunately have to mimick if we want to be compatible.

For what it's worth, Google Sheets gives an imaginary number error.
Comment 2 Javen O'Neal 2018-02-21 11:26:56 UTC
Could you make your test case for -2^(1/2) and -2^(0.5) to show that the problem isn't with order of operations in the exponent but in the sign association with the base?

The mathematicians among us will also appreciate that x^0.5 is the same as sqrt(x).
Comment 3 Axel Howind 2018-02-21 14:18:28 UTC
I just tried that in Excel 2010 which will give an error for "-2^(1/2)" and calculate "-3^(1/2)". So Excel at least does what is to be expected in this case.

If we pull out the sign, the result will be wrong for -2^(1/2), so that change should rather not be made.

> The solution to this problem is to alter the calculation that happens. 
> We can alter the calculation is "-1 * (2 ^ 0.333..)" which is functionally
> the same but is supported by Math.pow(). 

No, it is not the same. You make the assumption that "0.333.." is the same as "1/3", which would be true if we had exact mathematic functions. But we don't have these, and no matter to which precision we can approximate 1/3, we still have to use an approximation, and the exact result of -2^(x) will be imaginary for an infinite number of values in the interval between the approximation we chose and -1/3.

I don't know if my above explanation is understandable. In short, -2^(1/n) is imaginary for even values of n and negative for odd values of n. That function is not continuous, and you'd better not rely on getting correct results.

If for any reason you believe that you have a case where it is safe to pull the minus out and calculate as you suggested, just use a pair of parenthesis.
Comment 4 Mark Murphy 2018-02-21 14:25:52 UTC
(In reply to Javen O'Neal from comment #1)
> Hmm.. -2^0.5 could be interpreted as either -1*(2^0.5)≈0.707 or
> (-2)^0.5≈0+0.707i, with the latter being the commonly accepted
> interpretation in mathematics. Looks like if Excel interprets this as the
> former, that's a quirk in their implementation that we unfortunately have to
> mimick if we want to be compatible.
> 
> For what it's worth, Google Sheets gives an imaginary number error.

Excel 2016 gives #NUM! for -2^.5. In fact except for the fractions representing odd roots, (1/3, 1/5, 1/7, ...) all other fractions return #NUM! when the base is negative.
Comment 5 mewalig 2018-02-21 17:18:38 UTC
fwiw, in Excel, although -2^(0.333333) gives an error, -2^(0.333333333333333) does not (and -2^(n/y) is also an error if n is > 1, even if 1/y works fine). 

Possibly the Excel pow() evaluator is simply checking its argument to see if it is the equivalent to 1/y where y is an odd number. this exception-based approach would not be hard to implement in POI-- it would not need to impact the interpreter, and would just be a change to the pow() code such as the following, with the appropriate type used in lieu of "double":

  function pow(x, y) {
    if(abs(y) < 1) {
      double one_over = abs(1/y);
      // change .001 to smallest possible val that still gives correct result
      int yth_root = (int)round(one_over, 0);
      if(abs(round(one_over, 0) - one_over) < .001) {
        double exact_1_over_y = (double)1/(double)yth_root;
        if(y == exact_1_over_y) { // y = 1/n or the exact decimal equivalent
          // find the yth root and return that
          ...
  ...
Comment 6 Axel Howind 2018-02-23 15:06:00 UTC
(In reply to mewalig from comment #5)

I don't know if this should really be mimicked. But if so, the code should be corrected in some places (still untested and should be checked if we really want to do zhis):

we should only do a special treatment for negative x, so it should be
>     if(x<0 && abs(y) < 1) {

Now you want to know if y is the reciprocal of an int. Lets call that r (reciprocal) instead of one_over (that name made me think about "n over k" instead and it took some time before I got the meaning).

We can use Math.rint() instead of Math.round() as the result is converted back to int for the comparison anyway. 

Also, the smallest value that still gives the correct result depends on the values being compared. Without trying, I'd think 2 ulp (units in the last place) should be a safe bet.

>    // test if y is the reciprocal of an integer value
>    double r = 1/y;
>    double rInt = Math.rint(r);
>    if(abs(r - rInt) < 2*Math.ulp(r)) {

At last the missing part:
>           // find the yth root and return that (undefined for even rInt)
>           return ((int)rInt)%2==0 ? Double.NAN : -Math.pow(-x,y);
Comment 7 mewalig 2018-02-23 15:44:31 UTC
These changes all make sense to me (though I didn't check the math code).

My 2 cents: it's worth mimicking-- Excel is the gold standard for spreadsheets and if someone has an Excel model that works and opens it in POI and it doesn't, it is an immediate turn-off. It's a pretty easy change to make, so the cost is small and the payoff, while not huge, is well worth that cost.
Comment 8 Bob van den Berge 2018-03-01 19:00:15 UTC
So who normally makes a decision about what happens seeing as we have conflicting opinions here (its my first time opening an issue). 

My math skills are not good enough to have a useful opinion on the math but as a consumer of POI, I would expect that the library would at least mimic what excels does.
Comment 9 Nick Burch 2018-03-01 19:43:34 UTC
Generally speaking, we try to have POI mimic Excel where practical/possible. We have special logic in the Date and Number formatting code, for example, to handle the edge cases where Excel and Java formatting rules differ. (At a cost of complexity and performance, sadly)

As a first step here, it would be great if someone could create a small spreadsheet in Excel, with 3 columns: formula as text, formula, manually typed in number of what excel renders. Add in a bunch of rows for various power edge cases

Second step - write a junit unit test that runs over that sample file, and checks where Apache POI differs from Excel

Third step - write a patch to POI to get it to match Excel in all cases...

Step #1 can be done by anyone - no POI experience needed, just Excel experience. Step #2 should be possible for anyone with some POI + junit user experience. #3 may or may not need extensive POI and/or Math skills, but we need people to tackle the easier #1 and #2 first before we can ponder proposed/actual fixes for 3!
Comment 10 Greg Woolsey 2018-03-01 19:57:24 UTC
(In reply to Nick Burch from comment #9)
> Second step - write a junit unit test that runs over that sample file, and
> checks where Apache POI differs from Excel

Note that POI has a test framework for exactly this form of Excel file:


BaseTestFunctionsFromSpreadsheet

subclasses can be examined for examples and specific formatting conventions.
Comment 11 Bob van den Berge 2018-03-17 16:55:26 UTC
Created attachment 35780 [details]
Obsolote - Patch that will apply the suggested fix
Comment 12 Bob van den Berge 2018-03-17 16:59:24 UTC
I wrote an implementation that will fix this issue. As stated in multiple places, its good to submit a patch early and get feedback often. So, I wonder if anyone could give some feedback on my patch?
Comment 13 PJ Fanning 2018-03-17 18:48:52 UTC
Can you put the patch in github? https://github.com/apache/poi
Comment 14 Bob van den Berge 2018-03-17 22:26:08 UTC
I suppose you mean as a pull request? I created one following your comment here: https://github.com/apache/poi/pull/104. 

Is this something that should always happen? If so, then maybe this should be added to the docs.
Comment 15 PJ Fanning 2018-03-18 00:11:49 UTC
http://forums.devshed.com/java-help/863310-math-pow-result-nan-post2713105.html#post2713105 describes the Java Math.pow behaviour that causes this
Comment 16 PJ Fanning 2018-03-18 00:33:37 UTC
I had to modify the attached patch to keep the existing unit tests working.

    public static final Function PowerEval = new TwoOperandNumericOperation() {
        protected double evaluate(double d0, double d1) {
            if (d0 < 0.0 && Math.abs(d1) > 0.0 && Math.abs(d1) < 1.0) {
                return -1 * Math.pow(d0 * -1, d1);
            }
            return Math.pow(d0, d1);
        }
    };
Comment 17 Bob van den Berge 2018-03-18 08:39:26 UTC
Created attachment 35781 [details]
Patch that will apply the suggested fix v2

I applied to suggested solution that will cover the edge case. I also added unit tests for that case and added our original problem scenario to the excel sheet.
Comment 18 PJ Fanning 2018-04-01 15:59:36 UTC
Fix merged in https://svn.apache.org/viewvc?view=revision&revision=1828143