0

In the following (naive) implementation of a pow(x, n) method, ignoring completely any optimized approach, I find the following problem:

public double pow(double x, int n) {  
  boolean negative = n < 0;  
  long power = Math.abs(n);  
  double ans = 1.0;  
  for(long i = 0; i < power; i++) {  
    ans = ans * x;  
  }    
  return negative ? 1.0/ans: ans;  
}

Here I have made the assumption that for the case of negative exponent I simply calculate the x^n and then return 1/(x^n) since e.g. 2^(-3) = 1/(2^3)

Problem:
The code fails in the following case:
pow(2.00000, -2147483648)
The output is 1.00000 while the expected correct result is 0.00000

If I change the code as follows:

public double pow(double x, int n) {  
  long power = n;  
  if(power < 0) {  
    x = 1 / x;  
    power = -power;
  }  
  double ans = 1.0;  
  for(long i = 0; i < power; i++) {  
    ans = ans * x;  
  }    
  return ans;  
}

The result is correct!

So what is the difference between doing the approaches? I was expecting them to be equivalent but they are not

Jim
  • 3,845
  • 3
  • 22
  • 47
  • [`double`](https://en.wikipedia.org/wiki/Double-precision_floating-point_format) has only 11 bit exponent and your result needs 32 !!! Also why not use [Power by squaring for negative exponents](https://stackoverflow.com/a/30962495/2521214) ? – Spektre May 09 '22 at 07:36
  • @Spektre: Could you please elaborate on "double has only 11 bit exponent and your result needs 32!!!"? I don't understand this – Jim May 09 '22 at 08:47
  • 11 bit exponent in `double` means it can store (normalized) numbers with exponents `exp = (+/-) 2^10` so `2^-1024 ... 2^+1024` and your result is `2^-2147483648` where `log2(2147483648)=31` + 1 bit for sign so you would need 32 bit exponent instead of 11 ... you can not store numbers (with decadic exponent) bigger/smaller than `~ 10 ^ (+/-) 308` in `double` while `2^-2147483648 -> ~ 10^-646456993.24` which is clearly outside double range – Spektre May 09 '22 at 09:01
  • @Spektre: For the purpose of this post 0 is what I expected. But out of curiosity how is what you described solved then? – Jim May 09 '22 at 10:56
  • depends on case ... for example you can use: higher precision FPU variable, arbitrary precision datatype, logarithmic scale of equation ... – Spektre May 09 '22 at 14:16
  • @Spektre: would that mean not using java? I don't know what a higher precision FPU variable would be when programming in Java – Jim May 09 '22 at 15:26
  • unless you want to implement it yourself there are libs for stuff like that for example try/google `BigDecimal` ... – Spektre May 09 '22 at 20:26
  • @Spektre: How did you come with `10^(+/-)308` when earlier you said it can store up to `2^(+/-)1024`? From the calculator 10^308 != 2^1024 – Jim May 10 '22 at 09:14
  • its basic logarithm math (changing base from 2 to 10): `2^1024 = 10^(1024*log10(2)) = 10^(1024*0.30102999) = 10^308.2547` its very useful for [number printing routines](https://stackoverflow.com/a/59861545/2521214) so you know how much space to allocate for string and can store in reverse order directly instead of adding another pass. Not sure what calculator you have my (win7 x64 calc) returns this: `2^1024 = 1.797693134862315907729305190789e+308` and `10^308.2547 = 1.7976287282083264877504930088425e+308` which is pretty close considering i rounded quite a few decimal digits of the exponent – Spektre May 10 '22 at 09:32
  • @Spektre: I just used this to calculate 10^308 https://www.mathsisfun.com/calculator-precision.html It gives `1.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e+308` While for 2^1024 it gives `1.7976931348623159077293051907890247336179769789423065727343008115773267580550096313270847732240753602112011387987139335765878976881441662249284743063947412437776789342486548527630221960124609411945308e+308` – Jim May 10 '22 at 11:19
  • yep both are correct ... (you truncated the decadic exponent to ~308 so the result might be off by up to factor of 10 (single digit)... but that is usually enough for rough comparison of magnitudes) – Spektre May 10 '22 at 11:23

1 Answers1

5

Math.abs(n) is still an int, and only afterwards it is assigned to a long, Therefore, the absolute value of -2147483648 was -2147483648 again (this is noted in the documentation of Math.abs(int)). With the negative bound, the loop performed no iterations.

Math.abs((long)n) would work around that issue.

harold
  • 61,398
  • 6
  • 86
  • 164