REGARDING BUILT IN LOG2 and manual calculation in FIBEASY

When i used built-in Log2 in python library i got WA for second subtask and But when I manually calculated log2 i got correct AC

WRONG

AC

1 Like

I think the problem is due to approximation. For small testcases it may seem to work. But for larger values the error may be too high to ignore (ie answer may vary by ± 1 index position) , thereby rendering WA.

i checked for 10^18 from both files i got 7 in both cases

Even tried Both C++ and Python

fails for some inputs between 1 \leq 10^{18} not checking just for 10^{18} gets AC. WA due to precision errors bro

I write it as log2((long double)n) in c++ . It showed AC.

2 Likes

I had the same issue in Python while using math.log2() , I then used bit_length() -1

can you please elaborate?

Try log2(2**59 - 1) in Python, it yields 59.0
Likewise, in C++ int(log2(2^59 - 1)) yields 59

Log2 isn’t very reliable for ‘exact’ computations. It is better to implement it manually for the specific use cases required in your problem.

4 Likes

https://codeforces.com/blog/entry/56975 here is the detailed explanation for those who use it in C++

2 Likes

Ohh I got it

> Be careful for log2

basically bit_length() returns the position of the highest set bit i.e. the length of the binary representation of the number (i.e. log2)
refer to this link https://stackoverflow.com/questions/3719631/log-to-the-base-2-in-python

1 Like

Same happened to me also
Ac code
WA

Check for this:

1
18014398509481983

The output should be 9, I think yours should give 2.

2 Likes

Yes Built-in Log Program is giving answer 2

Yes, the log function is losing precision for large numbers. That’s the reason for WA. This link explains the problem for C++, but I think the reason for Python should be the same.

Faced the same problem with log2(n) but log2l(n) will work fine in c++…

Yes, after many WA. I did the same thing and got AC.
that is log2((long double)n).
reason:
both long long int and double are of same size 8 bytes.
but when we pass long long int in log2 function then it will implicitly convert it into double.
and when large long long int converted into double it will lose some data because in double it will also store floating digits after this decimal point.

So, after type casting long long int into long double(12 bytes)…data of large number also not lossed…
This is my first contribution…hope it will be helpful

3 Likes