Блог пользователя Hz_

Автор Hz_, 4 года назад, По-английски

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.)

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +35 Проголосовать: не нравится

Precision error?

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      Try this link Casio Web Calculator

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится -7 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

          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)

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -37 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +23 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 18   Проголосовать: нравится +2 Проголосовать: не нравится

      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
              }
          }
      }
      
»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Use log2l

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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. :-)

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Wikipedia has a pretty good description of the double format.