log2 calculation gives wrong result in cpp

Question

both visual studio 2015 and gcc4.8 gives wrong result when calculating the log2 value of numbers greater than 49 ones.

double log2_49_ones = log2(0x1FFFFFFFFFFFF); // result is 49 - should be 48
double log2_48_ones = log2(0xFFFFFFFFFFFF); // result is 47 - correct result

Any idea if it is a bug ?

[`log2()`](http://en.cppreference.com/w/cpp/numeric/math/log2) is supposed to take `double` values? — πάντα ῥεῖ, May 13 '17 at 16:50
`std::log2` does not return an integer value see: http://en.cppreference.com/w/cpp/numeric/math/log2 and as integer arguments are cast to double you are probably loosing precision. — Richard Critten, May 13 '17 at 16:52
this will also get bad value : double log2_49_ones = log2(0x1FFFFFFFFFFFF); — Or Davidi, May 13 '17 at 16:54
@OrDavidi As seen [here](http://ideone.com/yeVdIZ), `log2(0xFFFFFFFFFFFF);` returns 48, not 47, as you claim, which is correct, since `0xFFFFFFFFFFFF` is 2 to the 48 power. So, there's no surprise that `log2(0x1FFFFFFFFFFFF)` returns 49, since the value is 2 to the 49th power. Your expectations are wrong. — Algirdas Preidžius, May 13 '17 at 16:59
Java's math library [talks about](https://docs.oracle.com/javase/8/docs/api/java/lang/Math.html) precision issues explicitly. Irrational functions like `log2()` are not guaranteed to produce the correctly rounded result, but may have an error of a few ULPs. — Nayuki, May 13 '17 at 17:07
@AlgirdasPreidžius a number with so many bits set is definitely not any power of two — harold, May 13 '17 at 17:32
As was mentioned by @AlgirdasPreidžius you expectations are wrong. Please check result of `std::pow (2, 49) - 0x1FFFFFFFFFFFF`, and `std::pow (2, 48) - 0x1FFFFFFFFFFFF`. — Gluttton, May 13 '17 at 18:37
@harold: It is obvious that `0x1FFFFFFFFFFFF` is actually `pow(2, 49) - 1`, so the `log2()` value should be ever so slightly below `49.0`, and is probably rounded to `49.0` on output. Similar arguments for the other value. — Rudy Velthuis, May 14 '17 at 22:20

score 2 · Answer 1 · edited May 23 '17 at 12:26

2

log2() takes a float/double number as a parameter, thus you are probably losing precision during the implicit casting.

You could use this trick:

unsigned int number = 59029; // example
int targetlevel = 0;
while (number >>= 1) ++targetlevel;

courtesy of this answer.

edited May 23 '17 at 12:26

Community

1
1

answered May 13 '17 at 16:59

gsamaras

71,951
46
188
305

[`log2`](http://en.cppreference.com/w/cpp/numeric/math/log2) also takes `long double` as an argument, where the numbers that OP is passing, fits without a precision loss. – Algirdas Preidžius May 13 '17 at 17:02
2

@AlgirdasPreidžius But the spec says that integral arguments are cast to double, not long double. see case (4): http://en.cppreference.com/w/cpp/numeric/math/log2 – Richard Critten May 13 '17 at 17:23

ProfDFrancis · Answer 2 · 2017-05-16T04:05:35.583

0

The same floating point formats are used in multiple languages, and so this can be a generic problem. In Javascript in Chrome 58 for Windows, for example, I see the same results as you.

Math.log2(0x1FFFFFFFFFFFF) 
49 // this really is 49, i.e. if you subtract 49, it is 0
Math.log2(0xFFFFFFFFFFFF) 
47.99999999999999 // This would be 47 if put into an int

Let's not call this a bug: it is working near the limits of the capabilities of the floating point format and/or the software libraries.

If you want the correct answer up to about 2^53, then for largish numbers you can do some integer division, so that log2 can stay operating in its comfortable range. In Javascript (sorry! don't kill me please), for example

function betterLog2 (x) {
    if (x<2**32){
        return Math.log2(x)
    } else { 
        return 32 + Math.log2(parseInt(x/(2**32)))
    }
}

It seems to give correct answers for integers up to 2^53-1.

The same principle should work in any language and implementation. I doubt any language implementation would have a library that rounds up log 2 for values under 2**32.

Hope it helps 8-)

edited May 16 '17 at 04:05

answered May 13 '17 at 16:59

ProfDFrancis

8,816
1
17
26

3

This is question about C++, not Javascript. – Algirdas Preidžius May 13 '17 at 17:02
Both languages might use the same floating-point math libraries. FP issues can often be reproduced in multiple languages, such as the classic `0.1 + 0.2 != 0.3` problem – Nayuki May 13 '17 at 17:05
Thanks Nayuki! Yes, for me in Javascript 0.1+0.2 gives 0.30000000000000004. Many languages, under the hood, are using https://en.wikipedia.org/wiki/IEEE_floating_point. Excellent library but we just need to be aware of the limitations, and the value of this awareness transcends individual programming languages. – ProfDFrancis May 13 '17 at 17:19
1

@Eureka: IEEE floating point is not a library, it is a standard, which is (or is claimed to be) implemented, as well as possible, by many different libraries. It is possible that Javascript internally uses a C or C++ runtime library, but if it does, it is not certain which one. Actually, it may depend on the browser, I guess. – Rudy Velthuis May 14 '17 at 22:16
@Rudy Velthuis: Thank you for clarifying this and sorry for my sloppy thinking. I have corrected my answer. I've left my incorrectly-worded comment above, so that people can understand your comment. – ProfDFrancis May 16 '17 at 04:07

log2 calculation gives wrong result in cpp

2 Answers2