0

I wonder if the following should be reported as a bug in gcc implementation of standard library.

For all unsigned integers i, if we compare int(std::sqrt(i)) to the actual square root of the integer, the conversion always give the good result. If we do the same with std::cbrt it's not the case :

// Problem of rounding of std::cbrt for i from 0 to 100 million
// i, exact cbrt(i), result of int(std::cbrt(i))
2197, 13, 12
17576, 26, 25
24389, 29, 28
140608, 52, 51
185193, 57, 56
195112, 58, 57
226981, 61, 60
1092727, 103, 102
1124864, 104, 103
1442897, 113, 112
1481544, 114, 113
1560896, 116, 115
1685159, 119, 118
1815848, 122, 121
8741816, 206, 205
8869743, 207, 206
8998912, 208, 207
9393931, 211, 210
9938375, 215, 214
11543176, 226, 225
11852352, 228, 227
12487168, 232, 231
12649337, 233, 232
13481272, 238, 237
13651919, 239, 238
14348907, 243, 242
14526784, 244, 243
14706125, 245, 244
69426531, 411, 410
69934528, 412, 411
70957944, 414, 413
71991296, 416, 415
72511713, 417, 416
73560059, 419, 418
74618461, 421, 420
75151448, 422, 421
79507000, 430, 429
88121125, 445, 444
89314623, 447, 446
91733851, 451, 450
92345408, 452, 451
92959677, 453, 452
94818816, 456, 455
99897344, 464, 463

Do you think that should be reported as a defect ?

Vincent
  • 57,703
  • 61
  • 205
  • 388
  • per-chance this is because of floating point conversion of the input value prior to the actual cube-root, and the cube-root compounds the delta? – WhozCraig Jan 14 '13 at 01:17
  • 2
    Try rounding instead of truncation. – Ben Voigt Jan 14 '13 at 01:24
  • @WhozCraig: There's no representation error (in data type `double`) for integers in the range shown. – Ben Voigt Jan 14 '13 at 01:25
  • What version are you using? This seems fine in GCC 4.3.4: http://ideone.com/JRcWpx. – Oliver Charlesworth Jan 14 '13 at 01:32
  • As an aside, whenever you get unexpected results in your code, the immediate assumption should be that your code is wrong - it is extremely unlikely in most cases that you will have stumbled across a compiler bug. – JBentley Jan 14 '13 at 01:47
  • @BenVoigt twas just a stab. I dunno how some of you guys keep the no-exact-rep vs. exact-rep floats straight. I swear some of you can just rattle them off from memory. The discussion in Jon's answer is interesting. – WhozCraig Jan 14 '13 at 03:28
  • @WhozCraig: IEEE-754 `double` is a 53-bit integer (52 bits stored, the first bit is always 1), with the sign and the location of the decimal point (binary point?) stored in the remaining space. So all integers up to 2^53-1 can be trivially stored by putting the binary point right after the entire integral part. 2^53 can be stored as well, because it has trailing zeros. 2^53+1 can't be stored exactly. 2^53+2 is stored like 2^52+1 and the binary point moved over once more (to multiply by 2). – Ben Voigt Jan 14 '13 at 04:25

1 Answers1

2

std::cbrt returns a floating point type (float, double, etc.) but you are converting it to an int. Such conversions truncate rather than round e.g. 0.9999 becomes 0. Although it may seem logical that the cube root of 2197 is an integer, due to the fact that floating point types are stored in binary, it is not always possible to perfectly represent a decimal number, and such inaccuracies are likely to propagate during the calculations that std::cbrt performs. If for example, std::cbrt(2197) == 12.99999 (my compiler doesn't support it so I can't check the real value), then by converting it to an int you are truncating the value to 12.

To correct your code, round the result of std::cbrt(i) before converting it to an int. See this question for an idea of how to do that.

Community
  • 1
  • 1
JBentley
  • 6,099
  • 5
  • 37
  • 72
  • This is all reasonable. The remaining question is: is `cbrt(2197)` allowed to return `12.999999`? – Oliver Charlesworth Jan 14 '13 at 01:51
  • 2
    There is absolutely no problem representing a small integer precisely in floating point; both `13` and `2197` have precise floating point representations, even as `float`. The problem is that the computation of `cbrt` with whatever standard c library is being used by OP is slightly inaccurate. The solution (for integer cube root) is as you suggest. – rici Jan 14 '13 at 01:51
  • @rici I didn't say there is a problem representing integers precisely - I said decimal numbers (which includes non-integers). – JBentley Jan 14 '13 at 01:53
  • @JonBentley: yes, but the cube root of 2197 is exactly 13. So if it were computed precisely, there would be no representation issue. – rici Jan 14 '13 at 01:54
  • @rici I see your point, but I was referring to the fact that internally, `cbrt` is working with floating point types for its calculations, and the result it returns will be the end result of any intermediate values it stores during it's calculations - any representation error will therefore propagate to the value it returns. – JBentley Jan 14 '13 at 01:58
  • 4
    @JonBentley: that would be a feeble excuse if the result were required to be correct. IEEE-754 requires square root to be correct (that is, the result must be the correctly rounded representation of the precise square root of the argument), and math libraries generally manage to do that. `cbrt` has no such guarantee, and math libraries may be off by 1 ULP (or more, for all I know, but 1 ULP is pretty common), as with trig functions. – rici Jan 14 '13 at 02:09