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

How many digits are there in a number in certain base? Why the logarithmic formula doesn't work here?
Автор shadaBhai, история, 4 года назад, По-английски

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.

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

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

i'm pretty sure it's cuz u can't find the exact logarithm (we have good algos but not infinitely precise) so at larger and larger numbers it'll become less and less precise. i'm not sure how log is calculated but if you try and do stuff with the cosine and sine functions with absolute double precision you'll get weird comparison answers even if the answers when u do it by hand are the same. so i assume it's the same thing here, where the log should have been like 58.99999999999999999 but it rounded up to 59 automatically for you

edit: yeah that big number is 11111111111111111111111111111111111111111111111111111111101 in binary, so log computation could be like 0.0000000000000001 off or somth and just auto round up

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

I recommend that you use __builtin_clz and __builtin_clzll instead to calculate the binary lengths of numbers.

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

Yes, the problem is that log gives value in double. It can cause a lot of problems. You can use a function to calculate the least power of the base b greater than n. It will work in O(log n)

int digits(int n, int b){
if(b==1)
   return -1;
int pow=1;
int digits=0;
while(pow<=n){
   pow*=b;
   digits+=1;
}
return digits;
}
→ Ответить