shadaBhai's blog

By shadaBhai, history, 3 years ago, In English

How many digits are there in a number n in a base b? There is a well-known theorem for that. You know it's floor(logb(n))+1.

We calculate it as floor(log10(n)/log10(b))+1 as you can find it through the basics of the logarithm. As you see it's a well-known formula and obviously your logic will say it must work for every number. Why? The floor of the logarithm of a number n is actually largest power of b which is not greater than n.

So if we want to calculate the number of digits in the binary representation of a n, it should be floor(log2(n))+1.

Using this, I calculate the length of the binary representation of a number for a long time. But today I encountered some counterexample of this. I solved the problem 1362C - Johnny and Another Rating Drop. My first submission (82557478)got WA in the last case(case 21) during the system test. I just counted the length of the binary representation and then did some work there. The value of n was 576460752303423485. Here the logarithmic formula says that the length should be 60. The log value comes to be 59. so the length is floor(59)+1 =60.

But when I did the binary representation on the calculator I found that the length is actually 59. So, I just changed the code and determined the length by determining the binary representation. Then it got AC(82574624). (This made me too much sad.)

Now why the formula didn't work here though it is a proved theorem?

Again as n is not a power of 2, so the log value should not be an integer number, shouldn't it come as a floating-point number?. But it comes as an integer number. So is there a bug in the system that calculates log in computers?

Sorry for my lack of knowledge. I expect to have some knowledge on that from the wise members of the community. Any suggestions are appreciated as this is my first blog. Thanks in advance.

Full text and comments »

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