PSA: don't use these functions unless you really, really need to
source link: https://codeforces.com/blog/entry/107717
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
PSA: don't use these functions unless you really, really need to
When solving problems in competitive programming, it is almost never a good idea to use the following inbuilt C++ functions. You will be hacked or fail a pretest or worse, a systest.
Why? Because they use floating-point numbers. They are designed to be used with a floating-point input and a floating-point output. The issue is that on a floating-point number, the result may not be exact. Worse, floating-point numbers may not be able to accurately encode the integer.
To calculate for positive integers and :
- Don't use
floor((double) a / (double) b)
or similar. - Do use
a / b
. It will round down. - Warning: be careful with negative numbers. The answer depends on whether we should round down or towards 0.
To calculate for positive integers and :
- Don't use
ceil((double) a / (double) b)
or similar. - Do use
(a + b - 1) / b
. - Warning: the same caveat goes for negative numbers as before.
To calculate for a nonnegative integer :
- Don't use
sqrt(a)
or similar. - Do use binary search to calculate the square root.
To calculate for nonnegative integers and :
- Don't use
pow(a, b)
or similar. - Do use the naive algorithm. If you really want to do this and fits in a long long, then it will take no more than 64 steps, unless or , in which case you can just return .
To calculate for a positive integer :
- Don't use
log2(a)
or similar. - Do use
__lg
or an approach based on__builtin_clz
or__builtin_clzll
. The "clz" stands for "count leading zeroes" and it does exactly what it says — on the binary representation of the number. If you have access to C++20, there is also thebit_width
library function. - Warning:
__builtin_clz(0)
and__builtin_clzll(0)
are undefined behavior. Also all these functions starting with__
are specific to GCC and you're technically not meant to use them, but it's fine in competitive programming.
Exceptions
The only major exception is if floating-point numbers are an inherent part of your solution. Most commonly, this happens in problems where the output is itself a floating-point number (especially geometry problems, sometimes probability). There are also some algorithms where you need to work with floating-point numbers even if the input and output are integer (FFT, possibly some LP).
But even in these cases, it's always a good idea to do as much as possible with integers and move to floats as late as possible.
I got WA with one compiler, accepted with another
Most likely it has to do with 64-bit versus 32-bit. Also the widths of the various floating-point types vary. It's possible that in some circumstances your solution is actually correct. However, rely on this only if you know what you're doing.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK