Hz_'s blog

Why log2((2^59)-1)=59?
By Hz_, 4 years ago, In English

Today I puzzled to find out the value of log2((2^59)-1). Here, (2^59)-1 = 576460752303423487. We know that the value of log2(4)=2, log2(3)=1.58496 and log2(576460752303423488)=59 but why log2(576460752303423487)=59 when log2(x)=y and x=2^y. This happens not only for (2^59)-1 but also for other values.

(I searched about it on google but couldn't find out the reason behind this.)

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (32)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +35 Vote: I do not like it

Precision error?

$$$log2$$$ is a double function, which means precision error could occur.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    But does the precision error occur in web calculators? I mean that I searched in some web calculators such as MiniWebtool, decode.fr etc. but same results found.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Try this link Casio Web Calculator

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +28 Vote: I do not like it

      Maybe the difference between $$$log2(2^{59}-1)$$$ and $$$log2(2^{59})$$$ are so small that the answer is automatically adjusted to $$$59$$$

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -7 Vote: I do not like it

        Is there any way to get the perfect floor result of this value in C++? I tried many times in a different way but failed.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 3   Vote: I like it +8 Vote: I do not like it

          convert number to binary and count length then subtract 1, and i'm pretty sure there's a c++ function too (that's just what i do in java)

          → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if you use the calculator on Windows 10 you can get 58.999999999999999997497323043895

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes , in a problem of previous contest I couldn't solve C because of this precision problem.

    → Reply
»
4 years ago, # |
  Vote: I like it -37 Vote: I do not like it

Because $$$log(x)$$$ in Competitive Programming is usually equal to $$$y$$$ where $$$y$$$ is the smallest integer such that $$$2^y >= x$$$.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This is because of precision error. The answer you are looking for is 58.9999999999999999975 A double variable cannot store these many decimal places. So it rounds it off to 59

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Is there any valid way to get 58 in C++?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      Write a simple loop and count how often you need to multiply by 2.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 18   Vote: I like it +2 Vote: I do not like it

      Simply implement it (for integer answers):

      int ilog(long long x){
    for(int i=0;i<=70;i++){
        if(1ll<<i >= x){
            return i;//if you want to ceil the answer, use this version
        }
        if(1ll<<i > x){
            return i-1;//if you want to floor the answer, use this version
        }
    }
}
      → Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

You can also use __builtin_clzll, which should be faster than a loop.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Or, if you want to remember less characters, __lg.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Interesting, I've never seen that even though it seems more direct (I don't actually use C++ so it's not that surprising, I guess).

      In Java for the other five Java users: Long.numberOfTrailingZeros(Long.highestOneBit(x)).

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        In Java, 63 - Long.numberOfLeadingZeros(x) would be faster.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Makes sense, thanks! I write it my way to avoid off by one mistakes (it's easiest for me, since it's pretty rare to write this anyway), but I will remember that in case I am reaching TLE.

          → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      What's the difference between log2 and __lg?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        __lg(2^59-1)=58

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 3   Vote: I like it +3 Vote: I do not like it

          Yes,it's amazing.

          Now I know __lg != log2 and std::__lg(block_sz — pos_l + 1), but my curiosity made me want to know the reason(maybe difference).

          I really want to know the reason why __lg is correct, so I can use it without doubt.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +45 Vote: I do not like it

            __lg is a function of integers

            log2 is a function of float/double/long double

            → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    https://en.cppreference.com/w/cpp/numeric/countl_zero

    → Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Use log2l

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://ideone.com/HcgbhH More to think about

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How is this possible? niyaznigmatul do you know the reason behind it?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      Sure, floating point numbers store first several digits, depending on the number of bits provided for that (mantissa), and the other bunch of bits show the decimal point location (exponent).

      For instance, for double it stores only 14-15 digits, and $$$2^{59}$$$ has more than that, the last digit isn't being stored.

      P.S. Actually, it's more complex than what I said, because it doesn't store decimal digits, it stores in binary, that's why, for example, $$$2^{59}$$$ is printed correctly https://ideone.com/dPsCa6

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I also tested for 2^59 vs 2^59 — 32 they both are showing the same result. As pointed by you, the 14-15 digits part is playing the role. :-)

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Wikipedia has a pretty good description of the double format.

      → Reply